数学

質問

横一列に並べて固定されている9つの白いマスのいくつかを黒く塗ります。(塗るマスが0もあり)
ただし塗った黒いマスが2つ以上隣合ってはいけません。この時全ての塗り方は何通りありますか？

回答No.1

tmppassenger · ベストアンサー

例えば黒いマスを3つ作る場合を考える。
この場合白いマスが6つとなるが、ここで6つの白マスを先に一列に並べておいて、後から黒マスを列に「挿入する」、という風に考える。
この時、白マスの列の中で、黒マスを挿入出来る箇所は、（列の両外側を含めて）計7箇所あるが、（6つあるマスの間の数は6-1 = 5, それに列の両外側 2箇所を加えて7箇所）、この7箇所の同じ隙間には黒マスは2つ以上挿入出来ないから、結局この7箇所の隙間から3箇所選んで、それぞれに1つずつ黒マスを挿入する事となる。
従って、黒いマスが3つの場合の数は、7C3 = 35 となる。

結局求める場合の数は、黒マスが1つもない場合（1通り）も加えて、

1 + 9C1 + 8C2 + 7C3 + 6C4 + 5C5 = 1 + 9 + 28 + 35 + 15 + 1 = 89（通り）となる。

お礼

コンビネーション使っていただけるのはありがたかったです！ありがとうございます

Powered by GRATICA

回答No.4

staratras

2進法を応用して考えるとわかりやすいかもしれません。
白いマスを０、黒く塗ったマスを１とし、右端を1の位、左端を最上位の位と考えます
。
以下の数字はすべて2進法です。
すべての白黒のマスの塗り分けかたは０から111111111までの2進数に一対一で対応します。これから、黒が隣接する場合、すなわち数では1のゾロ目を含む数を取り除くことを考えます。
まず少なくとも1か所は塗った場合、題意を満たすのは１桁の数では1、2桁の数では10、3桁の数では100と101であることは明らかです。
ここで題意を満たすある桁数の数が得られたとして、これから1桁上の題意を満たす数
を作れるのは次の2通りしかないことがわかります。

１、1つ前の桁で得られた数の2倍（左に1桁シフト）この場合1の位は0になるのでゾロ
目にはなりません。

２、2つ前の桁で得られた数の4倍(左に2桁シフト）＋１　この場合下2桁は０１となる
のでゾロ目にはなりません。

したがって題意を満たすｎ桁の数がＡｎ通りあるとすれば、
　　Ａｎ＝Ａn-1＋Ａn-2 が成り立ちます。
Ａ1＝１、Ａ２＝１だから　Ａ３＝２、Ａ４＝３、Ａ５＝５、Ａ６＝８
Ａ７＝１３　Ａ８＝２１　Ａ９＝３４
また一つも塗らなくてもよいのでＡ０＝１
も題意を満たします。

答えはこれらをすべて加えた
１＋１＋２＋３＋５＋８＋１３＋２１＋３４＋１＝８９(通り）

お礼

ありがとうございます

Powered by GRATICA

回答No.3

tmppassenger

こうやってデバッグ表示させてみると、実はこれFibonacci列になっているのか...

9の所をnに変えた場合の数を考えてみる。
つまり、『横一列にn個の白マスが並んでいて、このうちの0個以上のマスを、黒マスが連続しないように黒マスに塗る場合の数』を a[n] とすると：

(a) 左端を黒マスにする場合： この場合左から2番目のマスは黒く塗れない。左から3番目以降の塗り方を決めればよいので、この場合はa[n-2] 通り
(b) 左端を白マスのままにする場合： この場合左から2番目以降の塗り方を考えれば良いので、この場合は a[n-1]通り

つまり、a[n] = a[n-1] + a[n-2] の漸化式が成立する。
明らかにa[1] = 2, a[2] = 3 であるから、a[3] = 5, a[4] = 8, a[5] = 13, a[6] = 21, a[7] = 34, a[8] = 55, a[9] = 89 となる。

お礼

ありがとうございます

Powered by GRATICA

回答No.2

tmppassenger

検証
https://wandbox.org/permlink/TjsukllLIdfYzlnG
0が白マス、1が黒マス

お礼

丁寧にありがとうございます

Powered by GRATICA