場合の数の問題です。

質問

図のような、ＡからＦまでの6区間に隣同士が異なる色を塗ります。
用意した色は全て使います。
6色を使った時、
5色を使った時、
4色を使った時、
それぞれ何通りあるか、答えを教えてください。

回答No.2

DJ-Potato · ベストアンサー

6色使った時は、6!ですね。

5色の時は、
AとDが同じ色の5!
AとEが同じ色の5!
AとFが同じ色の5!
BとE、BとF、CとFで
6×5!

4色の場合は
3箇所を同じ色にはできないので
AとD、BとEが同じ4!
AとD、BとFが同じ4!
AとD、CとFが同じ4!
AとE、BとFが同じ4!
AとE、CとFが同じ4!
AとF、BとEが同じ4!
BとE、CとFが同じ4!
の7×4!ですかね。

数え漏れはないでしょうか。

回答No.9

noname#215361

ANo.8の訂正です。

(1)の最後の行
誤：「単に6!=120通り」→正：「単に6!=720通り」

回答No.8

noname#215361

ANo.3の回答者です。
自分では完璧を期したつもりでしたが、やはり漏れがありました。
BとEの関係だけに傾注し過ぎて、AとDの関係及びAとEの関係を見落としていました。
ANo.3と一部重複するので、ANo.3は無視してください。

(1)6色を使った時
6区間に6色を使うので、
単に6!=120通り

(2)5色を使った時
「Aの色」と「Bの色」と「Cの色」の塗り分け方は、5*4*3=60通り
・「Dの色」=「Aの色」の場合
「Eの色」=「Bの色」とすると、FにA～Cと異なる色を塗っても4色しか使えないので不適
「Eの色」≠「Bの色」とすると、「Eの色」は2色、「Fの色」は残りの1色しか有り得ないので、
この場合は、60*2*1=120通り
・「Dの色」≠「Aの色」の場合
「Dの色」は、2色が有り得る
「Eの色」=「Aの色」とすると、「Fの色」は残りの1色しか有り得ないので、
この場合も、60*2*1=120通り
「Eの色」=「Bの色」とすると、「Fの色」は残りの1色しか有り得ないので、
この場合も、60*2*1=120通り
「Eの色」≠「Bの色」とすると、「Eの色」は残りの1色しか有り得ず、「Fの色」は3色が有り得るので、
この場合は、60*2*1*3=360通り
よって、5色を使った時は、120+120+120+360=720通り

(3)4色を使った時
「Aの色」と「Bの色」と「Cの色」の塗り分け方は、4*3*2=24通り
・「Dの色」=「Aの色」の場合
「Eの色」=「Bの色」とすると、「Fの色」は残りの1色しか有り得ないので、
この場合は、24*1=24通り
「Eの色」≠「Bの色」とすると、「Eの色」は残りの1色しか有り得ず、「Fの色」は2色が有り得るので、
この場合は、24*1*2=48通り
・「Dの色」≠「Aの色」の場合
「Dの色」は、残りの1色しか有り得ない
「Eの色」=「Aの色」とすると、「Fの色」は2色が有り得るので、
この場合も、24*1*2=48通り
「Eの色」=「Bの色」とすると、「Fの色」は2色が有り得るので、
この場合も、24*1*2=48通り
よって、4色を使った時は、24+48+48+48=168通り

お礼

何度もありがとうございましたm(_ _)m

回答No.7

yyssaa

回答No.4の「5色を使った時」と「4色を使った時」を
以下の通り訂正します。

5色を使った時
＞5色で6区間を塗るのだから2区間を同一色で塗ること
になり、その2区間の候補は(A,D)(A,E)(A,F)(B,E)(B,F)
(C,F)の6通りある。
同一色で塗る2区間を1区間と考えれば全部で5区間を5色
で塗ることになり、その塗り方は5!通り。
それが6通りあるので、全部で6*5!=6!=720通り・・・答

4色を使った時
＞4色で6区間を塗るのだから同一色で塗る2区間が2組
必要になる。(A,D)(A,E)(A,F)(B,E)(B,F)(C,F)の6通り
のうち区間が重複しない2区間の組は(A,D)と(B,E)、
(A,D)と(B,F)、(A,D)と(C,F)、(A,E)と(B,F)、
(A,E)と(C,F)、(A,F)と(B,E)、(B,E)と(C,F)の7通りある。
2区間の組2組をそれぞれ1区間と考えれば4区間を4色で
塗ることになり、その塗り方は4!通り。
それが7通りあるので、全部で7*4!=168通り・・・答

回答No.6

yyssaa

済みません。
回答No.4(5色、4色)は無視して下さい。

回答No.5

staratras

この問題は決して難問ではないと思いますが、5色・4色のときに数え間違いをしがちなので、下のようなグラフで考えるのも一法です。四色問題にならって、AからFまでの国の地図を塗り分けるものとします。

AからFまでの●は塗り分ける国を表し、２つの国が接している場合1本の線分で直接(黒色)つないでいます。例えばBから見ると、A,C,Dはつながっているので同じ色では塗れないことを示します。Bから見てEとFは直接はつながってないので同じ色で塗ることが可能です。(ただしEとFはつながっているので、どちらか一方だけです）

ここで、同じ色で塗れる組み合わせを赤い線分で結んでいます。AD,AE,AF,BE,BF,CFの６本(6通り)あります。また赤い線分が三角形を作っているところはないので、3か国を同じ色では塗れないことも明らかです。

まず6か国を6色で塗るときは、どの色でどこを塗っても構わないので、単純にA国6色、B国(A以外の)5色、C国(A、B以外の)4色…となり、
全体の組み合わせは、6!=720 通りです。

5色の場合、6か国のうちどれか2国を同じ色で塗らなければなりません、これは6通りあります。ここで同じ色で塗った2国を合併した一つの国と考えると、あとは5か国を5色で塗り分けることになりますので、5!=120通りです。したがって全体の組み合わせは、6×5!=720 通りです。

4色の場合、3か国を同じ色では塗れないので、同じ色で2か国を塗る組み合わせを2組作るしかありません。下の6本の赤い線分の中から、●を共有しない組み合わせは、（AD,BE)(AD,BF)(AD,CF)(AE,BF)(AE,CF)(AF,BE)(BE,CF)の7通りです。ここで同じ色で塗った2組の2か国をそれぞれ合併した一つずつの国と考えるとあとは4か国を4色で塗り分けることになりますので、4!=24通りです。したがって全体の組み合わせは、7×4!=168通りです。

お礼

図入りで丁寧にご回答いただき、ありがとうございましたm(_ _)m

回答No.4

yyssaa

6色を使った時、
＞Aに6色のうちのどれかを塗ると
BにはAに塗った色以外の5色のうちのどれかを塗り、
CにはAとBに塗った色以外の4色のうちのどれかを塗り、
DにはAとBとCに塗った色以外の3色のうちのどれかを塗り、
EにはAとBとCとDに塗った色以外の2色のうちのどれかを塗り、
Fには残った1色を塗ることになるので、塗り方は全部で
6*5*4*3*2*1=720通り・・・答
5色を使った時、
＞5色を全部使うのだから、
Aに5色のうちのどれかを塗ると
BにはAに塗った色以外の4色のうちのどれかを塗り、
CにはAとBに塗った色以外の3色のうちのどれかを塗り、
DにはAとBとCに塗った色以外の2色のうちのどれかを塗り、
Eには残った1色を塗り
FにはDとEに塗った色以外の3色のうちのどれかを塗ることに
なるので、塗り方は全部で
5*4*3*2*1*3=360通り・・・答
4色を使った時、
＞4色を全部使うのだから、
Aに4色のうちのどれかを塗ると
BにはAに塗った色以外の3色のうちのどれかを塗り、
CにはAとBに塗った色以外の2色のうちのどれかを塗り、
Dには残った1色を塗り
EにはCとDに塗った色以外の2色のうちのどれかを塗り、
FにはDとEに塗った色以外の2色のうちのどれかを塗ることに
なるので、塗り方は全部で
4*3*2*1*2*2=96通り・・・答

回答No.3

noname#215361

・6色を使った時
6!=720通り

・5色を使った時
Aに5通り、Bに4通り、Cに3通り、Dに2通り、E=Bの時Eに1通り、Fに1通りの場合は、
5*4*3*2*1*1=120通り
Aに5通り、Bに4通り、Cに3通り、Dに2通り、E≠Bの時Eに1通り、Fに3通りの場合は、
5*4*3*2*1*3=360通り
よって、答えは120+360=480通り

・4色を使った時
Aに4通り、Bに3通り、Cに2通り、Dに1通り、E=Bの時Eに1通り、Fに2通りの
4*3*2*1*1*2=48通り

回答No.1

mshr1962

6色を使った時、6×5×4×3×2×1=720通り　※6P6
5色を使った時、5×4×3×2×1=120通り　※AとFが同色で5通り、残り4色の組み合わせ4P4
4色を使った時、0通り　※BCDEで4色必要なので、AとFに付けられる色が無い