A145600 a(n) is the number of walks from (0,0) to (0,1) that remain in the upper half-plane y >= 0 using (2*n - 1) unit steps either up (U), down (D), left (L) or right (R).

1, 8, 75, 784, 8820, 104544, 1288287, 16359200, 212751396, 2821056160, 38013731756, 519227905728, 7174705330000, 100136810390400, 1409850293610375, 20002637245262400, 285732116760449700

Offset

1,2

Comments

Cf. A000891, which enumerates walks in the upper half-plane starting and finishing at the origin. See also A145601, A145602 and A145603. This sequence is the central column taken from triangle A145596, which enumerates walks in the upper half-plane starting at the origin and finishing on the horizontal line y = 1.

References

M. Dukes and Y. Le Borgne, Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q,t-Narayana polynomial, Journal of Combinatorial Theory, Series A, Volume 120, Issue 4, May 2013, Pages 816-842. - From N. J. A. Sloane, Feb 21 2013

Links

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

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

Formula

a(n) = 1/n*binomial(2*n,n+1)*binomial(2*n,n-1).

a(n) = A135389(n-1)/(n+1). - R. J. Mathar, Jul 14 2013

D-finite with recurrence (n+1)^2*a(n) -4*n*(5*n-1)*a(n-1) +16*(2*n-3)^2*a(n-2)=0. - R. J. Mathar, Jul 14 2013

Example

a(2) = 8: the 8 walks from (0,0) to (0,1) of three steps are
UDU, UUD, URL, ULR, RLU, LRU, RUL and LUR.

Maple

a(n) := 1/n*binomial(2*n, n+1)*binomial(2*n, n-1);
seq(a(n), n = 1..19);

Crossrefs

Cf. A000891, A145596, A145601, A145602, A145603.

Sequence in context: A288487 A123003 A015578 * A268085 A231617 A094735

Adjacent sequences: A145597 A145598 A145599 * A145601 A145602 A145603

Keyword

easy,nonn

Author

Peter Bala, Oct 14 2008

Status

approved