ｎ個の碁石を●が隣り合わないように並べる並べ方の総数をｆ_n通りであるとする．

解答１

1. １個のとき

   ○　●

   以上２通りである．

   ｆ₁＝２

2. ２個のとき

   ○○　○●　●○

   以上３通りである．

   ｆ₂＝３

3. ３個のとき

   ○○○　○○●　○●○　●○○　●○●

   以上５通りである．

   ｆ₃＝５

4. ４個のとき

   ○○○○　○○○●　○○●○　○●○○　○●○●
   ●○○○　●○○●　●○●○

   以上８通りである．

   ｆ₄＝８

   　３個，４個の場合から，一般の場合が類推できる．

5. ｎ≧３ のとき，ｆ₁，…，ｆ_n-2，ｆ_n-1 が定まったとする．

   １つ目の石を○とすると，残りのｎ−１個の並べ方はｆ_n-1通りである．

   １つ目の石を●とすると，２つ目は○でなければならず，残りのｎ−２個の並べ方はｆ_n-2通りである．

   ゆえに，ｆ_n＝ｆ_n-1＋ｆ_n-2

6. これは，フィボナッチ数列である．

   ｆ₀〜ｆ₁₀ は次のようになる（ｆ₀＝１ とする）.

   １，２，３，５，８，13，21，34，55，85，144

解答２
　●の個数で分類して考える．

1. ●が０個の場合

   ｎ個すべて○だから，１通りある．

2. ●が１個の場合

   ○をｎ−１個，●を１個並べる並べ方である．

   ゆえに，_nC₁＝ｎ通りある.

3. ●が２個の場合

   ２個ある●の間に○が１個以上あるので，間にある○を１個取り除いた列を考える．

   取り除く前の列が異なれば，取り除いた後の列も異なる．

   取り除いた後の列には，○をｎ−３個，●を２個並べる並べ方がすべて現れる．

   このような並べ方は，_n-1C₂通りある.

4. ●がｋ個ある場合（ｋ≦(ｎ＋１)／２）

   すべての●と●の間から○を１個ずつ取り除いた列を考える．

   取り除く前の列が異なれば，取り除いた後の列も異なる．

   取り除いた後の列には，○をｎ−２ｋ＋１個，●をｋ個並べる並べ方がすべて現れる．

   このような並べ方は，_n-k+1C_k通りある.

5. 合計すると（●が０個のときの１は_n+1C₀と表せるから），
   ｆ_n＝Σ _n-k+1C_k　（０≦ｋ≦(ｎ＋１)／２）

   ｆ₁₀＝₁₁C₀＋₁₀C₁＋ ₉C₂＋₈C₃＋ ₇C₄＋₆C₅
   　　＝１＋10＋36＋56＋35＋６＝144

これから，フィボナッチ数列とパスカルの三角形の間の興味深い関係が得られる．

１								１
１							１		１
２						１		２		１
３					１		３		３		１
５				１		４		６		４		１
８			１		５		10		10		５		１
13		１		６		15		20		15		６		１