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.

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

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

Cf. A126222.

Sequence in context: A001075 A293210 A113436 * A369231 A369489 A273320

Adjacent sequences: A126220 A126221 A126222 * A126224 A126225 A126226

Keyword

nonn

Author

Emeric Deutsch, Dec 28 2006

Status

approved