順列・円順列
順列・円順列
問題≪正多面体の面の塗り分け≫
-
$n$ 色を使って, 正 $n$ 面体の各面に互いに異なる色を塗る.
- (1)
- 次の各場合に, 色の塗り方は何通りあるか.
正 $n$ 面体の面の数 $n$ と, $1$ つの頂点で交わる辺の本数 $m,$ 頂点の個数 $v$ を用いて表せ.
- (i)
- すべての頂点を固定する場合.
- (ii)
- $1$ つの頂点を固定する場合.
- (iii)
- どの頂点も固定しない場合.
- (2)
- $n = 4,$ $6,$ $8,$ $12,$ $20$ の各場合に, 色の塗り方の総数を求めよ.
解答例
- (1)
-
- (i)
- すべての頂点を固定するとき, 色の塗り方は $n$ 個から $n$ 個をとる順列の総数に等しく, $n!$ 通り.
- (ii)
- $1$ つの頂点 $\mathrm A$ を固定するとき, $\mathrm A$ と正 $n$ 面体の中心を通る直線のまわりの回転移動で (1) の $m$ 通りの色の塗り方がそれぞれ同一視されるから, $\dfrac{n!}{m}$ 通り.
- (iii)
- どの頂点も固定しないとき, 任意の頂点を頂点 $\mathrm A$ の位置に移す移動で (2) の $v$ 通りの色の塗り方がそれぞれ同一視されるから, $\dfrac{n!}{m}\div v = \dfrac{n!}{mv}$ 通り.
- (2)
- 正 $n$ 面体の $1$ つの頂点で交わる辺の本数 $m,$ 頂点の個数 $v$ は次のようになる.
よって, (1) の (iii) の結果から, 求める場合の数はそれぞれ \begin{align*} \frac{4!}{3\cdot 4} &= 2, \\ \frac{6!}{3\cdot 8} &= 30, \\ \frac{8!}{4\cdot 6} &= 1\,680, \\ \frac{12!}{3\cdot 20} &= 7\,983\,360, \\ \frac{20!}{5\cdot 12} &= 40\,548\,366\,802\,944\,000 \end{align*} である.
$n$ $m$ $v$ $4$ $3$ $4$ $6$ $3$ $8$ $8$ $4$ $6$ $12$ $3$ $20$ $20$ $5$ $12$
背景
隣り合う領域には互いに異なる色を塗るという条件のもとで, 平面, 球面上の地図は, $4$ 色で塗り分けられることが知られている(「四色定理」).
球面への投影を考えればすぐわかるように, 穴の開いていないすべての多面体は $4$ 色で塗り分けられる.
塗り分けに必要な色の数の最小値は, 正四面体では $4,$ 正六面体では $3,$ 正八面体では $2,$ 正十二面体では $4,$ 正二十面体では $3$ である.