A268407 Number of North-East lattice paths that do not bounce off the diagonal y = x to the right.

1, 2, 5, 15, 48, 160, 548, 1914, 6785, 24335, 88109, 321521, 1181039, 4362855, 16195747, 60379623, 225955264, 848432824, 3195394520, 12067450014, 45685766306, 173350890788, 659126407978, 2510942564760, 9582235262428, 36627111558850, 140214938146148

Offset

0,2

Comments

This sequence is related to paired pattern P_2 in Pan and Remmel's link.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

Formula

G.f.: 2 (-1 + f(x) + x)/(1 - f(x) + (-5 + f(x))*x), where f(x) = sqrt(1 - 4*x).

a(n):= Sum_{k=0..n}((k+1)*fib(k)*binomial(2*n-k,n-k))/(n+1) + C(n), where fib(n) - Fibonacci numbers, C(n) - Catalan numbers. - Vladimir Kruchinin, Feb 27 2016

a(n) ~ 13*4^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 27 2016

Mathematica

CoefficientList[Series[2 (-1 + Sqrt[1 - 4 x] + x) / (1 - Sqrt[1 - 4 x] + (-5 + Sqrt[1 - 4 x]) x), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 04 2016 *)

Prog

(Maxima) a(n):=sum((k+1)*fib(k)*binomial(2*n-k, n-k), k, 0, n)/(n+1)+binomial(2*n, n)/(n+1); /* Vladimir Kruchinin, Feb 27 2016 */

Crossrefs

Cf. A000045, A000108.

Sequence in context: A301994 A289589 A071739 * A261003 A365268 A366041

Adjacent sequences: A268404 A268405 A268406 * A268408 A268409 A268410

Keyword

nonn

Author

Ran Pan, Feb 04 2016

Status

approved