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

正の整数 $n,k$ に対し、$\{1,\dots ,n\}$ を $k$ 個のブロックに分ける方法で、連続する 2 整数を同じブロックに含まないものの個数を $f(n,k)$ とする。また $S(n,k)$ を第 2 種スターリング数とする（$S(0,0)=1$）。

漸化式. $n\ge 2$ とし、条件を満たす $\{1,\dots ,n\}$ の分割から $n$ を取り除くことを考える。
- $n$ が単独のブロック $\{n\}$ をなすとき、残りは $\{1,\dots ,n-1\}$ の条件を満たす $k-1$ ブロックの分割で、$f(n-1,k-1)$ 通り。
- $n$ がほかの要素と同じブロックにあるとき、$n$ を除くと $\{1,\dots ,n-1\}$ の条件を満たす $k$ ブロックの分割が得られる。逆にそのような分割に $n$ を加えるには、$n-1$ を含むブロック以外の $k-1$ 個のブロックのどれかに入れればよい。よって $(k-1)f(n-1,k)$ 通り。

したがって
$$f(n,k)=(k-1)f(n-1,k)+f(n-1,k-1)(n\ge 2),f(1,1)=1,f(1,k)=0(k\ge 2).$$

スターリング数との関係. $g(n,k)=S(n-1,k-1)$ とおくと、スターリング数の漸化式 $S(m,j)=jS(m-1,j)+S(m-1,j-1)$ で $m=n-1,j=k-1$ とすれば
$$g(n,k)=(k-1)g(n-1,k)+g(n-1,k-1)$$
となり、$g(1,1)=S(0,0)=1$、$g(1,k)=S(0,k-1)=0(k\ge 2)$ である。漸化式と初期値が一致するので $f(n,k)=S(n-1,k-1)$。

計算. 求める値は $f(8,4)=S(7,3)$。全射の個数を包除原理で数えると、7 元集合から 3 元集合への全射は $3^7-3\cdot 2^7+3\cdot 1^7=2187-384+3=1806$ 個であり、ブロックの順序を区別しないので $3!=6$ で割って
$$S(7,3)=\frac{1806}{6}=301.$$

確認: $f(3,2)=S(2,1)=1$ であり、実際 $\{1,2,3\}$ の 2 ブロック分割で条件を満たすのは $\{1,3\},\{2\}$ のみである。

各ブロックに別の色を対応させると、隣り合う整数が異なる色となる 4 色による 8 個の路の塗り方で、4 色すべてを使うものに対応し、各分割は $4!$ 通りの塗り方に対応する。ちょうど $j$ 色以下で塗る適切な塗り方は $j(j-1{)}^7$ なので、4 色すべて使うものは包除原理により $4\cdot 3^7-\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 3\cdot 2^7+\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 2\cdot 1^7-0=8748-1536+12=7224$。よって $7224/24=301$。検算: 一般に $S(7,3)=301$ に一致する。