login
Number of ways to move a chess queen from the lower left corner to square (n,n), with the queen moving only up, right, or diagonally up-right.
3

%I #28 Sep 23 2024 04:22:54

%S 1,3,22,188,1712,16098,154352,1499858,14717692,145509218,1447187732,

%T 14462966928,145120265472,1461040916988,14751839744412,

%U 149316973768398,1514654852648052,15393833895932658,156716528008129892,1597861126366223768

%N Number of ways to move a chess queen from the lower left corner to square (n,n), with the queen moving only up, right, or diagonally up-right.

%C Main diagonal of the square array given in A132439.

%C a(n) is the number of Wythoff's Nim games starting with two equal piles of n stones. - Martin J. Erickson (erickson(AT)truman.edu), Dec 05 2008

%H Alois P. Heinz, <a href="/A132595/b132595.txt">Table of n, a(n) for n = 1..300</a>

%H M. Erickson, S. Fernando, K. Tran, <a href="https://www.semanticscholar.org/paper/Enumerating-Rook-and-Queen-Paths-Erickson-Fernando/fc8d32756ec73ccae8b28ad93431c13c571c6f10">Enumerating Rook and Queen Paths</a> , Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 37-48.

%F G.f.: (x*(x-1)/(3*x-2))*(1 + (1-x)/sqrt(1 - 12*x + 16*x^2)). a(n) is asymptotic to (5^(3/4)*(sqrt(5)-2)/16)*(6+2*sqrt(5))^n/sqrt(Pi*n).

%F a(1)=1; a(2)=3; a(3)=22; a(4)=188; a(n) = ((29*n-47)*a(n-1) + (-95*n + 238)*a(n-2) + (116*n - 418)*a(n-3) + (-48*n + 240)*a(n-4))/(2*n-2), n >= 5. - Martin J. Erickson (erickson(AT)truman.edu), Nov 20 2007

%e a(2) = 3 since the paths from (1,1) to (2,2) are

%e (1,1)->(2,1)->(2,2),

%e (1,1)->(1,2)->(2,2),

%e (1,1)->(2,2).

%t Rest[CoefficientList[Series[(x (x-1)/(3x-2))(1+(1-x)/Sqrt[1-12x+16x^2]),{x,0,20}],x]] (* _Harvey P. Dale_, Feb 09 2015 *)

%Y Cf. A132439.

%Y Column k=2 of A229345.

%K nonn,easy,nice

%O 1,2

%A Martin J. Erickson (erickson(AT)truman.edu), Nov 14 2007, Jan 28 2009