NF杯2023(E)

黒石が$x$個あって,かつ一番左の黒石から一番右までの黒石までの間に白石が$y$個ある状態にするための操作列の場合の数を$dp(x,y)$とおくと,

$$dp(1,0)=1$$

$$dp(1,y)=0;(y\neq 0)$$

$$dp(x,y)=dp(x-1,y-1)+dp(x-1,y)+dp(x-1,y+1)(y+1);(x\gt 1,y\gt 0)$$

$$dp(x,y)=dp(x-1,y)+dp(x-1,y+1)(y+1);(x\gt 1,y= 0)$$

という漸化式が成立する.これをもとにして表を書くと

$$\begin{array}{r | r r r r r r r r r r r r } dp(x,y) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 4 & 6 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 10 & 16 & 12 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 6 & 26 & 50 & 40 & 20 & 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 7 & 76 & 156 & 150 & 80 & 30 & \color{blue} 6 & \color{blue} 1 & 0 & 0 & 0 & 0 & 0 \\ 8 & 232 & 532 & 546 & 350 & \color{blue} 140 & \color{blue} 42 & \color{blue} 7 & \color{blue} 1 & 0 & 0 & 0 & 0 \\ 9 & 764 & 1856 & 2128 & \color{blue} 1456 & \color{blue} 700 & \color{blue} 224 & \color{blue} 56 & \color{blue} 8 & \color{blue} 1 & 0 & 0 & 0 \\ 10 & 2620 & 6876 & \color{blue} 8352 & \color{blue} 6384 & \color{blue} 3276 & \color{blue} 1260 & \color{blue} 336 & \color{blue} 72 & \color{blue} 9 & \color{blue} 1 & 0 & 0 \\ 11 & \color{red} 9496 & \color{blue} 26200 & \color{blue} 34380 & \color{blue} 27840 & \color{blue} 15960 & \color{blue} 6552 & \color{blue} 2100 & \color{blue} 480 & \color{blue} 90 & \color{blue} 10 & \color{blue} 1 & 0 \\ \end{array}$$

より,答えは$dp(11,0)=9496$である.なお,この問題を解答するにあたっては,上記の表における青文字の部分は計算する必要は無いことに注意.

余談だが,

$$a_N=dp(N+1,0)=\sum_{n=0}^{\lfloor N/2\rfloor }{}_{N}\mathrm{C}_{2n}\cdot (2n-1)!!$$

が成立する.

ここで,シグマの各項は「黒を向いた石の2つ隣にある白石をひっくり返す」操作をちょうど$n$回行うときの操作列の場合の数となっている.