離散数学・組合せ論の問題

求める個数は、第 1 種スターリング数 $\left[\genfrac{}{}{0ex}{}{5}{2}\right]$ です。漸化式
$$\left[\genfrac{}{}{0ex}{}{n}{k}\right]=\left[\genfrac{}{}{0ex}{}{n-1}{k-1}\right]+(n-1)\left[\genfrac{}{}{0ex}{}{n-1}{k}\right]$$
を使って、小さい $n$ から順に計算します。

この漸化式の意味は次のとおりです。$n$ 文字の置換で巡回が $k$ 個のものは、文字 $n$ について次の 2 通りに分けられます。
- $n$ が不動点（長さ $1$ の巡回）になっている場合：残りの $n-1$ 文字で巡回が $k-1$ 個の置換を作ればよいので $\left[\genfrac{}{}{0ex}{}{n-1}{k-1}\right]$ 通り。
- $n$ がほかの巡回の中に入っている場合：$n-1$ 文字で巡回が $k$ 個の置換を作り、そのどれかの文字の直後に $n$ を差し込む。差し込む位置は $n-1$ 通りなので $(n-1)\left[\genfrac{}{}{0ex}{}{n-1}{k}\right]$ 通り。

初期値は $\left[\genfrac{}{}{0ex}{}{1}{1}\right]=1$ で、$k=0$ や $k>n$ のときは $0$ です。また $\left[\genfrac{}{}{0ex}{}{n}{1}\right]=(n-1)!$、$\left[\genfrac{}{}{0ex}{}{n}{n}\right]=1$ です。

順に計算すると
$$\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1,\left[\genfrac{}{}{0ex}{}{3}{2}\right]=\left[\genfrac{}{}{0ex}{}{2}{1}\right]+2\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1+2\cdot 1=3,$$
$$\left[\genfrac{}{}{0ex}{}{4}{2}\right]=\left[\genfrac{}{}{0ex}{}{3}{1}\right]+3\left[\genfrac{}{}{0ex}{}{3}{2}\right]=2+3\cdot 3=11,$$
$$\left[\genfrac{}{}{0ex}{}{5}{2}\right]=\left[\genfrac{}{}{0ex}{}{4}{1}\right]+4\left[\genfrac{}{}{0ex}{}{4}{2}\right]=6+4\cdot 11=50.$$

（検算）$x(x+1)(x+2)(x+3)(x+4)$ を展開すると $x^5+10x^4+35x^3+50x^2+24x$ となり、$x^2$ の係数は $50$ です。また、巡回型で数えると、長さ $4$ と $1$ の巡回に分かれるものが $5\times 3!=30$ 個、長さ $3$ と $2$ に分かれるものが $\left(\genfrac{}{}{0ex}{}{5}{3}\right)\times 2!\times 1!=20$ 個で、合計 $50$ 個です。

よって、求める個数は $50$ です。

巡回の個数がちょうど $k$ 個の $n$ 次の置換の個数は第一種スターリング数（符号なし）$c(n,k)$ である。$c(5,2)$ を求める。

漸化式 $c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$ を使う。
- $c(1,1)=1$
- $c(2,2)=1,c(2,1)=1$
- $c(3,1)=2,c(3,2)=c(2,1)+2c(2,2)=3,c(3,3)=1$
- $c(4,1)=6,c(4,2)=c(3,1)+3c(3,2)=2+9=11$
- $c(5,2)=c(4,1)+4c(4,2)=6+44=50$

別の方法による検算として、巡回の長さの分割で数える。
- 長さ $(4,1)$: 不動点の選び方が $5$ 通り、残り $4$ 個の巡回は $3!=6$ 通りなので $30$ 通り。
- 長さ $(3,2)$: 3 個の選び方が $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通り、3 巡回が $2$ 通り、2 巡回が $1$ 通りなので $20$ 通り。

合計は $30+20=50$ となり、漸化式の結果と一致する。