並べ方は何通りありますか。

○と✕を合わせて一列にn個並べます。

だだし、隣どうしの2つをみたときに✕✕という部分があってはいけません。

例えばn=6の場合に、
○✕○✕✕○
というのは、✕✕の部分があるのでダメです。

その条件で、
○と✕を合わせてn個並べるとしたら何通りの並べ方がありますか。

質問者からの補足コメント

• 具体的にやってみると
  
  1個の場合
  ✕
  ○
  2通り
  
  2個の場合
  ○○
  ○✕
  ✕○
  3通り
  
  3個の場合、
  ○○○
  ○○✕
  ○✕○
  ✕○○
  ✕○✕
  5通り
  
  4個
  ○○○○
  ○○○✕
  ○○✕○
  ○✕○○
  ○✕○✕
  ✕○○○
  ✕○○✕
  ✕○✕○
  8通り
  
  組み合わせを書き出すと
  2,3,5,8…
  となっています。
  
  よくみると、これは「フィボナッチ数列」ではないでしょうか。したがって、nの一般項はフィボナッチ数列の一般項になるのではないでしょうか。
  
  この予想が正しいとか、違うとかの証明はできますか。

    補足日時：2023/04/05 23:17

No.2 回答者： hondarawa 回答日時： 2023/04/06 21:12

××を含まない順列の数を２つに分けて、

n個の××を含まない並びで、末尾が○の場合の数をa(n)、末尾が×の場合のをb(n)とします。
そして、n個の並びの後に、もう１個の○又は×を追加したn+1個の並びが何通りあるかを考えます。

○に、○を追加すると○○、×を追加すると○×
×には、○を追加して×○、しかし×を追加すると××になって、不可です。
つまり、
n=1の時、a(1) = 1、　b(1) = 1 で、
n=2の時、a(2) = 2 、　b(2) = 1 です。

a(n)、b(n)について考えます。
末尾が○の場合は、○も×も追加できるので、
a(n+1) = a(n) + b(n)　です。

末尾が×の時は、○だけなので、
b(n+1) = a(n)　になります。

ここで知りたいのは、a(n)+b(n)　です。これをF(n)とするとこうなります。
F(n) = a(n) + b(n)
=a(n-1) + b(n-1) + a(n-1)
=a(n-1) + b(n-1) + a(n-2) + a(n-2)
=F(n-1) + F(n-2)　(ただしn>2)

たしかに、フィボナッチ数列になっています。

No.1 回答者： ありものがたり 回答日時： 2023/04/05 22:46

1) 列の右端に○を付ける

2) ✕の右隣りには必ず○がくることになる
3) ✕○の並びを■で置き換える
例えば、n=8 の列 ○✕○○○✕○✕ は
○■○○■■ に置き換えられる。
この操作で、○か✕がn個,そのうち✕がk個の列は
○か■がn+1-k個,そのうち■がk個の列になる。

○✕の列は○■の列と一対一に対応し、
○■の列のほうには、✕✕が並ばないなどの余計な規則はない。
その総数は、Σ{k=0..[n/2]} (n+1-k)Ck 通り。