場合の数

問題を解いていて、わかなかったのですが、答えがなくどうしようも
ないのでどなたか模範解答をつくっていただけないでしょうか？

道路に正n角形のいっぺんが面している。正n角形の中心から各頂点をむすんでｎこの区画にわける。それぞれに３種類の花を埋める。このときそれぞれはとなりあってはいけないとする。このときなんととおりの埋め方があるか？

と言う問題です。
どなたかお願いいたします。

No.2 ベストアンサー 回答者： age_momo 回答日時： 2005/12/13 17:07

質問者さんの考えた事を書かないと削除対象になりますよ。

全く分からなかったという事は無いでしょう？
n=3やn=4の時に何通りになるか数えてみたりもしませんでしたか？

#1さんの言われるとおり、問題もあいまいですね。

1)道が一つあるので円順列のように回転して同じとは考えない。
2)それぞれの区画に3種類の花を一つずつ植える。
2)3種類の花は全ては使わなくてもよい。(nが偶数の時、2種類の交互もOK)

と言う前提でヒントを書きます。もっとスマートな求め方があるかも知れませんが。。。

n角形での埋め方の数をA(n)とします。
仮に道に面している区画から右回りで考えると、
最初は3通り、その隣は2通りそのまた隣も2通り・・・と考えていって
最後の区画も仮に2通りとすると
3*2^(n-1)
となります。ところがここには最初の区画と同じ色が入る場合もあります。
ここに最初と同じ色が入って後は全て隣に同じ色がこない場合の数は
最初の区画と最後の区画を一つと考えるとA(n-1)通りあることになります。
ということで漸化式

A(n)=3*2^(n-1)-A(n-1)

が得られます。後は考えてください。

この回答へのお礼

age_momoさん、どうもご丁寧な解説ありがとうございました。
2を累乗していくところまではわかったのですが、最後の一手をどうするかがわからず悩んでおりました。（そこがみそなのですが・・・）
問題文も不十分なここまで丁寧に考えて返信していただき、まことにありがとうございました。

お礼日時：2005/12/14 23:31

No.8 回答者： age_momo 回答日時： 2005/12/14 10:56

#2です。

#7さん、#6の式であってますよ。
同じ結論にたどり着いておられます。
私が示した式を変形してみます。

A(n)=3*2^(n-1)-A(n-1)・・・・(1)
A(n-1)=3*2^(n-2)-A(n-2)
2A(n-1)=3*2^(n-1)-2A(n-2)・・・・(2)

(1)-(2)で

A(n)-2A(n-1)=-A(n-1)+2A(n-2)
A(n)=A(n-1)+2A(n-2)
で同じ式になります。

ちなみに#4(#3)さんの式も

A(k+1)/6={2^(k-3)-a(k)/6}×2+a(k)/6
=2^(k-2)-A(k)/6
A(k+1)=6*2^(k-2)-A(k)=3*2^(k-1)-A(k)

で、ほぼ同じです。
なお、(1)式は書き下せば単純な級数で、高校の数学の知識で簡単に
一般化できます。質問者さんが出てこないので、この辺にしておきますが。

No.7 回答者： 16August 回答日時： 2005/12/14 09:12

Ｎｏ5,6ですがまだ違いますね。

　すみません。　もうちょっと考えてみます。

No.6 回答者： 16August 回答日時： 2005/12/14 09:10

No5ですが、後半の部分が間違いでした。

n-1番目の花の色を1番目の花の色と同じにできるのは、n-2番目の花の色が1番目の花の色と違う場合のみ、要するにA(n-2)ですから

A(n)=A(n-1)+2A(n-2)
(n>4),A(3)=6、A(4)=18

これをどう解くかは昔習ったような気もしますが、覚えていません。

この回答へのお礼

16Augustさんどうもありがとうございました。
他の方と違う解答で、また違った見方ができよかったです。
返事がおくれましたが、誠にありがとうございました。

お礼日時：2005/12/14 23:33

No.5 回答者： 16August 回答日時： 2005/12/13 18:58

A(n-1)通りの植え方があったらその最初と最後の花の色は違いますから、その間に植えられる色は1種類、

A(n-1)の最後の色を最初の花の色に変えて間に2種類の花を植えることができるから、

A(n) = A(n-1)*3

と考えたら間違えかな

No.4 回答者： peror 回答日時： 2005/12/13 17:31

　すみません、No.3です。

いくつか訂正します。
　花をABCの三種とし、道路に面した区画を1番とし、右周りに2,3,4, , ,n-1,n番とします。
　もし、１番にＡを植えると、2番はＢかＣの２通り、2番にＢを選べば、３番はＡかＣの２通り以下、２通りづつｎ-１番まで選べます。ｎ番は、Ａであってはいけません。
　仮に1番をＡ、2番をＢとし固定して考えます。
　n=3の時、3番は２の一乗通りありますが、Ａになるのが、１通りありますので、これを引きます。２^１-1。
　n=4の時、４番は2の２乗通りありますが、Ａになるのは、n=3の時にＡになって、不適になった部分を延長して考えると、３番がＡだと、４番はＢＣの２通り。n=3の時にＡになって不適だったのは、１通り、1×2＝2。n=3の時にＣになって、適した部分は、延長しても、４番はＡが選べないので、１通り。計３通り。
　n=5の時、同様に、n=4で適した数３に、適さなかった数、2^2-3=1の２倍、つまり、2通り。計５通り。
　n=kの時、ak通りだとすると、n=k+1は{2^(k-3)-ak}×２+ak 。
　で、１，２番の入れ替えが、６通りあるので、最後は６倍。
　漸化式以外の方法が思いつきません。
　

No.3 回答者： peror 回答日時： 2005/12/13 17:25

　花をABCの三種とし、道路に面した区画を1番とし、右周りに2,3,4, , ,n-1,n番とします。

　もし、１番にＡを植えると、2番はＢかＣの２通り、2番にＢを選べば、３番はＡかＣの２通り以下、２通りづつｎ-１番まで選べます。ｎ番は、Ａであってはいけません。
　仮に1番をＡ、2番をＢとし固定して考えます。
　n=3の時、3番は２の一乗通りありますが、Ａになるのが、１通りありますので、これを引きます。２^１-1。
　n=4の時、４番は2の２乗通りありますが、Ａになるのは、n=3の時にＡになって、不適になった部分を延長して考えると、３番がＡだと、４番はＢＣの２通り。n=3の時にＡになって不適だったのは、１通り、1×2＝2。n=3の時にＣになって、適した部分は、延長しても、４番はＡが選べないので、１通り。計３通り。
　n=5の時、同様に、n=4で適した数３に、適さなかった数、2^2-3=1の２倍、つまり、2通り。計５通り。
　n=k番目がak通りだとすると、n=k+1番目は{2^(k-3)-ak}×２+ak 。
　で、１，２番の入れ替えが、６通りあるので、最後は６倍。
　数列以外の方法が思いつきません。
　
　

No.1 回答者： oog-oog 回答日時： 2005/12/13 12:55

もう少し説明が足りないように思います。

道路に一辺が面しているとはどういう意味があるのですか。n個の区画に3種類ずつ花を埋めるのですか。隣り合ってはいけないとは何が隣り合ってはいけないのですか。