

A132595


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 upright.


3



1, 3, 22, 188, 1712, 16098, 154352, 1499858, 14717692, 145509218, 1447187732, 14462966928, 145120265472, 1461040916988, 14751839744412, 149316973768398, 1514654852648052, 15393833895932658, 156716528008129892, 1597861126366223768
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Main diagonal of the square array given in A132439.
Recurrence relation: a_1=1; a_2=3; a_3=22; a_4=188; a_n=((29n47)a_{n1}+(95n+238)a_{n2}+(116n418)a_{n3}+(48n+240)a_{n4})/(2n2), n >= 5.  Martin J. Erickson (erickson(AT)truman.edu), Nov 20 2007
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


REFERENCES

M. Erickson, S. Fernando, K. Tran, Enumerating Rook and Queen Paths, Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 3748.  Martin J. Erickson (erickson(AT)truman.edu), Oct 21 2010


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..300


FORMULA

G.f.: (x(x1)/(3x2))(1+(1x)/sqrt(112x+16x^2)). a(n) is asymptotic to (5^(3/4)(sqrt(5)2)/16)(6+2sqrt(5))^n/(sqrt(pi n).


EXAMPLE

a(2) = 3 since the paths from (1,1) to (2,2) are
(1,1)>(2,1)>(2,2),
(1,1)>(1,2)>(2,2),
(1,1)>(2,2).


CROSSREFS

Cf. A132439.
Column k=2 of A229345.
Sequence in context: A077244 A138899 A147855 * A065204 A001393 A046743
Adjacent sequences: A132592 A132593 A132594 * A132596 A132597 A132598


KEYWORD

nonn,easy,nice


AUTHOR

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


STATUS

approved



