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

Author

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

Keywords

• nonn

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

Crossrefs

Cf. A000957, A217312, A257363.

Programs

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 *)

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 */

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