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

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


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

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

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

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

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

No.11 回答者： stomachman 回答日時： 2014/02/13 02:17

ANo.10訂正。

A=DかつB≠Cの場合も2400通りっすね。寝ぼけてます。

No.10 回答者： stomachman 回答日時： 2014/02/13 02:11

ANo.3のstomachmanです。

　以下、頂点A,B,C,…の色もA,B,C,…と書くことにします。

（２）のコタエが9600通りってのは、「A≠DかつB≠C」の場合(Fig2)しか数えていないんでは？問題はFig1のグラフの色分けなんで、Fig2以外の
A=DかつB≠Cの場合(Fig3) 3000通り
A≠DかつB=Cの場合(Fig4) 2400通り
A=DかつB=Cの場合(Fig5) 600通り
が抜けてるような気がしますけど、私の勘違いかな？

ANo.3へのコメントについて。

> どこのアルファベットから考え、どのように次のアルファベットを考えていくなど
> ルールはあるのでしょうか？

　そんなのありませんが、上記ように分類したとき、C,D,E,Fはどの場合も同じことになり、A, Bの扱いは場合による。だから、C,D,E,Fの部分から考えるのがカンタンでしょうね。

No.9 回答者： shuu_01 回答日時： 2014/01/27 10:53

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 ＝ その場、しのぎと言われたら、
まあ、仕方ないのですが、

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

No.8 回答者： ask-it-aurora 回答日時： 2014/01/25 21:32

<回答No.4補足

「式の意味がわからない」というのは具体的にどこかを指摘してもらわなければ的確な返事はできませんが，質問者のレベルが最初の問題文だけからよりはわかったので，もうすこしだけ．

一言で言うと回答No.4の解法は忘れていただいて結構です．回答No.7の解法が理解できれば，ひとまずOKでしょう．ただし，その回答者がしたように数え漏らしなどをしやすいし，間違えたときに気がつき難いので細心の注意を要します．

（この解法の差は例えるならば鶴亀算を使うのと未知数xを使うのとの違いのようなものです．前者の方が少ない知識で済みますが，式の意味や理屈をよく考えないといけません．後者は何に名前をつけ，どう方程式をたてるのかが，難しくなりますが，その後は機械的に式変形をしていくだけで問題が解けます．）

No.7 回答者： shuu_01 回答日時： 2014/01/23 11:55

No.1 ですが、その後、２ヶ所 間違いがあり、訂正し、

また、「Cから考えると、違う場合が出てしまった」
との補足があり、C から考えた場合も追加しました

「ad hoc」 ではなく 「統一的」 に計算できた方が良いのですが、
まだ、グラフの彩色問題を理解できていないので、
僕にはこれしかできませんでした

――――――――――――――――――――――――—

（１） A は ６通り、B は残り ５通り、C は ４通り、、、ですので、６！＝ 720通り

（２） A は６通り、B は残り ５通り、C は残り ４通り、
　　　D は BC 以外の ４通り、E は CD 以外の ４通り、F は D以外の ５通り
　　　６×５×４×４×４×５ ＝ 9600通り

（２’） C から始めても
　　　C は ６通り、Ａ　は残り ５通り、Ｂ は残り ４通り、
　　（あるいは 　C は ６通り、B　は残り ５通り、A は残り ４通り、）
　　　D は BC 以外の ４通り、E は CD 以外の ４通り、F は D以外の ５通り
　　　６×５×４×４×４×５ ＝ 9600通り
　　とほぼ同じです

（３） A は ６通り、B は ５通り、C は ４通り、
　　　ここでもう３色を選んでいるので、D は１通り、E も１通り、F は D以外の２通り
　　　６×５×４×２＝240通り

（３’） C から始めても
　　　C は ６通り、A は ５通り、B は ４通り、
　　（あるいは C は ６通り、B は ５通り、A は ４通り、）
　　　ここでもう３色を選んでいるので、D は１通り、E も１通り、F は D以外の２通り
　　　６×５×４×２＝240通り

（４ー１） A～F ６区画あるのに、オレンジ以外の５色しか
　　　使わないということは、
　　　どれか ２区画を同じ色に塗るということ、
　　　その組み合わせは A＝D、A＝E、A＝F、B＝E、B＝F、C＝F 、Ｅ＝Ｆ
　　　の７通りあります
　　　その各々について、
　　　色の塗り方は ５×４×３×２×１＝ 120通りあるので
　　　全部で 7 × 120 ＝ 840通り

（４ー２） 異なる６色（赤、青、緑、黄、ピンク、オレンジ）
　　　から５色を選ぶということは、使わない１色を選ぶという
　　　ことで、６通りあり、
　　　（４ー１） の ６倍
　　　840 × 6 ＝ 5040

【答え】
（１）　　　　720通り
（２）　　　9600通り
（３）　　　　240通り
（４ー１）　　840通り
（４－２）　5040通り

この回答への補足

私の疑問にも対応いただきありがとうございます。
さらに質問をする形で申し訳ないのですが、気になるところがあるので質問させてください。

(2)ですが、
たとえば、F→D→E→C→A→Bの順番に考えると、
6→5→5→4→5→3となり、答えは9000通り
同様に、D→F→E→C→A→Bの順に考えると、
6→5→5→4→5→3となり、答えは9000通りになります。
考え方はとてもよくわかり使っていきたいと思うのですが、
順番などに注意点などがあるのでしょうか？

また、(3)ですが、
D→E→Cの順番に考えると、
6→5→4となり、FはCかEと同じ色、またAについてもDかEと同じ色が選べるので、
6×5×4×2×2×1となり、480通りになるように思います。

補足日時：2014/01/27 09:25

No.6 回答者： shuu_01 回答日時： 2014/01/23 10:36

＞　他の方のコメントも参考にさせて頂くと、

＞　アルファベットを頂点と考えるやり方でしょうか？

図をパット見て、Ａ以外でも行けそうな気がしたの
ですが、試していません

Ａ以外を選ぶと、「なんで Ａ から始めないの？」と
質問されそうで、Ａ からやってました

Ａからだと、やりやすそうでしたし

C からはやってませんが、そのうち、時間があったら
トライしてみます

No.5 回答者： shuu_01 回答日時： 2014/01/23 10:32

No.1、No.2 です

No.4 さん、僕の回答（４）間違ってました
ご指摘の通り、EFの組合せを数え漏らしていました

そこを訂正すると、


（４ー１） A～F ６区画あるのに、オレンジ以外の５色しか
　　　使わないということは、
　　　どれか ２区画を同じ色に塗るということ、
　　　その組み合わせは A＝D、A＝E、A＝F、B＝E、B＝F、C＝F 、Ｅ＝Ｆ
　　　の７通りあります
　　　その各々について、
　　　色の塗り方は ５×４×３×２×１＝ 120通りあるので
　　　全部で 7 × 120 ＝ 840通り

（４ー２） 異なる６色（赤、青、緑、黄、ピンク、オレンジ）
　　　から５色を選ぶということは、使わない１色を選ぶという
　　　ことで、６通りあり、
　　　（４ー１） の ６倍
　　　840 × 6 ＝ 5040

と No.4 さんの回答と同じになりました

僕はこの塗り分けの問題は初めて解き、また、
グラフの彩色問題というのも初めて聞き、
正直、No.4 さんの回答を理解しきれていません

「統一的に」考えられれば、それが最高なのですが、
他のもと複雑な地図、グラフにどう応用できるのか
想像だにできません

いつか時間を見つけて、グラフの彩色問題を勉強
したいです

No.4 回答者： ask-it-aurora 回答日時： 2014/01/21 16:34

stomachmanさんが述べているように対応するグラフを考えた方がスッキリします．地図の地域に対応する点を小文字で表すことにすると，次のグラフの彩色問題に帰着されます．

a - c - e
| / | /
b - d - f
また答えはほぼshuu_01さんが与えていますが，次の多項式を考えるとより統一的に解けます．

p(k) : グラフを隣接する点の色が異なるようにk色以下で塗り分ける方法の数（彩色多項式）
q(k) : グラフを隣接する点の色が異なるようにk色ちょうどで塗り分ける方法の数

k色ちょうどで塗り分け方はk色以下の塗り分け方からk色未満の塗り分け方を除いたものなので関係式
q(k) = p(k) - kC1 * q(1) - kC2 * q(2) - … - kC(k - 1) * q(k - 1)
が成り立ちます．

(1) 6点を6色すべてで塗り分けるので，この方法は6! = 720通りです．

(2) 回答No.1(2)と同様に考えるとp(k) = k(k - 1)^2(k - 2)^3 (k ≧ 3)とわかります．よってこの方法はp(6) = 9600通りです．

(3) 問題文通りに計算すれば，この方法は6C3 * p(3) = 240通りです．

(4-i) p(k)を考えるとグラフは3色未満では塗り分けられないのでp(k) = q(k) = 0 (k < 3)です．よって関係式からこの方法は
q(5) = p(5) - 5C4 * q(4) - 5C3 * q(3)
= p(5) - 5p(4) + 10p(3) = 840通りです．
## 回答No.1はEFの組合せを数え漏らしています．ad hocな解法の危うさですね．

(4-ii) 問題文通りに計算すれば，この方法は6C5*q(5) = 6*840 = 5040通りです．

この回答への補足

コメント頂きありがとうございます。
勉強不足もあり、彩色多項式という言葉を初めて知りました。
中学レベルに少し毛が生えた程度の学力で、ご丁寧に説明頂いたのですが
式の意味がよく理解できません・・・。
私のレベルでもわかるように少しアドバイスも頂ければ助かります。
よろしくお願い致します。

補足日時：2014/01/22 23:09

No.3 回答者： stomachman 回答日時： 2014/01/21 14:52

計算はさておきです。

地図に書いてある記号(A, B, C..)を「頂点」だと思って、隣接している部分の頂点同士を線で結ぶと、ひとつのグラフができます。地図に書き込んでみて下さい。すると、「塗り分ける」とは、「線で結ばれた頂点同士は互いに異なる色にしなくちゃいけない」ということと同じ意味です。グラフにしてみるととても分かり易くなるんです。たとえば問題(3)がどうしてそういう計算になるのか、ということも、このグラフを見れば理解し易いでしょう。

この回答への補足

コメントありがとうございます。
後の方の説明を見て、おっしゃられている解法の素晴らしさが少しわかりました。
（２）の問題ですが、こちらの開放を使って考えたのですが、
どこのアルファベットから考え、どのように次のアルファベットを考えていくなど
ルールはあるのでしょうか？教えて頂いた答えと同じになる時と
違う値になる時があり、考え方がまだまだ理解できていないようなのでアドバイス頂ければ幸いです。

補足日時：2014/01/22 23:15

No.2 回答者： shuu_01 回答日時： 2014/01/21 01:21

単純な計算ミスあり、訂正します

（３） A は ６通り、B は ５通り、C は ４通り、
　　　ここでもう３色を選んでいるので、D は１通り、E も１通り、F は D以外の２通り
　　　６×５×４×２＝122通り

　　　　　　　　　　　　　　　　↓

（３） A は ６通り、B は ５通り、C は ４通り、
　　　ここでもう３色を選んでいるので、D は１通り、E も１通り、F は D以外の２通り
　　　６×５×４×２＝240通り