FC2ブログ

Welcome to my blog

[答149] 黒石が3連続しない並べ方

ヤドカリ

ヤドカリ


'


[答149] 黒石が3連続しない並べ方


 白黒の碁石全部で8個(白石だけでも可)を1列に、

 黒石が3個以上連続しないように並べるときの並べ方は何通り?


[解答]

 ●●●を含まないから、①②③④⑤⑥⑦〇 or ①②③④⑤⑥〇● or ①②③④⑤〇●● です。

 つまり、条件に合うように7個並べて〇 か 6個並べて〇● か 5個並べて〇●● です。

 従って、n個の並べ方を Tn 通りとすれば、T8=T7+T6+T5 です。

 1個の場合は、〇 or ● で、T1=2
 
 2個の場合は、〇〇 or 〇● or ●〇 or ●● で、T2=4

 3個の場合は、●●● を除いて、T3=7

 あとは、T8=T7+T6+T5 と同様に、

 T4=T3+T2+T1=13, T5=T4+T3+T2=24, T6=T5+T4+T3=44,

 T7=T6+T5+T4=81, T8=T7+T6+T5=149 で 149 通りです。


 Tn+3=Tn+2+Tn+1+Tn を満たす数列は有名で、トリボナッチ数列といいます。

 一般項は、方程式 x3-x2-x-1=0 の解α, β, γを使って、

 Tn+3=(α+β+γ)Tn+2-(βγ+γα+αβ)Tn+1+αβγTn

 数列 { Tn+2-(β+γ)Tn+1+βγTn } が公比αの等比数列になること等で解けますが、

 実際にこの漸化式を解くのは、簡単ではありません。

 また、方程式自体が、カルダノの公式を使うなど、α, β, γはかなり複雑な値です。

.

スポンサーサイト



Comments 16

There are no comments yet.
アキチャン  
No title

おはようございます。
今日は 白い色ですね (o^-^o)

uch*n*an  
No title

私は三つの方法で解きましたが,(解法1)が[解答]と同じでした。
(解法3)は(解法2)と等価なので,まぁ,いいとして,
(解法2)を,若干補って,ご参考までに示しておきます。

uch*n*an  
No title

最初に白を並べ,両端又は白の間に,まず黒二個を入れ,残りに黒一個ずつを入れる,
と考えます。ただし,黒は 3 個以上は並べないので,白は 2 個以上です。
白が 2 個,黒は 6 個,3C3 = 1 通り。
白が 3 個,黒は 5 個,4C2 * 2C1 + 4C1 * 3C3 = 16 通り。
白が 4 個,黒は 4 個,5C2 * 3C0 + 5C1 * 4C2 + 5C0 * 5C4 = 45 通り。
白が 5 個,黒は 3 個,6C1 * 5C1 + 6C0 * 6C3 = 50 通り。
白が 6 個,黒は 2 個,7C1 * 6C0 + 7C0 * 7C2 = 28 通り。
白が 7 個,黒は 1 個,8C0 * 8C1 = 8 通り。
白が 8 個,黒は 0 個,1 通り。
以上ですべてなので,1 + 16 + 45 + 50 + 28 + 8 + 1 = 149 通り,になります。

uch*n*an  
No title

この解法は,漸化式ほど楽ではないですが,曲りなりにも,
組合せと,足し算,掛け算だけで一般項を書き下せる,という利点はあります。
結果は,[ ] をガウス記号として,n = 1, 2, 3, 4, 5, ... で,
T(n) = Σ(k=0,n){Σ(m=0,[(n-k)/2]){(k+1)Cm * (k+1-m)C(n-k-2m)}}
ただし,a < b では aCb は意味がないので 0 と定義しておきます。
残念ながらこれは簡単になりそうにはないし,有用かどうかも疑問です。
複素数の出て来る漸化式の一般項よりはまだましかなぁ,というレベルですが。
ただ,理論的な議論をする場合には,漸化式の一般項の方が有用そうですね。

スモークマン  
No title

わたしは...uch*n*anさんの方法でしか解けなかったんですが...^^;
最初...4x4の格子路で横3個は通れないってな...カタラン数もどきの方法でできないかなぁって思ったのですが...挫折しました...^^;;;...Orz...

ヤドカリ  
No title

アキチャンさん、コメントを有難う御座います。
はい、今日は白です。白いセキチクもいいです。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
いろんな解答がある場合、中々全部を紹介しきれませんのでコメントを頂くと助かります。

トリボナッチ数列以外の解き方は数え上げですね。
①貴殿のように白黒の個数での場合分け、
②256通りから黒が8連続・7連続・…・3連続をダブリに注意して引く方法、
③プログラムによる方法
の3通りの解答がありました。

私は、ΣΣ で一般化することまでは考えていませんでしたので、
石の数が増えると困難になると思って紹介しませんでした。

②の方法については、ふじもさんの解答を簡略に書くと、
●8連続→1通り、●7連続→2通り、●6連続→5通り、
●5連続→12通り、●4連続→28通り、●3連続→64通り
このうち、重複カウントしたものは、
3連続と4連続の部分が両方あるもの 2通り
3連続の部分が2ヶ所にあるもの 3通り
というものです。

なお、漸化式の一般項についての話題は、疑問の鍵コメがあったので、
さわりの部分だけしたためました。

ヤドカリ  
No title

crazy_tomboさん、コメントを有難う御座います。
カタラン数は、132 の次は、429, 1430, …… ですので、当分使えそうにありません。
トリボナッチも次は 274 だから、これも中々使えませんね。

いっちゃん  
No title

こんばんは。
白い花は可愛いブーケにしたらジューンブライドに
ぴったり・・と思ったら、もう日が変わり7月でした。。
ポチ

ヤドカリ  
No title

いっちゃん、コメントとポチを有難う御座います。
執拗にセキチクを使いました。
撫子はピンクのイメージですが、白もいいです。
娘さんのブーケですか?

いっちゃん  
No title

こんにちは~
ゆぅはまだまだです^^笑

ヤドカリ  
No title

いっちゃん、コメントを有難う御座います。
「まだまだ」と思っているのは親だけかも知れませんよ^^笑

黒翼  
No title

質問失礼します.

3行目のT8 = T7 + T6 + T5となるところが,ピンときません.なぜこれが成り立つのでしょうか.

くだらない質問を何度もすみません.

ヤドカリ  
No title

黒翼さん、コメントを有難う御座います。
説明を書き変えました。
①②③④⑤⑥⑦ の所の並べ方が T7 通りという意味です。

黒翼  
No title

そんなに単純だったのか!!ありがとうございます.スッキリしました.

ヤドカリ  
No title

黒翼さん、コメントを有難う御座います。
はい、単純です。単純でもいつも思いつくのは難しい事です。