００７	平成１９年度前期	京都大学	理系・乙	・・・	場合の数	標準

　この問題は、教科書や参考書で見かけたことがあると受験生全員が多分思ったことだろ
う。ただ少しだけ、知っている解法からひねってある。そこに気がつけば、この問題は、「易」
に分類されるレベルだろう。（→参考：フィボナッチ数列）


京都大学　理系・乙（２００７）

　１歩で１段または２段のいずれかで階段を昇るとき、１歩で２段昇ることは連続しないもの
とする。１５段の階段を昇る昇り方は何通りあるか。

（解）　ｎ 段の階段を上記のような昇り方で昇る場合の数を、ａ_ｎ （通り）とおく。

　　明らかに、　ａ₁ ＝１　、ａ₂ ＝２　（１段ずつ、または、２段）　、

　　　　　　 　　　ａ₃ ＝３　（１段ずつ、または、１段と２段、または、２段と１段）

　　ｎ≧４　のとき、次の何れかの場合が起こり、互いに排反である。

　　（イ）　最初の１歩で１段昇るとき、残りの ｎ−１ 段の昇り方の総数は、ａ_ｎ−1 （通り）

　　（ロ）　最初の１歩で２段昇るとき、次の１歩は１段昇り、残りの ｎ−３ 段の昇り方の総数

　　　　　は、ａ_ｎ−3 （通り）

　よって、　ａ_ｎ ＝ ａ_ｎ−1 ＋ ａ_ｎ−3 　（ｎ≧４）　が成り立つ。

　この漸化式により、順次　ａ_ｎ を求めて、

　　　ａ₄ ＝ ａ₃ ＋ ａ₁ ＝ ３＋１ ＝ ４

　　　ａ₅ ＝ ａ₄ ＋ ａ₂ ＝ ４＋２ ＝ ６

　　　ａ₆ ＝ ａ₅ ＋ ａ₃ ＝ ６＋３ ＝ ９

　　　ａ₇ ＝ ａ₆ ＋ ａ₄ ＝ ９＋４ ＝ １３

　　　ａ₈ ＝ ａ₇ ＋ ａ₅ ＝ １３＋６ ＝ １９

　　　ａ₉ ＝ ａ₈ ＋ ａ₆ ＝ １９＋９ ＝ ２８

　　　ａ₁₀ ＝ ａ₉ ＋ ａ₇ ＝ ２８＋１３ ＝ ４１

　　　ａ₁₁ ＝ ａ₁₀ ＋ ａ₈ ＝ ４１＋１９ ＝ ６０

　　　ａ₁₂ ＝ ａ₁₁ ＋ ａ₉ ＝ ６０＋２８ ＝ ８８

　　　ａ₁₃ ＝ ａ₁₂ ＋ ａ₁₀ ＝ ８８＋４１ ＝ １２９

　　　ａ₁₄ ＝ ａ₁₃ ＋ ａ₁₁ ＝ １２９＋６０ ＝ １８９

　　　ａ₁₅ ＝ ａ₁₄ ＋ ａ₁₂ ＝ １８９＋８８ ＝ ２７７

　以上から、１５段の階段を昇る昇り方は、２７７通りある。　　（終）

（コメント）　漸化式は直ぐに作れるが、その後の計算が何となく泥臭い。もっとエレガントな
　　　　　　解法はないものだろうか？

　　（追記）　平成１９年３月４日付け

　　　　　当ＨＰがいつもお世話になっているらすかるさんから、別解を頂いた。１５段のうち
　　　　の丁度真ん中の８段目の動向に注目するのがポイントのようだ。

　　　　（別解）　８段目の起こりうる場合として次の３通りあり、それらは互いに排反である。

　　　　　　　　　Ａという場合の数は、　ａ₇×ａ₇＝１３×１３＝１６９

　　　　　　　　　Ｂという場合の数は、　ａ₆×ａ₅＝９×６＝５４

　　　　　　　　　Ｃという場合の数は、　ａ₅×ａ₆＝６×９＝５４

　 　　　　以上から、１５段の階段を昇る昇り方は、

　　　　　　　　　　１６９＋５４＋５４＝２７７　（通り）　ある。　　（終）

（コメント）　なるほど！スッキリしますね．．．。　らすかるさんに感謝します。
　　　　　　でも、実際の本番だったら、泥臭くても漸化式で押し切るのかな？


　　　次のように考えてもいいようだ。（この考え方で解くことを想定していれば、問題の不自
　　然とも思える条件は、実は解答を考えやすくしているということに気づかされる。これは京
　　都大学の作問者の温情なのだろうか？）

（別解）　１段昇ることを「A」、２段昇ることを「Ｂ」と表すと、求める場合の数は、

　　　　　　　　Ｂが隣り合わないような、ＡとＢの順列の総数

　　　　　である。　よって、

　　　　　　　Ｂが０個のとき、　A・・・・・・・A（Aが１５個）という場合は、１通り

　　　　　　　Ｂが１個のとき、　A・・・・・・・A（Aが１３個）の並びにＢを挿入する場合の数は、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　₁₄Ｃ₁＝１４　（通り）

　　　　　　　Ｂが２個のとき、　A・・・・・・・A（Aが１１個）の並びにＢを挿入する場合の数は、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　₁₂Ｃ₂＝６６　（通り）

　　　　　　　Ｂが３個のとき、　A・・・・・・・A（Aが９個）の並びにＢを挿入する場合の数は、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　₁₀Ｃ₃＝１２０　（通り）

　　　　　　　Ｂが４個のとき、　A・・・・・・・A（Aが７個）の並びにＢを挿入する場合の数は、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　₈Ｃ₄＝７０　（通り）

　　　　　　　Ｂが５個のとき、　A・・・・・・・A（Aが５個）の並びにＢを挿入する場合の数は、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　₆Ｃ₅＝６　（通り）

　 　　　　以上から、１５段の階段を昇る昇り方は、

　　　　　　　　　　１＋１４＋６６＋１２０＋７０＋６＝２７７　（通り）　ある。　　（終）


（コメント）　解法的に、どちらが優れているのだろう？


　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが上記話題について考察された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２３年１２月８日付け）

　上記では、解が３通り書いてある。実際の入試で正解した人の多くは、解１によるだろうと
思うが、解２や解３による人もあったであろう。第４の解を思いついたわけではない。解２や
解３のやり方を一般化し、「１歩で２段昇ることは連続しないものとする」をはずして、フィボ
ナッチ数列の性質を導こうと思う。

　「１歩で２段昇ることは連続しないものとする」という条件で、ｎ段を昇る昇り方を、ａ_n とす
るとき、解１にあるように次の漸化式が成り立つ。

　　　　ａ_n+3 ＝ ａ_n ＋ ａ_n+2　、ａ₁＝１　、ａ₂＝２　、ａ₃＝３

　これを使って、ａ₄、ａ₅、･･･、ａ₁₅ を求めていけばよいのだが、それを一工夫しようというの
が解２で、全く違う考え方でやるのが解３である。

　解２を一般化して、次の式が成り立つ。

　　　　ａ_2n+1 ＝ ａ_n² ＋ ２ａ_n-1ａ_n-2

　「ａ_2n＝・・・」とか「ａ_n+ｍ＝・・・」とかの式もできるが、省略して、フィボナッチ数列を考える。

　「１歩で２段昇ることは連続しないものとする」をはずした場合の昇り方を ｂ_n とする。ｂ_n は
次の漸化式を満たす。

　　　　ｂ_n+2 ＝ ｂ_n ＋ ｂ_n+1　、ｂ₁＝１　、ｂ₂＝２

　漸化式は、フィボナッチ数のものと同じだが、初期条件が少し違う。

　ａ_n+1＝ｂ_n とおけば、ａ_n はフィボナッチ数列である。

　ｂ_n について、解２と同じ考え方をすると、次の式が成り立つ。

　　ｂ_2n+1 ＝ ｂ_n² ＋ ２ｂ_nｂ_n-1＝（ｂ_n ＋ ｂ_n-1）² − ｂ_n-1² ＝ ｂ_n+1² − ｂ_n-1²

　　ｂ_2n ＝ ｂ_nｂ_n-1 ＋ ｂ_nｂ_n-2 ＋ ｂ_n-1² ＝ ｂ_n² ＋ ｂ_n-1²

　　ｂ_n+ｍ ＝ ｂ_nｂ_ｍ-1 ＋ ｂ_n-1ｂ_ｍ-1 ＋ ｂ_nｂ_ｍ-2 ＝ ｂ_nｂ_ｍ ＋ ｂ_n-1ｂ_ｍ-1

　これらの式を、ａ_n+1＝ｂ_n によって、フィボナッチ数列の式に直すと、それぞれ「フィボナッ
チ数を極める」の(性質７)(性質１５)(性質５)になる。

　(性質７)(性質１５)は(性質５)の特殊化である。(性質５)は、フィボナッチ数列の性質におい
て重要な役割をしているが、数学的帰納法による証明では、どのようにしてこの式が得られ
たのかがわからなかったが、階段の昇り方で、解２の形で考えれば、自然に得られることが
わかったのは意味があると思う。解２の方法は、ちょっとした思いつきかと思ったがそうでは
なくて、本質的な方法のようだ。

　「フィボナッチ数を極める」で、攻略法さんがやられている、例えば、ａ₄₀、ａ₄₁ を求める考
え方と同じである。ａ_ｎ を、ｎ の半分のあたりでの値を使って書こうということである。だから
解２は、解１での方向での計算の短縮としては多分最善であるだろうと思う。

　解３を一般化すると、次のようになる。

　　　ａ_ｎ ＝ _n+1Ｃ₀ ＋ _n-1Ｃ₁ ＋ _n-3Ｃ₂ ＋ ････ ＋ _n+1-2rＣ_r　　ただし、ｒ=[(n+1)/3]

　「１歩で２段昇ることは連続しないものとする」をはずして、ｂ_n の関係式にすると、組合せ
が重複組合せに変わって、次のようになる。

　ｂ_ｎ ＝ _n+1Ｈ₀ ＋ _n-1Ｈ₁ ＋ _n-3Ｈ₂ ＋ ････ ＋ _n+1-2rＨ_r　　ただし、ｒ=[n/2]

　　ここで、　_n+1-2kＨ_k ＝ _n+1-2k+k-1Ｃ_k ＝ _n-kＣ_k　であるから

　ｂ_ｎ ＝ _nＣ₀ ＋ _n-1Ｃ₁ ＋ _n-2Ｃ₂ ＋ ････ ＋ _n-rＣ_r　　ただし、ｒ=[n/2]

　ｂ_ｎ はフィボナッチ数列の第ｎ＋１項 ａ_ｎ+1 であるから、これは「フィボナッチ数を極める」
の(性質２４)である。攻略法さんが碁石の並べ方を使ってされてる証明と実質的に同じだろ
うと思いますが確認できてません。