In How Many Ways Can The Chess Pieces Walk n steps, staying on the board? By Shalosh B. Ekhad Theorem 1: Let N(n) be the number of ways a Knight can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, second column) never getting off the board, but with no other pieces in its way, and RETURNING TO ITS STARTING LOCATION. We have: infinity ----- \ n 44 42 40 ) N(n) t = (6401949696 t - 120046288896 t + 938591729664 t / ----- n = 0 38 36 34 - 4158527392256 t + 11876735584768 t - 23487147816832 t 32 30 28 + 33650380462224 t - 36013769415876 t + 29413334644818 t 26 24 22 - 18608443660581 t + 9212319078339 t - 3591185903428 t 20 18 16 14 + 1105528358318 t - 268685441229 t + 51373260051 t - 7672920180 t 12 10 8 6 4 2 + 884944470 t - 77455183 t + 5012665 t - 230468 t + 7050 t - 127 t / 12 2 4 24 + 1) / ((-778007264 t + 126 t - 6906 t - 5477084687453 t / 22 8 16 32 + 2331088574968 t - 4710523 t - 41028550343 t - 12485590818496 t 10 18 34 20 + 70643166 t + 202036318746 t + 7418834478848 t - 775909563682 t 14 38 40 42 + 6454673128 t + 853645496320 t - 137985490944 t + 9831186432 t 36 26 28 - 3098698852864 t + 10027463891722 t - 14199186452644 t 30 6 2 + 15366841655912 t + 221752 t - 1) (4 t - 1)) In Maple input format it is: (6401949696*t^44-120046288896*t^42+938591729664*t^40-4158527392256*t^38+ 11876735584768*t^36-23487147816832*t^34+33650380462224*t^32-36013769415876*t^30 +29413334644818*t^28-18608443660581*t^26+9212319078339*t^24-3591185903428*t^22+ 1105528358318*t^20-268685441229*t^18+51373260051*t^16-7672920180*t^14+884944470 *t^12-77455183*t^10+5012665*t^8-230468*t^6+7050*t^4-127*t^2+1)/(-778007264*t^12 +126*t^2-6906*t^4-5477084687453*t^24+2331088574968*t^22-4710523*t^8-41028550343 *t^16-12485590818496*t^32+70643166*t^10+202036318746*t^18+7418834478848*t^34-\ 775909563682*t^20+6454673128*t^14+853645496320*t^38-137985490944*t^40+ 9831186432*t^42-3098698852864*t^36+10027463891722*t^26-14199186452644*t^28+ 15366841655912*t^30+221752*t^6-1)/(4*t^2-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [0, 3, 0, 30, 0, 578, 0, 16102, 0, 529042, 0, 18493354, 0, 660614194, 0, 23774230742, 0, 857769312498, 0, 30975227279378, 0, 1118895528187682, 0, 40421263921389310, 0, 1460312971638806946, 0, 52757893488848169978, 0, 1906034882974149797714] Of course the number of ways of walking an odd number of steps is 0, and N(2n) is asymptotically n 0.00817455596313203761054829482880 36.1280406445029591509294343328 Theorem 1': Let N1(n) be the number of ways a Knight can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, second column) never getting off the board, but with no other pieces in its way, and ENDING UP ANYWHERE ON THE BOARD. We have: infinity ----- \ n ) N1(n) t = / ----- n = 0 7 6 5 4 3 2 72 t + 112 t - 40 t - 85 t + 4 t + 18 t - 1 - ----------------------------------------------------------------- 8 7 6 5 4 3 2 96 t - 16 t - 276 t - 42 t + 162 t + 29 t - 27 t - 3 t + 1 In Maple input format it is: -(72*t^7+112*t^6-40*t^5-85*t^4+4*t^3+18*t^2-1)/(96*t^8-16*t^7-276*t^6-42*t^5+ 162*t^4+29*t^3-27*t^2-3*t+1) The first, 30, terms of the enumerating sequence (staring at n=1) are [3, 18, 102, 628, 3712, 22508, 134540, 811156, 4866500, 29281892, 175892276, 1057614132, 6355591348, 38206077028, 229626895060, 1380268397268, 8296116714228 , 49865871985476, 299724261334932, 1801549827899764, 10828472800643572, 65086386141434020, 391211783645273812, 2351442625161463060, 14133718657748369908, 84953002646577478660, 510623604597797734676, 3069185383169594594228, 18447830865675617994740, 110883652424162964235620] N1(n) is asymptotically n 0.475555694654920134026815461507 6.01066058303935168650729032336 Theorem 2: Let B(n) be the number of ways a Bishop can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, third column) never getting off the board, but with no other pieces in its way, and RETURNING TO ITS STARTING LOCATION. We have: infinity ----- \ n ) B(n) t = - ( / ----- n = 0 8 7 6 5 4 3 2 936 t + 468 t - 3668 t + 752 t + 1562 t - 979 t + 233 t - 25 t + 1) / 2 3 / ((-3 t - 6 t + 1 + 8 t ) / 7 6 5 4 3 2 (192 t + 184 t - 1066 t - 113 t + 468 t - 166 t + 22 t - 1)) In Maple input format it is: -(936*t^8+468*t^7-3668*t^6+752*t^5+1562*t^4-979*t^3+233*t^2-25*t+1)/(-3*t-6*t^2 +1+8*t^3)/(192*t^7+184*t^6-1066*t^5-113*t^4+468*t^3-166*t^2+22*t-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [0, 7, 22, 185, 1324, 11183, 97130, 869061, 7863800, 71606571, 653956662, 5981357281, 54749470692, 501339473191, 4591712989762, 42059758670909, 385288444429456, 3529559295655523, 32334320371046414, 296218435637140953, 2713709983802161148, 24860884166867215071, 227756502305332056474, 2086534896711866149813, 19115291243742908017704, 175120275210754072927387, 1604324049113100709142758, 14697648257722033021597649, 134649164691207836426916628, 1233557827513312659049313687] B(n) is asymptotically n 0.0170797743614389994884497011632 9.16127478196252927617267254356 Theorem 2': Let B1(n) be the number of ways a Bishop can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, third column) never getting off the board, but with no other pieces in its way, and ENDING UP ANYWHERE ON THE BOARD. We have: infinity ----- \ n ) B1(n) t = / ----- n = 0 5 4 3 2 180 t - 36 t - 125 t + 75 t - 15 t + 1 - --------------------------------------------------------------- 7 6 5 4 3 2 192 t + 184 t - 1066 t - 113 t + 468 t - 166 t + 22 t - 1 In Maple input format it is: -(180*t^5-36*t^4-125*t^3+75*t^2-15*t+1)/(192*t^7+184*t^6-1066*t^5-113*t^4+468*t ^3-166*t^2+22*t-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [7, 63, 567, 5143, 46831, 427503, 3908295, 35761255, 327384127, 2997990015, 27458531415, 251517507895, 2304013588495, 21106551451023, 193356503361639, 1771356107536519, 16227677671797343, 148665070961909535, 1361955087105884919, 12477207990394487383, 114306921406225597231, 1047195921852632784687, 9593642769404989380615, 87889958578886829665959, 805183838034302312120959, 7376509112999545096504767, 67578219599050075497676695, 619102597088161606316766583, 5671768769724626613365876815, 51960630820339120252372363983] B1(n) is asymptotically n 0.719444191312708698475432912287 9.16127478196252927617267254356 Theorem 3: Let R(n) be the number of ways a Rook can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, first column) never getting off the board, but with no other pieces in its way, and RETURNING TO ITS STARTING LOCATION. We have: infinity ----- 2 \ n 58 t - 18 t + 1 ) R(n) t = ---------------------------- / 2 ----- (2 t + 1) (84 t - 20 t + 1) n = 0 In Maple input format it is: (58*t^2-18*t+1)/(2*t+1)/(84*t^2-20*t+1) The first, 30, terms of the enumerating sequence (staring at n=1) are [0, 14, 84, 896, 10080, 127904, 1708224, 23426816, 325032960, 4532831744, 63353816064, 886318555136, 12404650352640, 173642248822784, 2430854346031104, 34031138021113856, 476430995352453120, 6670004313281921024, 93379882656019513344, 1307317290804734590976, 18302435672989001318400, 256234061032182423486464, 3587276624112572153462784, 50221871355548119907434496 , 703106190685506336435732480, 9843486619844084658134319104, 137808812379299160898796519424, 1929323371519080106699224252416, 27010527190520472618472424079360, 378147380602806723406739951058944] R(n) is asymptotically n 0.0156250000000000000000000000071 14.0000000000000000000000000000 Theorem 3': Let R1(n) be the number of ways a Rook can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, first column) never getting off the board, but with no other pieces in its way, and ENDING UP ANYWHERE ON THE BOARD. We have: infinity ----- \ n 1 ) R1(n) t = - -------- / 14 t - 1 ----- n = 0 In Maple input format it is: -1/(14*t-1) Comment by DZ: Even a human can get this (trivially) by pure thought! (why?) The first, 30, terms of the enumerating sequence (staring at n=1) are [14, 196, 2744, 38416, 537824, 7529536, 105413504, 1475789056, 20661046784, 289254654976, 4049565169664, 56693912375296, 793714773254144, 11112006825558016 , 155568095557812224, 2177953337809371136, 30491346729331195904, 426878854210636742656, 5976303958948914397184, 83668255425284801560576, 1171355575953987221848064, 16398978063355821105872896, 229585692886981495482220544, 3214199700417740936751087616, 44998795805848373114515226624, 629983141281877223603213172736, 8819763977946281130444984418304, 123476695691247935826229781856256, 1728673739677471101567216945987584, 24201432355484595421941037243826176] R1(n) is asymptotically n 1.00000000000000000000000000000 14.0000000000000000000000000000 Theorem 4: Let Q(n) be the number of ways a Queen can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, fourth column) never getting off the board, but with no other pieces in its way, and RETURNING TO ITS STARTING LOCATION. We have: infinity ----- \ n 17 9 3 ) Q(n) t = - (1950497755648 t - 68 t + 1 - 355692240 t - 27604 t / ----- n = 0 4 2 5 6 7 + 220068 t + 1883 t - 686474 t - 3372774 t + 40066304 t 8 10 12 14 - 109003719 t + 2948222415 t - 24231162550 t + 35317743484 t 18 16 20 - 4482161872832 t + 648807602264 t + 12416869424256 t 22 24 26 - 15289404469248 t + 5208863883264 t + 2400189677568 t 11 21 19 - 3591377964 t - 5581081238016 t - 1740031827968 t 23 25 27 + 15015493189632 t - 10686125408256 t + 635608498176 t 13 15 / 17 + 84478206798 t - 607141869488 t ) / ((4 t + 1) (520224768 t / 16 15 14 13 - 933728256 t - 8487936 t + 884399616 t - 396529728 t 12 11 10 9 8 - 234837168 t + 200136160 t - 2204280 t - 34821028 t + 8643313 t 7 6 5 4 3 2 + 1661792 t - 1037284 t + 110520 t + 25158 t - 8416 t + 980 t - 52 t 10 9 8 7 6 5 + 1) (4608 t - 7296 t - 10816 t + 15472 t - 348 t - 4652 t 4 3 2 + 1375 t + 168 t - 130 t + 20 t - 1)) In Maple input format it is: -(1950497755648*t^17-68*t+1-355692240*t^9-27604*t^3+220068*t^4+1883*t^2-686474* t^5-3372774*t^6+40066304*t^7-109003719*t^8+2948222415*t^10-24231162550*t^12+ 35317743484*t^14-4482161872832*t^18+648807602264*t^16+12416869424256*t^20-\ 15289404469248*t^22+5208863883264*t^24+2400189677568*t^26-3591377964*t^11-\ 5581081238016*t^21-1740031827968*t^19+15015493189632*t^23-10686125408256*t^25+ 635608498176*t^27+84478206798*t^13-607141869488*t^15)/(4*t+1)/(520224768*t^17-\ 933728256*t^16-8487936*t^15+884399616*t^14-396529728*t^13-234837168*t^12+ 200136160*t^11-2204280*t^10-34821028*t^9+8643313*t^8+1661792*t^7-1037284*t^6+ 110520*t^5+25158*t^4-8416*t^3+980*t^2-52*t+1)/(4608*t^10-7296*t^9-10816*t^8+ 15472*t^7-348*t^6-4652*t^5+1375*t^4+168*t^3-130*t^2+20*t-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [0, 21, 168, 3927, 83222, 1895461, 43260012, 991219451, 22725409186, 521171219697, 11953121525144, 274153661273639, 6287968403757006, 144220788722824989, 3307849733061615172, 75868903641831891155, 1740130769684441161466, 39911677221186748019785, 915415107454533238825456, 20995981132214970098861183, 481564287746173345155789094, 11045169161685525803047001717, 253332244375017804095473027228, 5810433964685017103273275824427, 133268242034165499191268633978450, 3056643349344070643526179695183265, 70107239523037063454530835532323400, 1607981197609345442275665964143255255, 36880692342992399368828768355086554750, 845896375978013698221783926319352461773] Q(n) is asymptotically n 0.0129352310844525887627023693827 22.9360221362211689601524227017 Theorem 4': Let Q1(n) be the number of ways a Queen can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, fourth column) never getting off the board, but with no other pieces in its way, and ENDING UP ANYWHERE ON THE BOARD. We have: infinity ----- \ n 8 7 6 5 4 3 ) Q1(n) t = - (9216 t - 10432 t - 352 t + 3876 t - 1152 t - 153 t / ----- n = 0 2 / 9 8 7 6 + 119 t - 19 t + 1) / (112896 t - 170880 t + 29184 t + 55636 t / 5 4 3 2 - 26128 t + 79 t + 2120 t - 482 t + 40 t - 1) In Maple input format it is: -(9216*t^8-10432*t^7-352*t^6+3876*t^5-1152*t^4-153*t^3+119*t^2-19*t+1)/(112896* t^9-170880*t^8+29184*t^7+55636*t^6-26128*t^5+79*t^4+2120*t^3-482*t^2+40*t-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [21, 477, 10925, 250533, 5746117, 131793053, 3022810813, 69331282293, 1590184037717, 36472497823469, 836534027893645, 19186763050457861, 440068022493111397, 10093409908178026685, 231502673101745687261, 5309750434967190375189, 121784553514906654750197, 2793253215271961705093389, 64066117577574785757806765, 1469421890941163375747874213, 33702693018075468697254803973, 773005713112851544356611743709, 17729676147381829607908387177725, 406648244584382316677459520232117, 9326893139442874241985681424677013, 213921827508431125689746040743796013, 4906515771154262942749429235335135181, 112535954338912454414436961608908900933, 2581127139838070762418508961706845714853, 59200789215727223678807579728347636947197] Q1(n) is asymptotically n 0.905283330954138392207135014032 22.9360221362211689601524227017 Theorem 5: Let K(n) be the number of ways a King can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, fifth column) never getting off the board, but with no other pieces in its way, and RETURNING TO ITS STARTING LOCATION. We have: infinity ----- \ n 17 9 3 4 ) K(n) t = (620633898 t + 14 t - 1 + 6426456 t - 941 t + 607 t / ----- n = 0 2 5 6 7 8 10 + 22 t + 29117 t - 26044 t - 539884 t + 298032 t - 82656 t 12 14 18 16 - 26227929 t + 236892895 t + 1690100338 t - 920688786 t 20 22 24 26 - 1394559224 t + 478776605 t - 37540871 t - 7210248 t 11 28 21 19 23 - 48872218 t + 222972 t - 530229868 t + 73670122 t + 303033938 t 25 27 13 15 / - 54310193 t + 1236948 t + 226401516 t - 577009977 t ) / (( / 21 20 19 18 17 49419 t + 342873 t - 1029123 t - 3790296 t + 2534643 t 16 15 14 13 12 + 11278242 t + 1487915 t - 12207666 t - 6602517 t + 4290952 t 11 10 9 8 7 6 + 4086195 t - 192474 t - 990460 t - 155925 t + 110286 t + 30770 t 5 4 3 2 - 5565 t - 2313 t + 103 t + 78 t - 1) 6 5 4 3 2 (3 t + 18 t + 15 t - 34 t - 30 t + 12 t - 1) (-1 + 3 t) (1 + t)) In Maple input format it is: (620633898*t^17+14*t-1+6426456*t^9-941*t^3+607*t^4+22*t^2+29117*t^5-26044*t^6-\ 539884*t^7+298032*t^8-82656*t^10-26227929*t^12+236892895*t^14+1690100338*t^18-\ 920688786*t^16-1394559224*t^20+478776605*t^22-37540871*t^24-7210248*t^26-\ 48872218*t^11+222972*t^28-530229868*t^21+73670122*t^19+303033938*t^23-54310193* t^25+1236948*t^27+226401516*t^13-577009977*t^15)/(49419*t^21+342873*t^20-\ 1029123*t^19-3790296*t^18+2534643*t^17+11278242*t^16+1487915*t^15-12207666*t^14 -6602517*t^13+4290952*t^12+4086195*t^11-192474*t^10-990460*t^9-155925*t^8+ 110286*t^7+30770*t^6-5565*t^5-2313*t^4+103*t^3+78*t^2-1)/(3*t^6+18*t^5+15*t^4-\ 34*t^3-30*t^2+12*t-1)/(-1+3*t)/(1+t) The first, 30, terms of the enumerating sequence (staring at n=1) are [0, 5, 12, 92, 440, 2855, 16940, 109885, 706704, 4690555, 31336910, 212453394, 1451520200, 10004676487, 69405575382, 484465584931, 3399099652256, 23960007499098, 169578465693860, 1204555106080513, 8583595725964080, 61339860884731723, 439444146176305112, 3155191039972392327, 22698368071456737080, 163572069732411470044, 1180533867515059911828, 8531431345285871758261, 61725962778998304150332, 447046810285565899015809] K(n) is asymptotically n 0.00560249218856760687437854337293 7.29085936938158960662122241042 Theorem 5': Let K1(n) be the number of ways a King can walk n steps on the, 8, by , 8, chessboard, starting at its initial location, (first row, fifth column) never getting off the board, but with no other pieces in its way, and ENDING UP ANYWHERE ON THE BOARD. We have: infinity ----- \ n ) K1(n) t = / ----- n = 0 9 8 7 6 5 4 3 2 24 t + 9 t - 258 t - 437 t - 99 t + 143 t + 41 t - 20 t - 4 t + 1 - ------------------------------------------------------------------------- 6 5 4 3 2 4 3 (9 t + 27 t + 9 t - 33 t - 27 t - 3 t + 1) (9 t - 30 t + 6 t - 1) In Maple input format it is: -(24*t^9+9*t^8-258*t^7-437*t^6-99*t^5+143*t^4+41*t^3-20*t^2-4*t+1)/(9*t^6+27*t^ 5+9*t^4-33*t^3-27*t^2-3*t+1)/(9*t^4-30*t^3+6*t-1) The first, 30, terms of the enumerating sequence (staring at n=1) are [5, 34, 233, 1643, 11649, 83422, 600507, 4341771, 31477752, 228655539, 1663045965, 12105752949, 88169340024, 642392246961, 4681505156193, 34122264768486, 248733358430445, 1813254938673615, 13219115909165469, 96373618897421214, 702622249582559715, 5122604595906712863, 37347640467477414156, 272293780666380682815, 1985243223624732727353, 14474069965893812987673, 105528126944060093270088, 769389392611564697866113, 5609503482915566328751485, 40898070670210028785502010] K1(n) is asymptotically n 0.534983729487404503718695439592 7.29085936938158960662122241042 -------------------------------------------------------------------------------------------------------- This took, 117.322, seconds