A245067 Number of three-dimensional random walks with 2n steps in the wedge region x >= y >= z, beginning and ending at the origin without crossing the wedge boundary.

1, 2, 12, 120, 1610, 25956, 474012, 9475752, 202921290, 4587734580, 108376022040, 2654745191280, 67043341981980, 1737717447946200, 46062204663294000, 1245096242017227360, 34239776369652506970, 956050033694583839220

Offset

0,2

References

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.9 Polya's random walk constants, p. 326.

Links

Table of n, a(n) for n=0..17.

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

Cf. A000108, A002896, A086230, A086231.

Sequence in context: A302702 A189981 A326000 * A052680 A096317 A226760

Adjacent sequences: A245064 A245065 A245066 * A245068 A245069 A245070

Keyword

nonn,walk,easy

Author

Jean-François Alcover, Nov 12 2014

Status

approved