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
Alois P. Heinz, Table of n, a(n) for n = 0..1000
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 28 2006
STATUS
approved