　整数 $m, n \geq 3$ に対し，パンを含む $m$ 種類の食材を以下の条件を満たすように積み上げたものを $m$ 種類の食材を使った $n$ 段の**サンドイッチ**とよぶ．
- 食材をちょうど $n$ 段積み上げたものである．
- 最も上の段および最も下の段の食材はパンである．
- 同じ具が連続して積み上がることはない．
- パティは含まれていなくても構わない．

　ハンバーガーはパティが含まれるサンドイッチであるため，$m$ 種類の食材を使った $n$ 段のサンドイッチの種類数を $f_m(n)$ とすると，ハンバーガーの種類数は $f_5(10) - f_4(10)$ である．$n+2$ 段のサンドイッチの種類数を考えると，これの $1, n+2$ 段目はパンである．

- $3$ 段目にパン以外の食材が入る場合，$3$ 段目から $n+1$ 段目までの食材の並び方は $n+1$ 段のサンドイッチの種類数と等しく $f_m(n+1)$ 通りあり，このとき $2$ 段目に入る食材は $m-2$ 通りあるので，この場合の $n+2$ 段のサンドイッチは $(m-2)f_m(n+1)$ 通りある．

- $3$ 段目にパンが入る場合，$4$ 段目から $n+1$ 段目までの食材の並び方は $n$ 段のサンドイッチの種類数と等しく $f_m(n)$ 通りあり，このとき $2$ 段目に入る食材は $m-1$ 通りあるので，この場合の $n+2$ 段のサンドイッチは $(m-1)f_m(n)$ 通りある．

　以上の議論より，
$$ f_m(n+2) = (m-2)f_m(n+1) + (m-1)f_m(n) $$
であり，$f_m(3) = m-1$，$f_m(4) = (m-1)(m-2)$ と合わせて
$$ f_m(n) = \frac{m-1}{m} \left( (m-1)^{n-2} - (-1)^{n-2} \right) $$
を得る．求める値は
$$ f_5(10) - f_4(10) = \frac{4}{5} \left( 4^8 - (-1)^8 \right) - \frac{3}{4} \left( 3^8 - (-1)^{8} \right) = \frac{4^{10} - 5 \cdot 3^9 - 1}{20} = \textbf{47508} $$
である．
公式解説
https://onlinemathcontest.com/contests/hamamatsu2023/editorial/4205
**包除原理を用いた別解**

以下の 4 条件を満たす長さ $10$ の整数列 $a$ を数え上げればよい．
- $(1): 1\leq a_i\leq 5$
- $(2): a_1 = a_{10} = 1 $
- $(3): a_i\neq a_{i+1}$
- $(4):a$ は $5$ を含む

これは，「$(1)$ かつ $(2)$ かつ $(3)$」を満たす数列 $a$ の個数から 「$1\leq a_i\leq 4$ かつ $(2)$ かつ $(3)$」を満たす数列 $a$ の個数を引いた値と等しい．

「$(1)$ かつ $(2)$ かつ $(3)$」を満たす数列 $a$ の個数の求め方について，包除原理が適用できる．必ず $a_i=a_{i+1}$ となる $i$ の個数を決め打ったとき（決め打つ個数を $c$ とする），「$(1)$ かつ $(2)$」を満たす数列 $a$ は $0\leq c\lt 9$ のとき $\dbinom{9}{c}5^{8-c}$，$c=9$ のとき $1$ であるから，求める個数は
$$\begin{aligned}
\sum_{c=0}^9 \dbinom{9}{c}5^{8-c}(-1)^c+(-1)^91&=\dfrac{1}{5}\sum_{c=0}^9 \dbinom{9}{c}5^{9-c}(-1)^c-\dfrac{4}{5}\\\\
&=\dfrac{4^9-4}{5}
\end{aligned}$$

である．「$1\leq a_i\leq 4$ かつ $(2)$ かつ $(3)$」の個数も同様に計算することで $\dfrac{3^9-3}{4}$ であると分かるから，本問題の答えは $\dfrac{4^9-4}{5}-\dfrac{3^9-3}{4}=47508$ である．
ユーザー解説
https://onlinemathcontest.com/contests/hamamatsu2023/editorial/4205/249
　$5$ 種類の食材（パン，パティ，チーズ，レタス，トマト）を，次の条件をみたすように上下にちょうど $10$ 段積み上げて，**ハンバーガー**を作ります：
- 最も上の段および最も下の段の食材はパンである．
- 少なくとも $1$ つのパティを含む．
- 同じ食材が隣接してはならない．
- 使わない食材があってもよい．

このとき，ハンバーガーとしてありうるものは何通りありますか？\
　ただし，上下は区別して考え，同じ食材は区別しないものとします．