|
| |
|
|
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 consecutive-123-avoiding stack followed by a classical-21-avoiding 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), 291-301.
|
|
|
FORMULA
|
a(n) = Sum_{b = 1..(n+1)/2) C(n, 2b-1)*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(i-1)| <= 1 for i >= 2, Also T(n, n), where T is the array defined in A026105.
D-finite with recurrence: (n+3)*a(n) +(-3*n-4)*a(n-1) +(-n-1)*a(n-2) +3*(n-2)*a(n-3)=0. - R. J. Mathar, Dec 03 2012
G.f.: A(z) satisfies z*A(z) = (1-z)*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(n-1) + a(n-2) + Sum_{k=0..n-3} a(k) * a(n-k-3). - 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/(1-x+Sqrt[1-2x-3x^2])^2, {x, 0, 30}], x] (* Harvey P. Dale, Jul 18 2011 *)
a[n_] := n*Hypergeometric2F1[(1-n)/2, 1-n/2, 3, 4]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 13 2012 *)
|
|
|
PROG
|
(PARI) my(z='z+O('z^66)); concat(0, Vec(4*z/(1-z+sqrt(1-2*z-3*z^2))^2)) \\ Joerg Arndt, Mar 08 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
