〇と●が合計ｎ個並んでいる。〇が少なくとも3個のグループを作らなければならないことにする。

このとき、P(n)をn人の並び方の総数とすると、漸化式

P(n)=2P(n-1)-P(n-2)+P(n-4)

が成り立つという。

P(0)=1,P(1)=1,P(2)=1,P(3)=2,P(4)=4,P(5)=7

P(6)=11,P(7)=17,P(8)=27,P(9)=44,P(10)=72

P(n+1)/P(n)→τ・・・x^4=2x^3-x^2+1の解:x^2(x-1)^2-1=(x^2-x-1)(x^2-x+1)=(x^2-x)^2-1

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ＝0の場合、

1通りとする

ｎ＝1の場合、

黒●黒 の1通り

ｎ＝2の場合、

黒●●黒 の1通り

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ＝3の場合、

白黒〇〇〇白黒

黒●●●黒 の2通り

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ＝4の場合、

白黒〇〇〇〇白黒

黒●〇〇〇白黒

白黒〇〇〇●黒

黒●●●●黒 の4通り

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ＝5の場合、

白黒〇〇〇〇〇白黒

黒●〇〇〇〇白黒

白黒〇〇〇〇●黒

黒●●〇〇〇白黒

黒●〇〇〇●黒

白黒〇〇〇●●黒

黒●●●●●黒 の7通り

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

白黒が左右対称における場合+1

おけない場合+1/2

として、P(n-1)に加えるとP(n)が得られるようである。 →破綻する

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝