A079280 Number of log-concave paths of length n starting from the origin (0,0) with steps from {N=(0,1), E=(1,0) and S=(0,-1)} that stay in the second octant and never touch the line y=x except possibly at the beginning or the end.

1, 2, 2, 5, 7, 17, 26, 62, 99, 233, 382, 890, 1486, 3434, 5812, 13340, 22819, 52073, 89846, 204002, 354522, 801422, 1401292, 3155300, 5546382, 12444842, 21977516, 49155332, 87167164, 194392628, 345994216, 769547192, 1374282019, 3049104233

Offset

1,2

Comments

The first S step can only come after an E step.

Links

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

Formula

G.f.: (1-x)/(2-4*x) + (1+3*x)/(2*sqrt(1-4*x^2));

a(2n) = (1/2)*(4^(n-1) + 3*binomial(2n-2, n-1));

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

Crossrefs

Sequence in context: A127413 A145344 A034438 * A038750 A356434 A300439

Adjacent sequences: A079277 A079278 A079279 * A079281 A079282 A079283

Keyword

nonn

Author

Wenjin Woan, Feb 07 2003

Extensions

More terms from Max Alekseyev, Jul 04 2009

Status

approved