191224

PARI


King walk

この記事は
日曜数学 Advent Calendar 2019
の12/24 分として書いております。

チェスのキングは
八方（左右、前後、斜め）に対して一つ進めることができます。
kステップ動いたのち、キングが元の位置に戻ってくる回数は、
(-1 + (1 + x_1 + 1/x_1) * (1 + x_2 + 1/x_2))^k

を展開した時の定数項に一致します。

チェスのキングは平面上で動きますが、３次元バージョンを考えてみましょう。

3×3×3のルービックキューブの中心が現在地で、

1ステップで各表面の26方向へ一つ動けると考えるのです。

kステップ動いたのち、元の位置に戻ってくる回数は、
(-1 + (1 + x_1 + 1/x_1) * (1 + x_2 + 1/x_2) * (1 + x_3 + 1/x_3))^k

を展開した時の定数項に一致します。

一般にn次元の場合、

kステップ動いたのち、元の位置に戻ってくる回数は、
(-1 + Product_{j=1..n} (1 + x_j + 1/x_j))^k

を展開した時の定数項に一致します。

この計算はもう少し簡単にできます。

(Product_{i=1..n} (1 + x_i + 1/x_i))^j を展開した時の定数項

＝ Product_{i=1..n} (1 + x_i + 1/x_i)^j を展開した時の定数項

＝ ((1 + x + 1/x)^j を展開した時の定数項)^n

OEIS の数列を使えば、A002426(j)^n と表せます。

よって、

(-1 + Product_{j=1..n} (1 + x_j + 1/x_j))^k を展開した時の定数項

＝ Sum_{j=0..k} (-1)^(k-j) * binomial(k,j) * A002426(j)^n

となります。

計算させると以下のようになります。

(23:30) gp > A002426(n) = polcoef((1+x+1/x)^n, 0);
(23:31) gp > T(n, k) = sum(j=0, k, (-1)^(k-j)*binomial(k, j)*A002426(j)^n);
(23:31) gp > for(n=0, 20, for(k=0, 10, print1(T(n, k), ", ")); print)
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 2, 0, 6, 0, 20, 0, 70, 0, 252,
1, 0, 8, 24, 216, 1200, 8840, 58800, 423640, 3000480, 21824208,
1, 0, 26, 264, 5646, 101520, 2103740, 43632960, 942507790, 20685977760, 462661368876,
1, 0, 80, 2160, 121200, 6136800, 356570960, 21225304800, 1321586558320, 84398804078400, 5518934916677280,
1, 0, 242, 16080, 2410326, 332810400, 53697494180, 8991859578240, 1588952640046870, 290130193580539200, 54549289544119302492,
1, 0, 728, 115464, 46579656, 17362227600, 7753173594200, 3629664225897360, 1811032329629569480, 940207973773389212640, 505521059527272701647728,
1, 0, 2186, 816984, 890590686, 892949532720, 1102613692023500, 1440193875113407680, 2025646018337212678750, 2984605767929762104796640, 4580903032976856547078813836,
1, 0, 6560, 5745120, 16960543200, 45683084337600, 155951498758639520, 567944244530248152000, 2250630808138439243100640, 9405790933578792370103875200, 41186695004494186284009057648960,
1, 0, 19682, 40294560, 322526401446, 2332552137940800, 22013844950551909940, 223477342019800334350080, 2494694420290305518682852070, 29565964235758317208187044137600, 369291716262954385908143721687103932,
1, 0, 59048, 282298104, 6129936711096, 119011771320486000, 3105211996810908133160, 87865435772790767441547120, 2762903510649274890304259156920, 92853195312739597910538704061876000, 3307988125501026209547184198622507128848,
1, 0, 177146, 1976795304, 116482350654126, 6070581183685267920, 437899163240110617456860, 34536594257569505700554894400, 3059036113828903357039319734452910, 291516712235354833828936612458104505120, 29621816642630699912347389676070105208847596,
1, 0, 531440, 13839692880, 2213259557106000, 309618277939433642400, 61747060232035934608701680, 13573654018001312482667475837600, 3386550256699760816295197618010010960, 915126904997952337833503004060933342590400, 265221073703749587985887533425673329603712387040,
1, 0, 1594322, 96884227440, 42052595915781366, 15790886299208255071200, 8706502688512700407049903300, 5334554951942094554923679008187520, 3748988667677151219914737014220221471670, 2872645288663714089413610253783802286224779200, 2374577478924287643853175891958583461235356269740572,
1, 0, 4782968, 678208723944, 799003972919290536, 805341929694344570456400, 1227625406195478161931139241720, 2096495454437706444750103307348128080, 4150160926209119477755778680281848395297960, 9017302122873267595804056452835185182035004414560, 21259759185044272142430764840375250012215982054560315568,
1, 0, 14348906, 4747518463224, 15181108039714851966, 41072566255182882498507120, 173095617158899589750238957859820, 823924879127974937763464434638516957120, 4594240120511411585839159498369273571230390270, 28305387261941680100199336324670785438392885649199200, 190339148250353108850884378220542742326450589919423117134156,
1, 0, 43046720, 33232801429440, 288441280636157169600, 2094703307992562867214691200, 24406504198603827521142913801413440, 323802782838102547765577218632060514377600, 5085828519667281370110380916068554882553035833280, 88850694634737351347331932838111408818530669002875424000, 1704108039961408686800976867647225575282130250161078374284923520,
1, 0, 129140162, 232630126566720, 5480385927263521078086, 106829914858232254578547881600, 3441318223143176940404509544544690260, 127254536708454833790727311255657411781762560, 5630014020833491770527448669709466254480989939681670, 278902423468087877350711661471807244093473492150830487328000, 15256884447554743593810257419611723923448460574114489822249374028412,
1, 0, 387420488, 1628412435648984, 104127343784259174413976, 5448326534631639871710124618800, 485225927151346739978386836406550695880, 50011038996908458739710252508470890544530600240, 6232426247940633585562225612784491307253582951209704600, 875474810228030297980286592083938877044218087078808841730172320, 136594902674345478002136256122700208615163605754272078178820824681495888,
1, 0, 1162261466, 11398891698588744, 1978419610064739821200206, 277864669926588964621217882050320, 68416858670436309628828404555874869648380, 19654339181723578314889028398077419299446555819840, 6899296142133342406441185236286033004645978481962113290830, 2748115543284400700622239840311464001821063400756172950274295614880, 1222934214543521591907445349921001815312548110928799458469602913941024857516,
1, 0, 3486784400, 79792255837258800, 37589973138376913923614000, 14171098482803177085818962565724000, 9646777222578443139247915357317801581190800, 7724155419104705917696652637400796029722750440508000, 7637520941607196334975959820105352015097297261393359964471600, 8626334816544062579146867201600250292909722705424511742032658625576000, 10948930182583587673093631193088330075459621308898820661027560456686042050650400,
(23:31) gp >