下図のA,\ B,\ C,\ D,\ Eの各領域を塗り分ける.\
隣り合った領域には異なる色を用いるとき, 次の塗り分け方は何通りか. \ [\,広島修道大\,]
(1)\ \ 5色全て用いる. \ \ (2)\ \ 4色全て用いる. \ \ (3)\ \ 3色全て用いる色の塗り分け（平面）}5!}=120\ (通り)}$
(2)\ \ AとE,\ BとC,\ CとEの3組のうち,\ どれか1組の領域を同じ色で塗る.}
同じ色を塗る領域の選び方は3通り,\ どの色を塗るかは4通りある.
残りの3ヶ所は3色で塗ればよいから $3!}=6\ (通り)$
∴ (3×4)×6}=72\ (通り)}$}
D}の塗り方は4通り,\ A,\ B}の塗り方は$P32=6$通りである.
残りの1色については,\ Cに塗る,\ Eに塗る,\ CとEに塗るの3通り}がある.
∴ 4×6×3}=72\ (通り)}$}
(3)\ \ AとE,\ BとCには,\ それぞれ同じ色を塗る}しかない.
(A,\ E),\ (B,\ C),\ Dの3領域を3色で塗ればよいから $3!}=6\ (通り)}$
{A}からアルファベット順に塗るとすると,\ A}の塗り方は5通りある.
\ \ その5通りのいずれに対してもBの塗り方は4通りある.}
\ \ よって,\ AとBの塗り方は} 5×4=20\ (通り) (積の法則)
\ \ 同様に考えると,\ 5つの領域の塗り方は\,5×4×3×2×1\,となる.
\ \ これは,\ 異なる5つのものを並べる順列の総数5!\,に等しい.
\ \ 色の塗り分け問題は,\ 必然的に順列の総数を求めることに帰着する.
\ \ P nr\,やn!\,については,\ 単に並べるときの場合の数という認識では不十分なのであった.
\ \ n!\,の本質は,\ 「異なるn個のものを他の異なるn個のものと1対1で対応させる」}である.
\ \ 本問の本質は5つの領域と5つの色の1対1対応}であるから,\ 順列に帰着するのも当然である.
(2)\ \ どこか2つの領域を同じ色で塗らなければならない.
\ \ 条件が厳しいこの2つの領域を先に塗る}と,\ 後の3つの領域については単純な順列である.
\ \ 隣り合う領域を異なる色で塗るとき,\ 最も隣接する領域が多い領域から塗る}発想も有効である.
\ \ 本問の場合,\ まず4つの領域と隣接している Dから塗る.
\ \ 次に,\ 3つの領域と隣接しているA,\ B}を,\ D以外の3色から2色選んで塗る.
\ \ 最後,\ 2つの領域と隣接しているCとE}の塗り方は,\ 以下の3通りに限られる.
\ \ (C,\ E)}=( Bと同じ色,\ 残りの1色),\ (残りの1色,\ Aと同じ色),\ (残りの1色,\ 残りの1色)
下図の各領域を次のように塗る方法は何通りあるか.
隣り合う領域には異なる色を塗り,\ 回転して同じ塗り方になるものを区別しない.
(1)\ \ 5色全て用いる. \ \ (2)\ \ 4色全て用いる. \ \ (3)\ \ 3色全て用いる. \\
(1)\ \ 中央部の塗り方は5通り,\ 残りは異なる4個のものの円順列}である.
∴ 5×(4-1)!}=30\ (通り)}$} \\
(2)\ \ 中央部の塗り方は4通りである.
外周は3色から1色選んで2ヶ所を同じ色で塗る}と後の2ヶ所の塗り方は1通り}である.
(3)\ \ 中央部の塗り方は3通り,\ 残りの2色での外周の塗り方は1通り}である.
(1)\ \ 特殊な領域を優先的に塗る.}\ 隣接する領域が多いことから見ても中央を先に塗るべきである.
\ \ 外周の4つの領域は対等で回転して一致するものは区別しないから,\ 円順列の扱いとなる.
(2)\ \ 中央を塗った後,\ 同じ色となる2ヶ所(対面)を先に塗る.}
\ \ 図の2つの塗り方は回転すると一致するから,\ 同じ塗り方であることに注意する.
右図の9つの正方形を3色で塗るとき,\ 次の塗り方は何通りあるか.
特に断りがない限り,\ 隣り合う領域を同じ色で塗ってもよい.
(1)\ \ すべての塗り方.
(2)\ \ どの色も3つの正方形を塗る.
(3)\ \ どの横の列も3色で塗る.
(4)\ \ どの縦の列もどの横の列も3色で塗る.
(5)\ \ 回転して同じ塗り方になるものを区別しない. \\[-11zh]
1つの正方形につき3通りの塗り方がある}から $3^9}=19683\ (通り)}$
(2)\ \ 1つの色につきその色で塗る正方形3つを選べばよい}から\ \ $C93×C63}=1680\ (通り)}$
(3)\ \ 上段,\ 中段,\ 下段をそれぞれ3色で塗ればよい}から $3!×3!×3!}=216\ (通り)}$
(4)\ \ 上段を3色で塗ると他の段の塗り方は2通りになる}から $3!×2}=12\ (通り)}$
(5)\ \ $90°$回転して元の塗り方と一致する塗り方}は $3^3}=27\ (通り)$
$180°$回転して\.{初}\.{め}\.{て}元の塗り方と一致する塗り方}は $3^5-3^3}=216\ (通り)$
∴ 求める場合の数は 19683-27}-216{4+216{2+27}=4995\ (通り)}$}
(1)\ \ 9つの正方形それぞれに重複を許して3色を対応させればよく,\ 重複順列}に帰着する.
(2)\ \ 各色に着目して考えると,\ 組合せ}に帰着する.
\ \ あるいは,\ 同じものを含む順列}の扱いで求めることもできる.
\ \ 一旦,\ 9つの正方形を異なる色で塗ると考える(9!\,通り).
\ \ 実際には同じ色の正方形が3個ずつあるから,\ 重複度で割ると\,9!}{3!3!3!}=1680\ (通り)\ となる.
(3)\ \ 縦は影響しないから横だけを考えて重複を許さずに3色を対応させればよく,\ 順列}に帰着する.
(4)\ \ 縦と横の両方の考慮が必要で,\ 一見かなり難しく感じる.\ 初見では諦める人も多いだろう.
\ \ ここですぐに諦めるかとりあえず手を動すかの姿勢の違いが,\ 最終的な合否にまで影響する.
\ \ 条件が複雑になるほど塗り方が限られ,\ しらみつぶしできる可能性が高まる.}
\ \ 本問も,\ 上段の色が決まれば,\ それに対応した中段と下段の塗り方は2通りしかない}とわかる.
\ \ 実際に書き出してみることで初めて気付くことができるわけである.
(5)\ \ 本質的には,\ 同じものを含む円順列}(やや難)と同じ問題構造である.
\ \ 同じものを含む円順列を未学習でも,\ 以下の説明で理解できるだろう.
\ \ 例えば,\ (1)の19683通りに含まれる次の4つの塗り方は,\ (5)では1通りの扱いになる. \\[.2zh
\ \ ただし,\ 安易に19683÷4を計算しても求まらない(そもそも割り切れない).
\ \ (1)の塗り方のすべてが(5)と4:1で対応するわけではない}からである.
\ \ 具体的には,\ 回転対称性がある塗り方}のとき,\ 対応が4:1ではなくなる.
\ \ 実際,\ 90°\,回転して元の塗り方と一致する塗り方の場合,\ (1)と(5)は1:1で対応する(左下図).
\ \ また,\ 180°\,回転して元の塗り方と一致する塗り方の場合,\ (1)と(5)は2:1で対応する(右下図).
\ \ 以上を踏まえて(5)の場合の数を求めよう.\ まず,\ 回転対称性をもつ塗り方の総数を求める.
\ \ 90°\,の回転対称性をもつのは,\ 左下図のような塗り方の場合である.
\ \ ＊,\ ○,\ ■\ の色をそれぞれ決めればよく,\ 3通りずつあるから3^3\,通りである.
\ \ 180°\,の回転対称性をもつ塗り方は右下図の\,＊,\ ○,\ ■,\ ▲,\ ▽\,の色を決めればよく,\ 3^5\,通りある.
\ \ 注意すべきは,\ 3^5\,通りの中には90°\,の回転対称性をもつ塗り方3^3\,通りも含まれる}ことである.
\ \ 180°\,回転して\dot{初}\dot{め}\dot{て}一致する塗り方を求めることにより,\ ダブルカウントを防ぐ}ことができる. 結局,\ (回転対称性がない塗り方)}{4}+(180°\,対称の塗り方)}{2}+(90°\,対称の塗り方)}\ となる.
