ｸｲｽﾞ大陸

なんでパスカルの三角形からフィボナッチが？
と思って調べたら、なるほどそういう性質があるんですね。
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2

だとすると、カードの枚数がx枚の時の解をa(x)とすると、
　a(x) = F(x+2)-1
ですよね。F(x)はフィボナッチ数列のx番目の数です。
フィボナッチ数列には
　F(x+2)=F(x+1)+F(x)
の関係がありますから、F(x+2)=a(x)+1を代入して
　a(x+2)=a(x+1)+a(x)+1
の漸化式が成り立ちます。

ということは、パスカルの三角形を使わずに、最初からダイレクトに
の漸化式を導くような別解がありそうですね。

…と、漸化式から逆に考えたところ、別解が分かりました。

a(x+2)の計算を場合分けして

(i) x+2を選ばない場合が、a(x+1)通り
(ii) ややこしいのは、x+2を選ぶ場合。
　この場合は、残りのカードがx+1枚で、その中から、
　n以上のカードをn-1枚選ぶことになる。
　カードの数字を全部1引いて0からxにしてしまえば、
　n-1以上のカードをn-1枚選ぶことになる。
　n>1の時はa(x)通りで、n=1の場合は1通りなので、
　全部でa(x)+1通り

(i)(ii)を足したら、 の漸化式が導かれました。