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

人 $P_i$ を整数 $i$ と同一視すると、求める個数は「$\{1,2,\dots ,7\}$ を空でない $4$ つのブロックに分割する方法のうち、どのブロックも連続する $2$ 整数 $i,i+1$ を同時に含まないもの」の個数である。

帰着 $\{1,\dots ,n\}$ の $k$ ブロック分割で連続する 2 整数を同じブロックに含まないものの個数を $T(n,k)$ とすると、$T(n,k)=S(n-1,k-1)$ が成り立つ。

理由：$n$ に注目する。$n$ が $1$ 元だけのブロックなら、残りは $\{1,\dots ,n-1\}$ の条件をみたす $k-1$ ブロック分割になる。そうでなければ、$\{1,\dots ,n-1\}$ の条件をみたす $k$ ブロック分割の、$n-1$ を含まない $k-1$ 個のブロックのどれかに $n$ を入れることになる。よって
$$T(n,k)=T(n-1,k-1)+(k-1)T(n-1,k)$$
である。これは $S(n-1,k-1)=S(n-2,k-2)+(k-1)S(n-2,k-1)$ と同じ形の漸化式であり、初期値も一致するので、$T(n,k)=S(n-1,k-1)$ となる。

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

表を作る 漸化式 $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ を使う。

まず $k=2$ の列を求める。$S(n,1)=1$ なので
- $S(2,2)=1$
- $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(3,3)=1$
- $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$ 色での正則彩色の数は $f(k)=k(k-1{)}^6$ である。

ちょうど4色をすべて使う彩色の数を、包除原理で求める。
$f(4)-\left(\genfrac{}{}{0ex}{}{4}{3}\right)f(3)+\left(\genfrac{}{}{0ex}{}{4}{2}\right)f(2)-\left(\genfrac{}{}{0ex}{}{4}{1}\right)f(1)$
$=2916-4\cdot 192+6\cdot 2-0=2160$

ここで $f(4)=4\cdot 3^6=2916$、$f(3)=3\cdot 2^6=192$、$f(2)=2$、$f(1)=0$ である。

グループは区別しないので、色の入れ替え $4!=24$ で割って $2160/24=90$ 通り。

検算として、$n=3$、$k=2$ の場合を同じ方法で調べる。$f(2)-2f(1)=2$ を $2!$ で割って $1$ となる。これは $\{P_1,P_3\},\{P_2\}$ の1通りだけであり、実際と一致する。