login
A126223
Number of level steps in all 2-Motzkin paths (i.e., Motzkin paths with blue and red level steps) of length n, without red level steps on the x-axis.
3
0, 1, 2, 7, 26, 98, 372, 1419, 5434, 20878, 80444, 310726, 1202852, 4665412, 18126760, 70538355, 274877370, 1072515990, 4189573740, 16383007410, 64126407180, 251226790620, 985033185240, 3865138313790, 15176957307876, 59633260964748, 234453859803352
OFFSET
0,3
COMMENTS
a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 213 and 321 in the classical sense. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014
LINKS
FORMULA
a(n) = Sum_{k=0..n} k*A126222(n,k).
G.f.: (1-2z)(1-2z-sqrt(1-4*z))/(2z*sqrt(1-4z)).
a(n) = 2*(2*n-3)*(n^2-n+1)*a(n-1)/((n+1)*(n^2-3*n+3)) for n>1. - Alois P. Heinz, May 20 2014
a(n) = 2*(1-n+n^2) * C(2*n-2, n-1) / (n*(n+1)). - Vaclav Kotesovec, Sep 08 2014
EXAMPLE
a(3) = 7 because the 2-Motzkin paths without red level steps on the x-axis are BBB, BUD, UBD, URD and UDB, where U=(1,1), D=(1,-1), B=blue (1,0), R=red (1,0); they have a total of 3+1+1+1+1 = 7 level steps.
MAPLE
G:=(1-2*z)*(1-2*z-sqrt(1-4*z))/2/z/sqrt(1-4*z): Gser:=series(G, z=0, 32): seq(coeff(Gser, z, n), n=0..28);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
2*(2*n-3)*(n^2-n+1)*a(n-1)/((n+1)*(n^2-3*n+3)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, May 20 2014
MATHEMATICA
CoefficientList[Series[(1-2*x)*(1-2*x-Sqrt[1-4*x])/(2*x*Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 08 2014 *)
Flatten[{0, Table[2*(1-n+n^2) * Binomial[2*n-2, n-1]/(n*(n+1)), {n, 1, 25}]}] (* Vaclav Kotesovec, Sep 08 2014 *)
CROSSREFS
Cf. A126222.
Sequence in context: A001075 A293210 A113436 * A369231 A369489 A273320
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 28 2006
STATUS
approved