当ＨＰがいつもお世話になっているＨＮ「ａｔ」さんからの出題です。
（平成２５年１１月１７日付け）
「数学の部屋」というサイトに、『オンボロ階段の問題』という問題が掲載されてあります。
寄せられた解答から、全部で841通りの上り方があります。この841通りの上り方のすべて
を一覧にしました。例えば、( 3 1 2 1 1 3 3 1 ) という表記は、15段の階段を、
1歩目が3段、2歩目が1段、3歩目が2段、4歩目が1段、5歩目が1段、6歩目が3段、
7歩目が3段、8歩目が1段
で上るような上り方を意味します。
この問題を少し一般化して、次のような問題を考えてみました。気が向いたら考えてみて
ください。
【問題】
ｎを任意の正整数とします。石で出来たｎ段の古いオンボロ階段があり、階段は、一
度に３段までは上ることが可能です。しかし、５の倍数となる全ての整数ｋ（５≦ｋ＜ｎ）
に対して、下からｋ段目は補修工事でセメントが塗りたてのため、踏むことはできませ
ん。(例えば、ｎ=16 のとき、下から5段目と10段目と15段目は踏むことができません。)
このオンボロ階段を上る方法の総数 ｆ(ｎ) をｎの式で表してください。
参考までに、ｎ＝1、2、3、…、16 に対するｆ(ｎ)の値は次のようになります。
f(1)=1、f(2)=2、f(3)=4、f(4)=7、f(5)=13、f(6)=11、f(7)=18、f(8)=29、f(9)=58、f(10)=105、
f(11)=87、f(12)=145、f(13)=232、f(14)=464、f(15)=841、f(16)=696
（答） 空舟さんが考察されました。（平成２５年１１月１９日付け）
A[k]＝matrix([f(5k+4)],[f(5k+3)],[f(5k+2)],[f(5k+1)]) とおいて、 A[k]についての漸化式を立
てれば、行列のｎ乗を求める問題に帰着されました。
A[0]＝matrix([f(4)],[f(3)],[f(2)],[f(1)])、A[1]＝matrix([f(9)],[f(8)],[f(7)],[f(6)]) に対して、
f(9)=f(8)+f(7)+f(6) 、f(8)=f(7)+f(6) 、f(7)=f(6)+f(4) 、f(6)=f(4)+f(3)
下から上に代入して、 f(7)=2・f(4)+f(3) 、f(8)=3・f(4)+2・f(3) 、f(9)=6・f(4)+4・f(3)
このとき、 P＝matrix([6,4,0,0],[3,2,0,0],[2,1,0,0],[1,1,0,0]) とおけば、 A[1]=P・A[0] が成
り立ちます。このようにして、一般に、A[k+1]=P・A[k] が得られます。
ハミルトンケーリーと多項式の割り算を使います。
Pの固有多項式は、g(x)=x4-8x3 で、xn を g(x) で割った余りを r(x)=ax3+bx2+cx+d とおく。
n≧3のとき、 r(8)=8n 、r(0)=0 、r'(0)=0 、r"(0)=0 より、 r(x)=8n-3・x3
従って、ｎ≧3 のとき、 Pn = 8n-3・P3
A[0]=matrix([7],[4],[3],[1]) とおくと、 A[n]=Pn・A[0]
以上により、次の結果を得ることができました。
ｎ≧3 のとき、f(5n+4)=58・8n-1、f(5n+3)=29・8n-1、f(5n+2)=145・8n-2、f(5n+1)=87・8n-2
これらより、 f(5n+5)=841・8n-2
以上は、ｎ=2 でも成り立つようです。
検討すると、Pの最小多項式は、x3-8x2 だったという事情でした。かなり単純な式になっ
たので意外でした！P3 = 8P2 と移項すれば、多項式の考え方を経由しなくて良かったです
ね。
（コメント） 明解な解答ですね！空舟さんに感謝します。
ａｔ さんからのコメントです。（平成２５年１１月２０日付け）
空舟さん、この問題を考えていただきありがとうございます。行列を用いれば、きれいに解
けるのですね。空舟さんの提示された f(ｎ) の式は簡明ですね。一応私の用意しておいた解
答も書いておきます。
f(n)=(n-8)(n-9)(15841n8-639398n7+10311722n6-85350380n5+387640529n4-953830982n3+1162017028n2
-550627560n+42386400)・FLOOR((n-11)/(11(n+1)))/1857945600-145・2^(3・FLOOR(n/5))・2^(-9)・FLOOR(n/5+4/5)
+29・2^(3・FLOOR(n/5))・2^(-5)・FLOOR(n/5+3/5)+87・2^(3・FLOOR(n/5))・2^(-6)・FLOOR(n/5+2/5)
+29・2^(3・FLOOR(n/5))・2^(-3)・FLOOR(n/5+1/5)-2871・2^(3・FLOOR(n/5))・2^(-9)・FLOOR(n/5)
+841・2^(3・FLOOR(n/5))・2^(-9).
私は、包除原理と母関数を使って考えました。
「ｎ段目を除く５の倍数の階段は踏めない」という条件を無視すれば、上り方の総数を表す母関数
は、g(ｘ)=(ｘ+ｘ2+ｘ3)/(1-ｘ-ｘ2-ｘ3) です。
g(ｘ)の ａｘ5k (ｋは正の整数) という形にかける項だけを取り出して足し合わせたものを h(ｘ) とす
れば、h(ｘ)=ｘ5(ｘ10+ｘ5+13)/(1-(21ｘ5+ｘ10+ｘ15))
f(ｎ)の母関数 Σk=1〜∞ f(k)・ｘk は、
Σk=1〜∞ f(k)・ｘk=g(ｘ)+g(ｘ)・Σk=1〜∞ (-h(ｘ))k=g(ｘ)+g(ｘ)(-h(ｘ)/(1+h(ｘ)))
=ｘ(ｘ2+ｘ+1)(ｘ12-ｘ11+2ｘ9-3ｘ8+2ｘ7+3ｘ6-8ｘ5+7ｘ4+4ｘ3+2ｘ2+ｘ+1)/(1-8ｘ5)
これを級数展開して、ｘn の係数を求めればいいです。