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

対応づけ　1 つの円卓に座った人たちについて、「各人をその時計回りの隣の人に移す」と考えると、その円卓は 1 つの巡回置換になる。回転して一致する座り方は同じ巡回置換を与える。逆に、巡回置換を 1 つ決めると円卓の座り方が 1 つ決まる。1 人だけの円卓は長さ $1$ の巡回（不動点）にあたる。

したがって、5 人を区別のない 2 つの円卓に座らせる方法は、5 文字の置換のうち巡回がちょうど 2 個のものと 1 対 1 に対応する。その個数は第 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]$$
を使う。初期値は $\left[\genfrac{}{}{0ex}{}{1}{1}\right]=1$ である。$k=1$ の場合は $\left[\genfrac{}{}{0ex}{}{n}{1}\right]=(n-1)!$ となる（全員が 1 つの円卓に座る円順列）。また $\left[\genfrac{}{}{0ex}{}{n}{n}\right]=1$ である。

• $n=2$: $\left[\genfrac{}{}{0ex}{}{2}{1}\right]=1,\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1$
• $n=3$: $\left[\genfrac{}{}{0ex}{}{3}{1}\right]=2,\left[\genfrac{}{}{0ex}{}{3}{2}\right]=\left[\genfrac{}{}{0ex}{}{2}{1}\right]+2\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1+2=3$
• $n=4$: $\left[\genfrac{}{}{0ex}{}{4}{1}\right]=6,\left[\genfrac{}{}{0ex}{}{4}{2}\right]=\left[\genfrac{}{}{0ex}{}{3}{1}\right]+3\left[\genfrac{}{}{0ex}{}{3}{2}\right]=2+9=11$
• $n=5$: $\left[\genfrac{}{}{0ex}{}{5}{2}\right]=\left[\genfrac{}{}{0ex}{}{4}{1}\right]+4\left[\genfrac{}{}{0ex}{}{4}{2}\right]=6+44=50$

検算　円卓の人数の組で分けて数える。
- $1$ 人と $4$ 人のとき：1 人を選ぶ方法が $5$ 通り、4 人の円順列が $3!=6$ 通りなので $5\times 6=30$ 通り。
- $2$ 人と $3$ 人のとき：2 人を選ぶ方法が $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り。2 人の円順列は $1$ 通り、3 人の円順列は $2!=2$ 通りなので $10\times 1\times 2=20$ 通り。

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

よって、座り方は $50$ 通りである。

これは符号なし第1種スターリング数 $c(5,2)$ を求める問題である。円卓が区別されず、各円卓で回転のみ同一視するので、5 人を 2 つの巡回置換（サイクル）に分ける置換の個数に等しい。

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

別の方法で検算する。人数の分け方で数える。
・1人と4人: $\left(\genfrac{}{}{0ex}{}{5}{1}\right)\times 0!\times 3!=5\times 6=30$。
・2人と3人: $\left(\genfrac{}{}{0ex}{}{5}{2}\right)\times 1!\times 2!=10\times 2=20$。
合計は $30+20=50$。

答えは 50 通り。