NF杯2024(E) - 漸化式を立てずに数え上げ　その2

　いわゆる simasima special (参考： https://mathlog.info/articles/nNX6dXUeyb35vYurGP5l ) の簡単な適用例として最後の数え上げを行う． 　 　本解のように $x_i = \frac{y_i}{2}$ とおく． 　$y_i\in \{ 0,1,2,3,4 \}$ であり，$y_1 + \dots + y_{10}$ が偶数であるような組 $(y_1,\dots, y_{10})$ の個数を求めればよい．

　集合 $A, B$ を $A = \{ 0,1,2,3 \}$, $B = \{ 4\}$ とおく．$y_i \in A$ であるかどうかで列 $Y = (y_1,\dots, y_{10})$ を $(A,B,\dots)$ のように変換した列を $T$ とおく．

　$T = (B,\dots, B)$ であるとき，すべての $i$ で $y_i = 4$ であり，明らかに条件を満たす． 　$T$ が $A$ を $a \geq 1$ 個含む列であるとする（このような $T$ は ${}_{10}\mathrm{C}_{a}$ 個ある）．その $A$ を一つ選び，それが $k$ 番目であるとする．このとき，$i\neq k$ を満たす $y_i$ をどのように選んでも ($4^{a-1}$通り)，ちょうど2つの $y_k \in A$ が存在して $y_k + \sum_{i\neq k} y_i \equiv 0\pmod{2}$ にできるので，$2\cdot 4^{a-1}$ 通り条件を満たす組が見つかる． 　これらと二項定理より $$\begin{aligned} a_{10} &= 1 + \sum_{a=1}^{10} 2\cdot 4^{a-1}{}_{10}\mathrm{C}_{a} = 1 + \frac{1}{2}\{ (4+1)^{10} - 1\} \\ &= \frac{5^{10} + 1}{2} \end{aligned}$$ を得る．