当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２５年１２月２８日付け）
今年もあと僅か。1年３６５日は1週間（７日）の繰り返し。そこで下図の如く、７階建ての７つ
横並びの棟をもつマンションに４９世帯が暮らしているところを想像してもらおう。
（各マス内に一家族が住む）
[第１問]
西側端１Ｆに住むＡさんは、右隣の部屋か、もしくは真上の部屋かに回覧板を回してもらう。
次に回覧板を受け取った人も同様にその部屋の右隣か、真上の部屋に回してもらうように
依頼する。こうして回覧板が、東側端７Ｆに住むＢさんのところへ達したとすると、回覧板が
辿った経路は何通りできるか。
[第２問]
上記の回覧板の回し方を、右の部屋か、真上の部屋か、右斜め上の部屋から選んで回し
てもらう規則にすると、Ａさん宅からＢさん宅へ回覧板の辿る経路は何通りか。
[第３問]
回覧板回しをその部屋から次へ渡すのを右隣か、右上か、右下かの部屋で回してもらう
ことにしたとき、Ａさんから出発した回覧板が、東側端１Ｆに住むＣさんの所に達したときの
回覧板が辿った経路は何通りあるか。
[第４問」
マンション西側端に住む住人（１Ｆ〜６Ｆだれでもよい。）から出発して隣の棟の住人に回す。
ただし、最初は自分の階より高い所に住む家庭に持って行く。つぎに受け取った人は、今度
は自分が住む階より下（４Ｆに住んでいれば、３，２，１Ｆいずれでもよい）に住む隣の棟の家
庭に回す。さらに次の人は、今度は住んでいる階より上に住む隣の棟へとアップとダウンを
交互に繰り返し渡していくものとする。
さて、西端から出発した回覧板が東端の棟に辿り着いたとき、各棟の１Ｆから７Ｆの住人が
必ず一家族が含まれるような回覧板の経路は何通りできるか。
（例：西端棟から東端棟へ、4Ｆ→7Ｆ→3Ｆ→5Ｆ→2Ｆ→6Ｆ→1Ｆの住人を辿る）
（答） [第１問] 12Ｃ6＝９２４（通り） [第２問] ８９８９（通り） [第３問] ５１（通り）
[第４問」 ２７２（通り）
（回覧板といっても、全部の部屋を回らなくてもいいらしい．．．。）
ＧＡＩ さんからのコメントです。（平成２５年１２月３０日付け）
すべて正解です。（全世帯を回らなかったので他のネーミングが良かったかな？）その中で、
特に、問題２（よくある道の順路に斜めを加えた行き方）の解答数について面白いことを読ん
だので報告しておきます。
P0(x)=1 、P1(x)=x 、P2(x)=1/2 (-1 + 3 x2) 、P3(x)=1/2 (-3 x + 5 x3)
P4(x)=1/8 (3 - 30 x2 + 35 x4) 、P5(x)=1/8 (15 x - 70 x3 + 63 x5)
P6(x)=1/16 (-5 + 105 x2 - 315 x4 + 231 x6) 、P7(x)=1/16 (-35 x + 315 x3 - 693 x5 + 429 x7)
P8(x)=1/128 (35 - 1260 x2 + 6930 x4 - 12012 x6 + 6435 x8)
P9(x)=1/128 (315 x - 4620 x3 + 18018 x5 - 25740 x7 + 12155 x9)
P10(x)=1/256 (-63 + 3465 x2 - 30030 x4 + 90090 x6 - 109395 x8 + 46189 x10)
･･･････････
なるLegendre多項式という微分方程式から決まっていく関数があり、そのPN-1(3)の値が、
N×Nでの問題２（右か上か右斜めで進む）での解答数に一致するという。
（→ 参考：整数列大辞典「A001850」）
この場合、7×7のマンションで考察していたので、
P6(3)=1/16(-5+105*32-315*34+231*36)=8989（通り）
従って、2×2のマンションなら、P1(3)=3（通り）
3×3のマンションなら、P2(3)=1/2(-1+3*32)=13（通り）
4×4のマンションなら、P3(3)=1/2(-3*3+5*33)=63（通り）
･････････
以下同様。
まったく無関係に見えるLegendre(ルジャンドル）多項式と道の行き方が思わぬ所で繋がる
のが不思議でもあり、奥深さを感じてしまう。また、なぜ、x=3 なのかも不思議です。
（コメント） 問題２については、最短経路問題の裏技を活用しましたが、上記のような別解が
あるとは驚きです。ＧＡＩ さんに感謝します。
攻略法さんからのコメントです。（平成２６年１月１８日付け）
「Ａ001850」より、 a0=1 、a1=3 、an={3(2n-1)an-1 - (n-1)an-2}/n
ルジャンドル多項式が満足する漸化式（ボネの漸化式）は、
Pn+1(x)={(2n+1)xPn-nPn-1}/(n+1)
ここで、n=N-1、x=3を代入すると、PＮ(3)={3(2Ｎ-1)PN-1-(N-1)PN-2}/N となり、同じ漸化式を
満たす。
ＧＡＩ さんからのコメントです。（平成２６年１月１８日付け）
私もLegendre(ルジャンドル）多項式と道順との関連について興味があったので少し調べて
みました。
ルジャンドル多項式Pn(x)は、母関数 1/√(1-2xt+t2)=Σn=0〜∞ Pn(x)・tn ････････（*） から
決まり、従って、x=3 と置くと、1/√(1-6t+t2)=Σn=0〜∞ Pn(3)・tn となる。
左辺の関数をテイラー展開すると、tnの係数がまさにA001850の数列に一致する。
また、x=5 と置くと、1/√(1-10t+t2)=Σn=0〜∞ Pn(5)・tn となる。
左辺のテイラー展開で、tnの係数からA006442の数列が出現し、これは格子状を上方、右
斜め上、右横へは２通り（歩いて進むか走って進かの選択ができるとする。）で進むときの総
数を与える。
さらに、x=7 と置くと、1/√(1-14t+t2)=Σn=0〜∞ Pn(7)・tn となる。同様に、これからA084768
の数列が発生する。
これの説明に、
Directed 2-D walks of length 2n starting at (0,0) and ending on the X-axis using steps
NE,SE,NE,SW and avoiding NE followed by SE.
とあるが、これがどの様な行き方を意味するのかが判読できませんでした。