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

彩色への言い換え. $3$ つのブロックに色 $1,2,3$ を割り当てると、条件を満たす分割 $1$ つにつき、$\{1,\dots ,8\}$ から $\{1,2,3\}$ への写像 $c$ で
- 隣り合う整数は異なる色: $c(i)\ne c(i+1)$ $(1\le i\le 7)$
- $3$ 色すべてを使う（全射）

を満たすものがちょうど $3!=6$ 個対応する（ブロックが空でなく互いに異なるので、色の割り当て方は $6$ 通りで、どれも異なる写像になる）。

隣り合う色が異なる写像の個数. 使える色を $m$ 色とすると、$c(1)$ は $m$ 通り、$c(2),\dots ,c(8)$ はそれぞれ直前と異なる $m-1$ 通りなので $m(m-1{)}^7$ 個（道グラフ $P_8$ の彩色多項式）。

包除原理で全射に限る. $3$ 色のうち使わない色の集合で包除すると
$$3\cdot 2^7-\left(\genfrac{}{}{0ex}{}{3}{1}\right)\cdot (2\cdot 1^7)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot (1\cdot 0^7)=384-6+0=378.$$
（$3$ 色で $3\cdot 2^7$、特定の $1$ 色を使わない $2$ 色で $2\cdot 1^7=2$、$1$ 色だけでは $0$。）

分割の個数.
$$\frac{378}{3!}=63.$$

（別の見方: 一般に、このような $\{1,\dots ,n\}$ の $k$ ブロック分割の個数は第 $2$ 種スターリング数 $S(n-1,k-1)$ に等しく、$S(7,2)=2^6-1=63$ と一致する。）

答えは $63$ 通り。

各ブロックに別の色を対応させると、条件は「隣り合う整数 $i,i+1$ が異なる色」である 3 色による塗り方（全 3 色使用）に対応し、各分割はブロックの順序の分 $3!$ 通りの塗り方に対応する。8 個の路の 3 色の適切な塗り方は $3\cdot 2^7=384$。このうち 2 色以下しか使わないものは、2 色を選んで交互に塗る $3\times 2=6$ 通り（1 色のみは不可）。全 3 色を使うものは $384-6=378$。よって $378/3!=63$。検算: 一般に $S(n-1,k-1)$ に一致し、$S(7,2)=2^6-1=63$。