どこが間違っているのでしょうか？

「A,B,Cの３種類の文字から重複をゆるして６個とり、その６個をAとBがとなりあわないように横一列に並べる。何通りの並べ方があるか答えよ。」という問題です。

解答では問題文を「A,B,Cの３種類の文字から重複をゆるしてn個とり、その６個をAとBがとなりあわないように横一列に並べる。」のように言い換えて、漸化式を立てています。漸化式はa[n+1]=x[n+1]+y[n+1]+z[n+1]・・・(1) とおいています。（x[n+1],y[n+1],z[n+1]はそれぞれA,B,Cが先頭にきたときの並べ方です。）そこからさらにx[n+1],y[n+1],z[n+1]をx[n],y[n],z[n],a[n]などで表して最初のa[n+1]=x[n+1]+y[n+1]+z[n+1] ・・・(1)の式に代入するときれいにx[n+1],y[n+1],z[n+1]が消えます。そうするとフィボナッチの数列があらわれて、あとはa[1]とa[2]からa[6]を求めれば終わりです。今回の質問内容とあまり関係がないので詳しいところは省略します。

それ対して私は全ての場合の数である3^6から「AとBがとなりあうように横一列に並べる通り」を引けば良いと考えました。そこで、「AとBがとなりあうように横一列に並べる通り」なんですが、６この場所から２つ選んで並べるとおりの6P2=30,残りの４個の場所はA,B,Cのどれでもいいから3^4=81,それらを掛けると、30・81=2430通りとなるんですが、全ての場合の数である3^6は729通りとなり、求める答えは729-2430=-1701通りとなってマイナスがついているので明らかに間違いだと言うことがわかるのですが、どこが間違っているのかわかりません。ちなみに答えは239通りです。よろしくお願いします。

No.4 ベストアンサー 回答者： kony0 回答日時： 2002/04/24 20:19

1. 6P2だと、rei00さんのおっしゃるとおり、AとBがとなりあわないものも含みます。

2. 6P2の中の別な２通り、「ＡＢ○○○○」と「○ＢＡ○○○」を考えて、どちらの場合も残りの４箇所には全部Ａが入る並べ方（3^4=81通りの中の１通り）を考えると、どちらも「ＡＢＡＡＡＡ」となり、同じものを重複して数えていることになります。

ちなみに、漸化式的な考え方は、決して難しいものではなくて、実は一番基本の、「なんか難しそうだから樹形図でも書いて考えようか」と思い立てば、漸化式的な考え方は自然と出てくると思います。

n文字並べて、末尾がA,B,Cである並べ方をそれぞれa[n],b[n],c[n]とする。
a[n+1]=a[n]+c[n], b[n+1]=b[n]+c[n], c[n+1]=a[n]+b[n]+c[n]
あぁ確かにフィボナッチ数列になりますね。。。でもそこは若干技巧的な気はしますが、a[6]+b[6]+c[6]を求めればよいわけですから、力ずくで代入しても求められると思います。

この回答へのお礼

＞2. 6P2の中の別な２通り、「ＡＢ○○○○」と「○ＢＡ○○○」を考えて、どちらの場合も残りの４箇所には全部Ａが入る並べ方（3^4=81通りの中の１通り）を考えると、どちらも「ＡＢＡＡＡＡ」となり、同じものを重複して数えていることになります。

あっ今やっとどこが重複していたのかわかりました！う～んやはり乱暴に考えてはダメなんですね。どっかでほころびが出てきてしまいます。

＞ちなみに、漸化式的な考え方は、決して難しいものではなくて、実は一番基本の、「なんか難しそうだから樹形図でも書いて考えようか」と思い立てば、漸化式的な考え方は自然と出てくると思います。

そうですか、私にはちょっと思いつかなかったです。n個の並べ方ではなく6個の並べ方であるのにとらわれたような気がします。n個の並べ方ならすぐに漸化式を立てようと思いますけど。でも「樹形図でも書いて考えようか」と思い立てば思いつくかもしれませんね。その場合の樹形図の書き方にも寄りますが。

kony0さんどうもありがとうございました！！

お礼日時：2002/04/26 00:27

No.6 回答者： rei00 回答日時： 2002/04/26 08:44

rei00 です。

お礼拝見しました。

失礼しました。

>> 残りの４個の場所はA,B,Cのどれでもいいから3^4=81
> これには「○ Ｂ Ａ Ｂ ○ ○」や「○ ○ Ａ Ｂ Ａ ○」の様な場合も
> 含まれていると思いますが・・・。
の部分は私の考え違いです。この部分が問題なのは kony0 さんがお書きの様に重複が生じるからですね。

　「アドバイス」にチェックしますが，これは「お詫び」ですね。どうもスミマセンでした。この内容に関しては「自信あり」です。

この回答へのお礼

わざわざ再度お返事くださってどうもありがとうございます。おかげで少し引っかかっていたところがすっきりして良かったです。「お詫び」なんてとんでもないです。またなにかあったらよろしくお願いします。

お礼日時：2002/04/26 18:08

No.5 回答者： good777 回答日時： 2002/04/25 01:00

「うまい方法はないかなあ」と「めんどうだあ」と考えながら取り組むことが

大切。
同じようでも
「うまい方法はないからやめた」とか
「めんどうだからやめた」というのとはちがうよ。

--------------------------------------------------
左から1,2番目がＡとＢ並ぶ型を型1
左から2,3番目がはじめてＡとＢ並ぶ型を型2
左から3,4番目がはじめてＡとＢ並ぶ型を型3
左から4,5番目がはじめてＡとＢ並ぶ型を型4
左から5,6番目がはじめてＡとＢ並ぶ型を型5
と呼ぶことにする。

ためしに書き並べる。
------------------------------------

型1　　　　　　　　　
ＡＢＸＸＸＸ
ＢＡＸＸＸＸ

型2
ＡＡＢＸＸＸ
ＢＢＡＸＸＸ
ＣＡＢＸＸＸ
ＣＢＡＸＸＸ

型3
ＡＡＡＢＸＸ
ＡＣＡＢＸＸ
ＡＣＢＡＸＸ
ＢＢＢＡＸＸ
ＢＣＡＢＸＸ
ＢＣＢＡＸＸ
ＣＡＡＢＸＸ
ＣＢＢＡＸＸ
ＣＣＡＢＸＸ
ＣＣＢＡＸＸ

型4
ＡＡＡＡＢＸ
ＡＡＣＡＢＸ
ＡＡＣＢＡＸ
ＡＣＡＡＢＸ
ＡＣＢＢＡＸ
ＡＣＣＡＢＸ
ＡＣＣＢＡＸ
ＢＢＢＢＡＸ
ＢＢＣＡＢＸ
ＢＢＣＢＡＸ
ＢＣＡＡＢＸ
ＢＣＢＢＡＸ
ＢＣＣＡＢＸ
ＢＣＣＢＡＸ
ＣＡＡＡＢＸ
ＣＡＣＡＢＸ
ＣＡＣＢＡＸ
ＣＢＢＢＡＸ
ＣＢＣＡＢＸ
ＣＢＣＢＡＸ
ＣＣＡＡＢＸ
ＣＣＢＢＡＸ
ＣＣＣＡＢＸ
ＣＣＣＢＡＸ

だんだん規則性が見えてきますね。
------------------------------------------------
☆「型1」は2通り
☆「型2」は
「型1」のＡの前にはＡをつける。
　Ｂの前にはＢをつける。
　どれにもＣをつける。
　1+1+2＝4（通り）
☆「型3」は
「型2」のＡかＣの前にはＡをつける。
　ＢかＣの前にはＢをつける。
　どれにもＣをつける。
　（1+2）+（1+2）+（型2の場合の数＝4）＝10（通り）
☆「型4」は
「型3」のＡかＣの前にはＡをつける。
　ＢかＣの前にはＢをつける。
　どれにもＣをつける。
　（3+4）+（3+4）+10＝24（通り）
☆「型5」は
「型4」のＡかＣの前にはＡをつける。
　ＢかＣの前にはＢをつける。
　どれにもＣをつける。
　（7+10）+（7+10）+24＝58（通り）

--------------------------------------------------
☆「型1」でＸＸＸＸの決め方は
　3＾4＝81通り
☆「型2」でＸＸＸの決め方は
　3＾3＝27通り
☆「型3」でＸＸの決め方は
　3＾2＝9通り
☆「型4」でＸの決め方は
　3＾1＝3通り
☆「型5」は各1通り
-----------------------------------------------------
全部で
　81×2+27×4+9×10+3×24+1×58
＝162+108+90+72+58　　
＝490
729-490＝239（通り）

この回答へのお礼

good777さんお返事どうもありがとうございます！

＞「うまい方法はないかなあ」と「めんどうだあ」と考えながら取り組むことが
大切。同じようでも「うまい方法はないからやめた」とか「めんどうだからやめた」というのとはちがうよ。

ちょっと問題への取り組み方が雑だったと反省しています。数え漏れとか重複とかがないだろうという希望的観測のみでめちゃめちゃな考え方でした。good777さんの回答は寸分の漏れもなく数え上げていきながらしかも規則性まで見つけておられて感服いたします。ちょっと気づいたことなんですがgood777さんは先頭の文字で場合分けを介し為されていますね。私にはこのような発想もありませんでした。枝分かれは全部書いてくださったのでもう一度自分でNO,5を見ながら場合分けをやってみようと思います。どうもありがとうございました！！

お礼日時：2002/04/26 17:58

No.3 回答者： hinebot 回答日時： 2002/04/24 20:17

済みません。

自信ありにチェックしながら、間違ってました。

>○○○○○○　と６個あるなかから、隣り合う２個を選ばないといけませんから、隣り合う左側（１個）の選び方を考えればいいわけです。一番右側はとれませんから、６－１＝５通りとなります。

ここで、ＡＢと並ぶ場合とＢＡと並ぶ場合の２通りあるので、２×５＝１０通りです。
729-239 =490 ですので、残りの４箇所の並べ方が49通りであることが示せれば、
729-10×49＝239
と計算があうんですが…。もう少し悩みます。

この回答へのお礼

hinebotさんお返事どうもありがとうございます。

＞左側（１個）の選び方を考えればいいわけです。一番右側はとれませんから、６－１＝５通りとなります。
ここで、ＡＢと並ぶ場合とＢＡと並ぶ場合の２通りあるので、２×５＝１０通りです。

そうですね、私も同じ値になったので安心しました。

あとは・・・ここからが問題ですね。

お礼日時：2002/04/26 00:12

No.2 回答者： hinebot 回答日時： 2002/04/24 19:57

>６この場所から２つ選んで並べるとおりの6P2=30

これがおかしいですね。
#1の方も仰ってますが、「○ ○ ○ Ａ ○ Ｂ」の様なＡとＢが隣り合わない場合も含まれてしまいます。

○○○○○○　と６個あるなかから、隣り合う２個を選ばないといけませんから、隣り合う左側（１個）の選び方を考えればいいわけです。一番右側はとれませんから、６－１＝５通りとなります。

これでも、729 - 5*81 = 324 ですので、まだ見落としがありますね。
もうちょっと、考えてみます。

No.1 回答者： rei00 回答日時： 2002/04/24 19:34

　詳しい事は解らないので，どう改良すれば正しい答えが得られるかは解りませんが，次の点はいかがでしょうか？

> ６この場所から２つ選んで並べるとおりの6P2=30
　これだと，「○ ○ ○ Ａ ○ Ｂ」の様なＡとＢが隣り合わない場合も含んでいませんか？

> 残りの４個の場所はA,B,Cのどれでもいいから3^4=81
　これには「○ Ｂ Ａ Ｂ ○ ○」や「○ ○ Ａ Ｂ Ａ ○」の様な場合も含まれていると思いますが・・・。

この回答へのお礼

>> ６この場所から２つ選んで並べるとおりの6P2=30
　これだと，「○ ○ ○ Ａ ○ Ｂ」の様なＡとＢが隣り合わない場合も含んでいませんか？

そうですね。まったく頭にありませんでした。違う方法が必要ですね。

>> 残りの４個の場所はA,B,Cのどれでもいいから3^4=81
　これには「○ Ｂ Ａ Ｂ ○ ○」や「○ ○ Ａ Ｂ Ａ ○」の様な場合も含まれていると思いますが・・・。

私は３つがとなりあっている場合でもあくまでもABの２つだけがとなりあわさっていると考えて「○ Ｂ Ａ Ｂ ○ ○」のような場合はABでひとつの組ができて残りのBは隣合わさっているのではなくて単独でそこに存在していると考えました。だから、AB以外の４つの場所にはABCの何がきても関係ないから3^4=81としたのですがどこが間違っているのでしょうか。

お礼日時：2002/04/26 00:08