OFFSET
0,2
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.9 Polya's random walk constants, p. 326.
LINKS
Eric Weisstein's MathWorld, Polya's Random Walk Constants
FORMULA
a(n) = sum_{k=0..n} (2n)!*(2k)!/((n-k)!*(n+1-k)!*k!^2*(k+1)!^2).
a(n) = C(n) * 3F2(1/2, -n-1, -n; 2, 2; 4) where C(n) is the n-th Catalan number and 3F2 the hypergeometric function.
a(n) ~ 2^(2*n-4) * 3^(2*n+9/2) / (Pi^(3/2) * n^(9/2)). - Vaclav Kotesovec, Nov 13 2014
Recurrence: n*(n+2)^2*a(n) = 2*(2*n-1)*(10*n^2 + 2*n - 3)*a(n-1) - 36*(n-1)*(2*n-3)*(2*n-1)*a(n-2). - Vaclav Kotesovec, May 14 2016
EXAMPLE
For 2n=4, the 12 acceptable walks are:
(0, 0, -1), (0, -1, -1), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (0, 0, 0), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (0, 0, 0), (1, 0, 0), (0 ,0, 0);
(0, 0, -1), (1, 0, -1), (0, 0, -1), (0 ,0, 0);
(0, 0, -1), (1, 0, -1), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (0, -1, -1), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (0, 0, 0), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (0, 0, 0), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (1, 0, -1), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (1, 0, -1), (1, 0, 0), (0 ,0, 0);
(1, 0, 0), (1, 1, 0), (0, 0, -1), (0 ,0, 0);
(1, 0, 0), (1, 1, 0), (1, 0, 0), (0 ,0, 0).
MATHEMATICA
a[n_] := CatalanNumber[n]*HypergeometricPFQ[{1/2, -n-1, -n}, {2, 2}, 4]; Table[a[n], {n, 0, 20}]
CROSSREFS
KEYWORD
nonn,walk,easy
AUTHOR
Jean-François Alcover, Nov 12 2014
STATUS
approved