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

第1種スターリング数（符号なし）を $c(n,k)$ と書く。これは $n$ 個の区別できる元の置換のうち、巡回の個数がちょうど $k$ であるものの個数である。

$c(n,2)$ の値　漸化式
$$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$$
を使う。$c(n,1)=(n-1)!$ なので、次のように順に求まる。
$$c(2,2)=1,$$
$$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$ 個の元を $2$ 個の巡回に分けることはできないので $c(1,2)=0$ である。

数え上げ　$1$ と $2$ を含む巡回の長さを $L$ とし、$L$ で場合分けする。
- その巡回に入る残り $L-2$ 個の元を、$\{3,\dots ,7\}$ の $5$ 個から選ぶ方法は $\left(\genfrac{}{}{0ex}{}{5}{L-2}\right)$ 通りである。
- 選んだ $L$ 個の元で $1$ つの巡回を作る方法は $(L-1)!$ 通りである。
- 残りの $7-L$ 個の元は、ちょうど $2$ 個の巡回に分ける必要がある。その方法は $c(7-L,2)$ 通りである。

よって求める個数は
$$N=\sum _{L=2}^6\left(\genfrac{}{}{0ex}{}{5}{L-2}\right)(L-1)!c(7-L,2)$$
である。各項を計算すると次のようになる。
- $L=2$: $1\cdot 1\cdot c(5,2)=50$
- $L=3$: $5\cdot 2\cdot c(4,2)=10\cdot 11=110$
- $L=4$: $10\cdot 6\cdot c(3,2)=60\cdot 3=180$
- $L=5$: $10\cdot 24\cdot c(2,2)=240$
- $L=6$: $c(1,2)=0$ より $0$

したがって
$$N=50+110+180+240=580$$
である。

検算　互換 $(12)$ を左から掛ける写像 $\sigma \mapsto (12)\sigma$ は全単射である。$1,2$ が同じ巡回にあればその巡回は $2$ つに分かれ、別々の巡回にあれば $2$ つの巡回が $1$ つにつながる。よって、「巡回 $3$ 個で $1,2$ が別々の巡回にある置換」の個数は、「巡回 $2$ 個で $1,2$ が同じ巡回にある置換」の個数に等しい。

後者を同じ方法で数える。残りの $7-L$ 個は $1$ 個の巡回にするので $c(7-L,1)=(6-L)!$ を使う。
$$1\cdot 24+5\cdot 2\cdot 6+10\cdot 6\cdot 2+10\cdot 24\cdot 1+5\cdot 120\cdot 1=24+60+120+240+600=1044.$$
すると $580+1044=1624=c(7,3)$ となり、全体の個数と一致する。

答えは $580$ である。

1 と 2 が同じ巡回に属する、巡回数ちょうど 3 の置換を数える。

1 と 2 が同じ巡回にあれば、2 は不動点ではない。2 を巡回から取り除くと、$\{1,3,4,5,6,7\}$ の置換で巡回数 3 のものが得られる。

逆に、この 6 元の置換に 2 を戻すには、1 を含む巡回の任意の元の直後に 2 を挿入すればよい。挿入位置の数は 1 を含む巡回の長さ $L$ に等しい。よって求める個数は、6 元の置換で巡回数 3 のものについての $L$ の総和である。

1 を含む巡回の長さが $L$ である 6 元置換の個数は $\left(\genfrac{}{}{0ex}{}{5}{L-1}\right)(L-1)!c(6-L,2)$ である。ここで $c(n,k)$ は第 1 種スターリング数（符号なし）。
- $L=1$: $c(5,2)=50$ 個
- $L=2$: $5\cdot 1\cdot c(4,2)=5\cdot 11=55$ 個
- $L=3$: $10\cdot 2\cdot c(3,2)=10\cdot 2\cdot 3=60$ 個
- $L=4$: $10\cdot 6\cdot c(2,2)=60$ 個
- $L=5$: $c(1,2)=0$ 個

合計は $50+55+60+60=225=c(6,3)$ で一致する。

$L$ の総和は $1\cdot 50+2\cdot 55+3\cdot 60+4\cdot 60=50+110+180+240=580$。

検算: 巡回数 3 の置換の総数は $c(7,3)=1624$。これは $c(6,2)+6c(6,3)=274+1350$ とも一致する。したがって 1 と 2 が別の巡回になるものは $1624-580=1044$ 個で、矛盾はない。

答え: 580