A253831 Number of 2-Motzkin paths with no level steps at height 1.

1, 2, 5, 12, 30, 76, 197, 522, 1418, 3956, 11354, 33554, 102104, 319608, 1027237, 3381714, 11371366, 38946892, 135505958, 477781296, 1703671604, 6132978608, 22256615602, 81327116484, 298938112816, 1104473254912, 4098996843500, 15272792557230, 57106723430892, 214202598271360, 805743355591301

Offset

0,2

Comments

For n=3 we have 12 paths: H(1)H(1)H(1), H(1)H(1)H(2), H(1)H(2)H(1), H(1)H(2)H(2), H(2)H(1)H(1), H(2)H(1)H(2), H(2)H(2)H(1), H(2)H(2)H(2), UDH(1), UDH(2), H(1)UD, H(2)UD.

Links

Robert Israel, Table of n, a(n) for n = 0..1000

Formula

G.f.: 1/(1-2*x-x*F(x)), where F(x) is the g.f. of Fine numbers A000957.

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

a(n) ~ 4^(n+1) / (25*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 21 2015

(54+36*n)*a(n)+(-3+7*n)*a(n+1)+(-60-36*n)*a(n+2)+(36+16*n)*a(n+3)+(-6-2*n)*a(n+4) = 0. - Robert Israel, Apr 29 2015

a(n) = Sum_{m=1..n/2}(Sum_{j=0..n-2*m}(((Sum_{k=0..j}((k+1)*binomial(k+m,k+1)*binomial(2*j-k+m-1,j-k)*(-1)^(k)))*2^(n-j-2*m)*binomial(n-m-j,m))/(j+m)))+2^n. - Vladimir Kruchinin, Mar 11 2016

Maple

rec:= (54+36*n)*a(n)+(-3+7*n)*a(n+1)+(-60-36*n)*a(n+2)+(36+16*n)*a(n+3)+(-6-2*n)*a(n+4) = 0:
f:= gfun:-rectoproc({rec, seq(a(i)=[1, 2, 5, 12][i+1], i=0..3)}, a(n), remember):
seq(f(n), n=0..100); # Robert Israel, Apr 29 2015

Mathematica

CoefficientList[Series[1/(1-2*x-x*((1-Sqrt[1-4*x])/(3-Sqrt[1-4*x]))), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 21 2015 *)

Prog

(Maxima)
a(n):=sum(sum(((sum((k+1)*binomial(k+m, k+1)*binomial(2*j-k+m-1, j-k)*(-1)^(k), k, 0, j))*2^(n-j-2*m)*binomial(n-m-j, m))/(j+m), j, 0, n-2*m), m, 1, n/2)+2^n; /* Vladimir Kruchinin, Mar 11 2016 */

Crossrefs

Cf. A000957, A217312, A257363.

Sequence in context: A002026 A026938 A086622 * A024851 A188378 A145267

Adjacent sequences: A253828 A253829 A253830 * A253832 A253833 A253834

Keyword

nonn

Author

José Luis Ramírez Ramírez, Apr 20 2015

Status

approved