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

言い換え 生徒を番号で表すと、求めるものは集合 $\{1,2,\dots ,7\}$ を空でない $4$ つのブロックに分ける分割のうち、どのブロックも連続する $2$ 整数 $i,i+1$ を同時に含まないものの個数です。

帰着 $\{1,\dots ,n\}$ をこの条件のもとで $k$ ブロックに分割する方法の数を $T(n,k)$ とします。最大の数 $n$ に注目して数えます。

• $n$ だけで $1$ つのブロックをつくる場合：残りは $\{1,\dots ,n-1\}$ の条件つき $(k-1)$ ブロック分割なので、$T(n-1,k-1)$ 通りです。
• $n$ がほかの数と同じブロックに入る場合：$n$ を除くと $\{1,\dots ,n-1\}$ の条件つき $k$ ブロック分割が残ります。$n$ は $k$ 個のブロックのうち $n-1$ を含むもの以外の $k-1$ 個のどれかに入れられるので、$(k-1)T(n-1,k)$ 通りです。

よって
$$T(n,k)=T(n-1,k-1)+(k-1)T(n-1,k)$$
が成り立ちます。一方、$S(n-1,k-1)$ は第 2 種スターリング数の漸化式から
$$S(n-1,k-1)=S(n-2,k-2)+(k-1)S(n-2,k-1)$$
を満たします。これは $T$ と同じ形の漸化式です。さらに $T(1,1)=1=S(0,0)$ で初期値も一致するので、$T(n,k)=S(n-1,k-1)$ です。

したがって、求める数は
$$T(7,4)=S(6,3)$$
です。

$S(6,3)$ の計算 漸化式 $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ と、$S(n,1)=1$、$S(n,n)=1$ を使って表を作ります。

$k=2$ の列：
$$S(3,2)=S(2,1)+2S(2,2)=1+2=3$$
$$S(4,2)=S(3,1)+2S(3,2)=1+6=7$$
$$S(5,2)=S(4,1)+2S(4,2)=1+14=15$$

$k=3$ の列：
$$S(4,3)=S(3,2)+3S(3,3)=3+3=6$$
$$S(5,3)=S(4,2)+3S(4,3)=7+18=25$$
$$S(6,3)=S(5,2)+3S(5,3)=15+75=90$$

よって、チームの分け方は $90$ 通りです。

7人を頂点とし、隣り合う席を辺で結ぶとパス $P_7$ になる。求める数は、$P_7$ の頂点を空でない独立集合ちょうど4つに分ける分割の数である。

まず、$k$ 色で隣り合う頂点が異なる色になる塗り方は $P(k)=k(k-1{)}^6$ 通りである。

4色すべてを使う塗り方の数は、包除原理より
$P(4)-4P(3)+6P(2)-4P(1)$
$=4\cdot 3^6-4\cdot 3\cdot 2^6+6\cdot 2\cdot 1-0$
$=2916-768+12=2160$ 通り。

チームは区別しないので、色の入れ替え $4!=24$ 通りで割ると $2160/24=90$ 通り。

検算：同じ方法で2チームの場合を求めると $(P(2)-2P(1))/2=1$ となる。これは奇数番と偶数番に分ける1通りだけで、正しい。