A144045 Number of paths of a chess Rook in a cube, from (1,1,1) to (n,n,n), where the rook may move in steps that are multiples of (1,0,0), (0,0,1), or (0,0,1).

1, 6, 222, 9918, 486924, 25267236, 1359631776, 75059524392, 4223303759148, 241144782230124, 13930829740017132, 812470444305924300, 47760356825349969600, 2826309951801018736800, 168207011284961649886800, 10060178088232285063542768, 604273284101165691102038556

Offset: 1

Author

Martin J. Erickson (erickson(AT)truman.edu), Sep 08 2008

Keywords

• nonn

Examples

			a(2)=6 because there are 6 Rook paths from (1,1,1) to (2,2,2).
G.f. = x + 6*x^2 + 222*x^3 + 9918*x^4 + 486924*x^5 + 25267236*x^6 + ...
		

Links

• Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
• M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.

Crossrefs

Cf. A051708.

Row d=3 of A181731.

Formula

a(n) satisfies the recurrence relation a(1) = 1; a(2) = 6; a(3) = 222; a(4) = 9918; a(n) = ((-121 n^3 + 575n^2 - 872n + 412)a(n - 1) + (-475n^3 + 4887n^2 - 16202n + 17448)a(n - 2) + (1746n^3 - 19818n^2 + 75060n - 94896)a(n - 3) + (-1152n^3 + 16128n^2 - 74880n + 115200)a(n - 4))/(-(2n^3 - 8n^2 + 10n - 4)), n>= 5.

G.f.: 1+int(6*hypergeom([1/3, 2/3],[2],27*x*(3*x-2)/(4*x-1)^3)/((4*x-1)*(64*x-1)),x). [Mark van Hoeij, Dec 10 2009]

Asymptotics: a(n) ~ 9*sqrt(3)/(40*Pi*n)*64^(n-1). - Frederic Chyzak, 2010