|
%I #84 Oct 27 2023 21:41:56
%S 1,8,168,5840,261800,13180608,702273264,38641656768,2171652448680,
%T 123938999632448,7158206751686848,417418594698260064,
%U 24535017440445455216,1451786144317963971200,86396682439552099487040,5166936574734171792925440,310340697572034456203934120
%N Number of 2n-move closed knight paths on an unbounded chessboard from a given square to the same square.
%C Every move changes the color of the square the knight is on, so there is no returning path of odd length.
%H Alois P. Heinz, <a href="/A254129/b254129.txt">Table of n, a(n) for n = 0..550</a> (first 85 terms from David A. Corneth)
%H Shalosh B. Ekhad and Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/chesswalks.html">In How Many Ways Can the Chess Pieces Walk n Steps, Staying on the Board?</a>, May 19 2011; <a href="/A254129/a254129.pdf">Local copy, pdf file only, no active links</a>
%H Mohamud Mohammed and Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/SMAZ">Maple program SMAZ</a>; <a href="/A254129/a254129.txt">Local copy</a>
%H Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/inSMAZ6">Input file inSMAZ6</a>; <a href="/A254129/a254129_1.txt">Local copy</a>
%H Doron Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oSMAZ6">Output from Maple program SMAZ</a>; <a href="/A254129/a254129_2.txt">Local copy</a>
%F From _Robert Israel_, Jan 26 2015: (Start)
%F a(n) = 4^n * (2*Pi)^(-2) * int_0^(2*Pi) int_0^(2*Pi) ds dt (cos(s+2*t)+cos(s-2*t)+cos(2*s+t)+cos(2*s-t))^(2*n).
%F G.f.: (2*Pi)^(-2) * int_0^(2*Pi) int_0^(2*Pi) ds dt 1/(1 - 4*x*(cos(s+2*t)+cos(s-2*t)+cos(2*s+t)+cos(2*s-t))^2).
%F (End)
%F a(n) ~ 64^n / (5*Pi*n). - _Vaclav Kotesovec_, Jan 28 2015
%F Recurrence (conjectured): 3*n^2*(3*n-2)*(3*n-1)*(4*n-3)*(4*n-1)*(58625*n^6 - 574525*n^5 + 2317575*n^4 - 4929815*n^3 + 5836090*n^2 - 3647730*n + 940788)*a(n) = 4*(563444875*n^12 - 7212094400*n^11 + 40894216825*n^10 - 135653664390*n^9 + 292742658975*n^8 - 432166599360*n^7 + 446527351283*n^6 - 324481592710*n^5 + 164046706898*n^4 - 56035458036*n^3 + 12203976528*n^2 - 1507156200*n + 78246000)*a(n-1) - 64*(n-1)*(2*n-3)^2*(167726125*n^9 - 1643716025*n^8 + 6735239425*n^7 - 15048594215*n^6 + 20072439970*n^5 - 16473493280*n^4 + 8273936628*n^3 - 2437948332*n^2 + 377982648*n - 22556880)*a(n-2) + 165888*(n-2)*(n-1)*(2*n - 5)^2*(2*n - 3)^2*(58625*n^6 - 222775*n^5 + 324325*n^4 - 232265*n^3 + 86220*n^2 - 15570*n + 1008)*a(n-3). - _Vaclav Kotesovec_, Jan 30 2015
%F a(n) = the constant term in the expansion of (x^2*y + x*y^2 + y^2/x + y/x^2 + 1/(x^2*y) + 1/(y^2*x) + x/y^2 + x^2/y)^(2*n). - _Peter Bala_, Feb 14 2017
%F The conjectured recurrence of _Vaclav Kotesovec_ is true. Running the input file inSMAZ6 (see Links) on the Maple program SMAZ gives the recurrence followed by the certificate shown in the output file oSMAZ6. - _Doron Zeilberger_, Mar 29 2019
%e a(1) = 8. For illustration, let's assume we're on a usual 8 X 8 chessboard, with the knight initially at D4. Then there are 8 paths bringing it back to D4 in 2 moves:
%e D4-E6-D4; D4-F5-D4; D4-F3-D4; D4-E2-D4; D4-C2-D4; D4-B3-D4; D4-B5-D4; D4-C6-D4.
%p G:= cos(x+2*y)+cos(x-2*y)+cos(2*x+y)+cos(2*x-y):
%p F:= 1: a[0]:= 1:
%p for n from 1 to 20 do
%p F:= combine(F*G^2,trig);
%p a[n]:= 4^n*remove(has,F,cos);
%p od:
%p seq(a[n],n=0..20); # _Robert Israel_, Jan 26 2015
%p # second Maple program:
%p b:= proc(n, x, y) option remember; `if`(max(x, y)>2*n or x+y>3*n, 0,
%p `if`(n=0, 1, add(b(n-1, abs(x+l[1]), abs(y+l[2])), l=[[1, 2],
%p [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]])))
%p end:
%p a:= n-> b(2*n, 0$2):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jan 29 2015
%t b[n_, x_, y_] := b[n, x, y] = If[Max[x, y] > 2n || x+y > 3n, 0, If[n == 0, 1, Sum[b[n-1, Abs[x+l[[1]]], Abs[y+l[[2]]]], {l, {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}}}]]];
%t a[n_] := b[2n, 0, 0];
%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Apr 30 2019, after _Alois P. Heinz_ *)
%o (PARI) a(n)={my(l=listcreate(),v=vector(2*n+1));m=matrix(1,1);m[1,1]=1;listput(l,m);v[1]=1;for(i=2,2*n+1, m=matrix(4*i-3,4*i-3);for(j=1,#l[i-1],for(k=1,#l[i-1],m[j+2-2,k+2-1]+=l[i-1][j,k];m[j+2-2,k+2+1]+=l[i-1][j,k];m[j+2-1,k+2-2]+=l[i-1][j,k];m[j+2-1,k+2+2]+=l[i-1][j,k];m[j+2+1,k+2-2]+=l[i-1][j,k];m[j+2+1,k+2+2]+=l[i-1][j,k];m[j+2+2,k+2-1]+=l[i-1][j,k];m[j+2+2,k+2+1]+=l[i-1][j,k]));v[i]=m[2*i-1,2*i-1];listput(l,m););listput(l,v);v[#v]} \\ _David A. Corneth_, Jan 26 2015
%o (PARI) {a(n) = polcoef(polcoef((x^2*y+x*y^2+y^2/x+y/x^2+1/(x^2*y)+1/(x*y^2)+x/y^2+x^2/y)^(2*n), 0), 0)} \\ _Seiichi Manyama_, Nov 02 2019
%Y Cf. A025600, A094061, A253974, A254459, A307347.
%K nonn,easy
%O 0,2
%A _David A. Corneth_, Jan 25 2015
|
