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

まず三角形 $abc$ を塗る。3 頂点は互いに隣接するので、塗り方は $k(k-1)(k-2)$ 通りである（$k\le 2$ のときはこの値が 0 になり、正しく 0 通りを表す）。

$a,b,c$ の色をそれぞれ $\alpha ,\beta ,\gamma$（互いに異なる）として固定し、$a^{\prime },b^{\prime },c^{\prime }$ の色 $(x,y,z)$ の選び方を数える。条件は
- $x,y,z$ が互いに異なる（三角形 $a^{\prime }{b}^{\prime }{c}^{\prime }$）
- $x\ne \alpha ,y\ne \beta ,z\ne \gamma$（辺 $a{a}^{\prime },b{b}^{\prime },c{c}^{\prime }$）
である。互いに異なる $(x,y,z)$ 全体を全体集合とし、$E_1:x=\alpha$, $E_2:y=\beta$, $E_3:z=\gamma$ として包除原理を使う。
- 全体: $k(k-1)(k-2)$
- $|E_1|$: $x=\alpha$ と決まり、$y,z$ は $\alpha$ と異なり互いに異なるので $(k-1)(k-2)$。$E_2,E_3$ も同様。
- $|E_1\cap E_2|$: $x=\alpha ,y=\beta$（$\alpha \ne \beta$ なので矛盾はない）、$z$ は $\alpha ,\beta$ と異なるので $k-2$。ほかの 2 組も同様。
- $|E_1\cap E_2\cap E_3|=1$

よって、条件を満たす $(x,y,z)$ の個数 $N(k)$ は
$$N(k)=k(k-1)(k-2)-3(k-1)(k-2)+3(k-2)-1=(k-1)(k-2)(k-3)+3k-7.$$
展開すると $(k-1)(k-2)(k-3)=k^3-6k^2+11k-6$ なので
$$N(k)=k^3-6k^2+14k-13.$$
$N(k)$ は $\alpha ,\beta ,\gamma$ の具体的な値によらないので
$$P_G(k)=k(k-1)(k-2)(k^3-6k^2+14k-13).$$

確認: $k=3$ のとき $N(3)=27-54+42-13=2$ で、これは 3 文字の攪乱順列の個数 2 に一致し、$P_G(3)=6\cdot 2=12$。また $P_G(k)$ を展開すると $k^6-9k^5+34k^4-\cdots$ となり、$k^5$ の係数 $-9$ は辺の数に、$k^4$ の係数 $34=\left(\genfrac{}{}{0ex}{}{9}{2}\right)-2$ は（辺の組の数）$-$（三角形の数）に一致する。

三角形 $abc$ の彩色は $k(k-1)(k-2)$ 通り。その色を $a=1,b=2,c=3$ とする。$a^{\prime }{b}^{\prime }{c}^{\prime }$ は三角形なので 3 色は相異なり、さらに $a^{\prime }\ne 1,b^{\prime }\ne 2,c^{\prime }\ne 3$ が必要。包除原理で、$a^{\prime }{b}^{\prime }{c}^{\prime }$ の彩色総数 $k(k-1)(k-2)$ から、$a^{\prime }=1$ など 1 条件違反が各 $(k-1)(k-2)$、2 条件違反が各 $k-2$、3 条件違反が $1$ なので $k(k-1)(k-2)-3(k-1)(k-2)+3(k-2)-1=(k-2)(k^2-4k+6)-1=k^3-6k^2+14k-13$。よって $P_G(k)=k(k-1)(k-2)(k^3-6k^2+14k-13)$。検算: $k=3$ で $6\cdot (27-54+42-13)=6\cdot 2=12$。これは上の三角形の 6 通りの彩色に対し下の三角形が完全順列 2 通りであることと一致する。