

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


2



1, 6, 222, 9918, 486924, 25267236, 1359631776, 75059524392, 4223303759148, 241144782230124, 13930829740017132, 812470444305924300, 47760356825349969600, 2826309951801018736800, 168207011284961649886800, 10060178088232285063542768, 604273284101165691102038556
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

Table of n, a(n) for n=1..17.
M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating HighDimensional Rook Walks, (arXiv:1011.4671).


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*x2)/(4*x1)^3)/((4*x1)*(64*x1)),x) [From Mark van Hoeij, Dec 10 2009]
Asymptotic (Frederic Chyzak, 2010): 9*sqrt(3)/(40*Pi*n)*64^(n1)


EXAMPLE

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


CROSSREFS

Cf. A051708.
Row d=3 of A181731.
Sequence in context: A015477 A144658 A203637 * A061610 A054324 A117255
Adjacent sequences: A144042 A144043 A144044 * A144046 A144047 A144048


KEYWORD

nonn


AUTHOR

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


STATUS

approved



