漸化式

1. 求めたい「$n$ 回目の確率」を $a_n$ とおく
2. $a_n$ と $a_{n-1}$ の関係を漸化式で表す
3. 漸化式を解く

$n\geqq 2$ とする。$1$ から $n$ までの整数を並び替えてできる順列のうち，すべての $i$ について「$i$ 番目が $i$ でない」を満たすものの個数 $a_n$ は

$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$

フィボナッチ数列(fibonacci sequence)とは，

• 最初の2つは $1$ で，
• 3つめ以降は「前の2つを足したもの」

になる数列のこと。つまり，

$1,1,2,3,5,8,13,21,34,\dots$

数列 $a_n$ に対して， $$f(x)=\displaystyle\sum_{k=0}^{\infty} a_k x^k$$ を（数列 $a_n$ の）母関数と呼ぶことがある。

$$\int_0^{\frac{\pi}{2}}\sin^n xdx = \int_0^{\frac{\pi}{2}}\cos^n xdx = \begin{cases} \dfrac{(n-1)!!}{n!!} &(n \text{が奇数})\\ \dfrac{(n-1)!!}{n!!}\dfrac{\pi}{2} &(n \text{が偶数}) \end{cases}$$

漸化式 $$a_{n+1} = 4 a_n (1-a_n)$$ は，$a_1=\sin^2\theta$ と置くと倍角公式が出現してうまくいきます。知らないと厳しい問題です。

$n$ を $2$ 以上の整数とする。$1$ から $n$ までの数字が書かれた札が各1枚ずつ合計 $n$ 枚あり，横一列におかれている。$1$ 以上 $(n-1)$ 以下の整数 $i$ に対して，次の操作 $(\mathrm{T}_i)$ を考える。

$(\mathrm{T}_i)$：左から $i$ 番目の札の数字が，左から $(i+1)$ 番目の札の数字よりも大きければ，これら2枚の札の位置を入れかえる。そうでなければ，札の位置をかえない。

最初の状態において札の数字は左から $A_1, A_2, \cdots , A_n$ であったとする。この状態から $(n-1)$ 回の操作 $(\mathrm{T}_1), (\mathrm{T}_2) , \cdots , (\mathrm{T}_{n-1})$ を順に行った後，続けて $(n-1)$ 回の操作 $(\mathrm{T}_{n-1}), \cdots ,(\mathrm{T}_2) , (\mathrm{T}_{1})$ を順に行ったところ，札の数字は左から $1,2, \cdots , n$ と小さい順に並んだ。以下の問いに答えよ。

1. $A_1$ と $A_2$ のうち少なくとも一方は $2$ 以下であることを示せ。
2. 最初の状態としてありうる札の数字の並び方 $A_1,A_2, \cdots , A_n$ の総数を $c_n$ とする。$n$ が $4$ 以上の整数であるとき，$c_n$ を $c_{n-1}$ と $c_{n-2}$ を用いて表せ。

カタラン数とは， $$c_n=\dfrac{{}_{2n}\mathrm{C}_{n}}{n+1}$$ で定義される数 $c_n$ のこと。