浜松2023(G)

包除原理を用いた別解

以下の 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$ である．