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

$A=\{a_1,a_2,a_3\}$, $B=\{b_1,\dots ,b_n\}$ とおく。$B$ の頂点どうしは辺で結ばれておらず、各 $b_j$ は $a_1,a_2,a_3$ のすべてと隣接している。したがって、$A$ の塗り方を先に決めると、各 $b_j$ は「$A$ に使われた色以外」の色から独立に選べる。$A$ に使われた色の種類数を $s$ とすると、$B$ の塗り方は $(k-s{)}^n$ 通りである。

$A$ の中で辺があるのは $a_1{a}_2$ だけなので、$a_1$ と $a_2$ は異なる色でなければならない。$a_1,a_2$ の塗り方は $k(k-1)$ 通り。$a_3$ は $a_1,a_2$ と隣接していないので自由に塗れるが、次の 2 つの場合に分ける。

(1) $a_3$ が $a_1$ または $a_2$ と同じ色のとき：$a_3$ の色は 2 通りで、$A$ に使われた色は 2 種類（$s=2$）。よって塗り方は
$$k(k-1)\cdot 2\cdot (k-2{)}^n=2k(k-1)(k-2{)}^n.$$

(2) $a_3$ が $a_1,a_2$ のどちらとも異なる色のとき：$a_3$ の色は $k-2$ 通りで、$A$ に使われた色は 3 種類（$s=3$）。よって塗り方は
$$k(k-1)(k-2)\cdot (k-3{)}^n.$$

(1), (2) は重複せず、すべての場合を尽くすので
$$P(G,k)=2k(k-1)(k-2{)}^n+k(k-1)(k-2)(k-3{)}^n.$$

（確認）$n=1$ のとき、$G$ は三角形 $a_1{a}_2{b}_1$ に頂点 $a_3$ を $b_1$ にだけつないだグラフなので、$P(G,k)=k(k-1)(k-2)\cdot (k-1)$ である。上の式に $n=1$ を代入すると $k(k-1)(k-2)\{2+(k-3)\}=k(k-1{)}^2(k-2)$ となり一致する。また $k\le 2$ では $G$ が三角形を含むので $0$ になることも式から確かめられる。

$a_1,a_2,a_3$ の塗り方を先に決め、各 $b_j$ の塗り方を数える。各 $b_j$ は $a_1,a_2,a_3$ のすべてと隣り合い、$b_j$ どうしは隣り合わない。したがって $a_1,a_2,a_3$ に使われた異なる色の数が $m$ のとき、各 $b_j$ の塗り方は $k-m$ 通りで、互いに独立に選べる。

$a_1,a_2$ は隣り合うので、塗り方は $k(k-1)$ 通り。$a_3$ は $a_1,a_2$ と隣り合わない。
- $a_3$ が $a_1$ または $a_2$ と同じ色の場合: 2 通り。使われる色は 2 種類なので、$b$ の塗り方は $(k-2{)}^n$ 通り。
- $a_3$ が $a_1,a_2$ のどちらとも異なる色の場合: $k-2$ 通り。使われる色は 3 種類なので、$b$ の塗り方は $(k-3{)}^n$ 通り。

よって
$$P(G,k)=k(k-1)\left[2(k-2{)}^n+(k-2)(k-3{)}^n\right].$$

検算: $n=1$ のとき、$G$ は三角形 $a_1{a}_2{b}_1$ の頂点 $b_1$ に $a_3$ が辺でつながったグラフである。この彩色多項式は $k(k-1)(k-2)(k-1)$。公式に代入すると $k(k-1)[2(k-2)+(k-2)(k-3)]=k(k-1)(k-2)(k-1)$ となり一致する。