NF杯2023(E)

　まず一般の $n$ に対し，黒を向いた石が $1$ つあり，その右側に白を向いた石が $n$ 個ある場合の方法の数 $a_n$ について考える．$a_1=1, ~ a_2=2$ である．
　$n\geq3$ の場合について，次のように場合分けして考える：

(i)　最初に左から2番目にある石を裏返す場合：
　残りの石の状態は $n-1$ での初期状態と同じとみなせるので，この場合は $a_{n-1}$ 通り.

(ii)最初に左から3番目にある石を裏返す場合：
　左から3番目以降にある石の状態は $n-2$ での初期状態と同じとみなせるので，左から4番目以降のオセロを裏返す順番は $a_{n-2}$ 通りある．そのうち一つを選んだあと，左から2番目にある石を任意のタイミングで裏返すことができるから，まとめるとこの場合は $(n-1)a_{n-2}$ 通りである．

よって，$n\geq3$ のとき $a_n=a_{n-1}+(n-1)a_{n-2}$ が成り立つ．順次計算することで，$a_{10}=\mathbf{9496}$ である．