

A002026


Generalized ballot numbers (first differences of Motzkin numbers).
(Formerly M1416 N0554)


35



0, 1, 2, 5, 12, 30, 76, 196, 512, 1353, 3610, 9713, 26324, 71799, 196938, 542895, 1503312, 4179603, 11662902, 32652735, 91695540, 258215664, 728997192, 2062967382, 5850674704, 16626415975, 47337954326, 135015505407, 385719506620, 1103642686382, 3162376205180, 9073807670316, 26068895429376
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of ordered trees with n+1 edges, having root of degree 2 and nonroot nodes of outdegree at most 2.
Sequence without the initial 0 is the convolution of the sequence of Motzkin numbers (A001006) with itself.
Number of horizontal steps at level zero in all Motzkin paths of length n. Example: a(3)=5 because in the four Motzkin paths of length 3, (HHH), (H)UD, UD(H) and UHD, where H=(1,0), U=(1,1), D=(1,1), we have altogether five horizontal steps H at level zero (shown in parentheses).
Number of peaks at level 1 in all Motzkin paths of length n+1. Example: a(3)=5 because in the nine Motzkin paths of length 4, HHHH, HH(UD), H(UD)H, HUHD, (UD)HH, (UD)(UD), UHDH, UHHD and UUDD (where H=(1,0), U=(1,1), D=(1,1)), we have five peaks at level 1 (shown between parentheses).
a(n) = number of Motzkin paths of length n+1 that start with an up step.  David Callan, Jul 19 2004
Could be called a Motzkin transform of A130716 because the g.f. is obtained from the g.f. x*A130716(x)= x(1+x+x^2) (offset changed to 1) by the substitution x > x*A001006(x) of the independent variable.  R. J. Mathar, Nov 08 2008
For n >= 1, a(n) is the number of length n permutations sorted to the identity by a consecutive123avoiding stack followed by a classical21avoiding stack.  Kai Zheng, Aug 28 2020


REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291301.


FORMULA

a(n) = Sum_{b = 1..(n+1)/2) C(n, 2b1)*C(2b, b)/(b+1).
Number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer, s(0) = 0 = s(n), s(1) = 1, s(i)  s(i1) <= 1 for i >= 2, Also T(n, n), where T is the array defined in A026105.
Dfinite with recurrence: (n+3)*a(n) +(3*n4)*a(n1) +(n1)*a(n2) +3*(n2)*a(n3)=0.  R. J. Mathar, Dec 03 2012
G.f.: A(z) satisfies z*A(z) = (1z)*M(z)  1, where M(z) is the g.f. of A001006.  Gennady Eremin, Feb 09 2021
a(0) = 0, a(1) = 1; a(n) = 2 * a(n1) + a(n2) + Sum_{k=0..n3} a(k) * a(nk3).  Ilya Gutkovskiy, Nov 09 2021
G.f.: x*M(x)^2 where M(x) = (1  x  sqrt(1  2*x  3*x^2)) / (2*x^2) is the g.f. of the Motzkin numbers A001006.  Peter Bala, Feb 05 2024


MATHEMATICA

CoefficientList[Series[4x/(1x+Sqrt[12x3x^2])^2, {x, 0, 30}], x] (* Harvey P. Dale, Jul 18 2011 *)
a[n_] := n*Hypergeometric2F1[(1n)/2, 1n/2, 3, 4]; Table[a[n], {n, 0, 26}] (* JeanFrançois Alcover, Aug 13 2012 *)


PROG

(PARI) my(z='z+O('z^66)); concat(0, Vec(4*z/(1z+sqrt(12*z3*z^2))^2)) \\ Joerg Arndt, Mar 08 2016


CROSSREFS



KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



