場合の数・塗り分けの問題

質問

添付の地図に関する色の塗り分け問題がよくわからないため、考え方と式、答えを教えてください。
よろしくお願い致します。

問題：
添付の地図において、この地図を色分けする方法について考える。
ただし、隣り合う部分は異なる色を塗るものとする。

（１）異なる６色（赤、青、緑、黄、ピンク、オレンジ）をすべて使って、色分けする方法は何通りあるか。

（２）異なる６色（赤、青、緑、黄、ピンク、オレンジ）を使って、色分けする方法は何通りか。ただし、６色以下の色で塗り分けるものとする。

（３）異なる６色（赤、青、緑、黄、ピンク、オレンジ）から３色を選んで色分けする方法は何通りあるか。

（４）オレンジ以外の異なる５色（赤、青、緑、黄、ピンク）をすべて使って、色分けする方法は何通りか。
また異なる６色（赤、青、緑、黄、ピンク、オレンジ）から５色を選び、その５色すべてを使って色分けする方法は何通りあるか。

回答No.9

shuu_01

No.7 への補足の質問ありがとうございます

（２）、（３） について

＞　順番などに注意点などがあるのでしょうか？

注意点あります

（２） について、

　F→D→E→C→A→B　の順に考えるのは面倒です

　F→D→E→C→B→A であれば、OK です

　というのは、CD を決めた後、B を決め、A を決めるという
　順番だと、簡単に計算できますが、
　CD を決めた後、B より先に A を決めちゃうと、
　A と D が違う色だったら、B は 4通りですが、
　A と D が同じ色だったら、B は 3通りになり、
　簡単に計算できなくなるのです

（３） について

　D→E→C→F→A→B の順に考えると、間違えやすいです

　D→E→C→F→B→A の順であれば、

　6×5×4×2×1×1 ＝ 240 と正しい答えになります

　どこが問題かというと、CD が決まると、B が決まり、A も決まるのです

　CD の次に A を決めると、A は 2通り、選べそうな気がしますが、
　A に D と違う色を選んでしまうと、A C D が違う色で、３色使ってしまい、
　B に使う色がなくなってしまうのです

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

今回の僕の解き方は ad hoc ＝ その場、しのぎと言われたら、
まあ、仕方ないのですが、

もっと複雑な地図でも一般的に解ける方法でと言われると、
かなり面倒です