|
%I M1416 N0554 #137 Jul 30 2024 01:53:36
%S 0,1,2,5,12,30,76,196,512,1353,3610,9713,26324,71799,196938,542895,
%T 1503312,4179603,11662902,32652735,91695540,258215664,728997192,
%U 2062967382,5850674704,16626415975,47337954326,135015505407,385719506620,1103642686382,3162376205180,9073807670316,26068895429376
%N Generalized ballot numbers (first differences of Motzkin numbers).
%C Number of ordered trees with n+1 edges, having root of degree 2 and nonroot nodes of outdegree at most 2.
%C Sequence without the initial 0 is the convolution of the sequence of Motzkin numbers (A001006) with itself.
%C 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).
%C 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).
%C a(n) = number of Motzkin paths of length n+1 that start with an up step. - _David Callan_, Jul 19 2004
%C 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
%C 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002026/b002026.txt">Table of n, a(n) for n = 0..500</a>
%H Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="http://math.colgate.edu/~integers/t46/t46.Abstract.html">Motzkin paths with a restricted first return decomposition</a>, Integers (2019) Vol. 19, A46.
%H L. Carlitz, <a href="http://www.jstor.org/stable/2099558">Solution of certain recurrences</a>, SIAM J. Appl. Math., 17 (1969), 251-259.
%H J. B. Cosgrave, <a href="/A103772/a103772.txt">The Gauss-Factorial Motzkin connection</a> (Maple worksheet, change suffix to .mw)
%H R. De Castro, A. L. Ramírez and J. L. Ramírez, <a href="http://arxiv.org/abs/1310.2499">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [hep-ph], 2013.
%H Wun-Seng Chou, Tian-Xiao He, and Peter J.-S. Shiue, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/He/he61.html">On the Primality of the Generalized Fuss-Catalan Numbers</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.1.
%H Colin Defant and Kai Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.
%H R. Donaghey and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, 23 (1977), 291-301.
%H Gennady Eremin, <a href="https://arxiv.org/abs/1911.01673">Arithmetic on Balanced Parentheses: The case of Ordered Motzkin Words</a>, arXiv:1911.01673 [math.CO], 2019. See p. 2.
%H Gennady Eremin, <a href="https://arxiv.org/abs/2002.08067">Generating function for Naturalized Series: The case of Ordered Motzkin Words</a>, arXiv:2002.08067 [math.CO], 2020.
%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See pp. 19, 21.
%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H Anthony J. Guttmann and Iwan Jensen, <a href="https://arxiv.org/abs/2208.06744">Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices</a>, arXiv:2208.06744 [math-ph], 2022; Journal of Physics A: Mathematical and Theoretical 55 012345, (33pp).
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.
%H J. A. Sharp and N. J. A. Sloane, <a href="/A002026/a002026.pdf">Correspondence, 1977</a>
%F a(n) = A001006(n+1) - A001006(n).
%F a(n) = Sum_{b = 1..(n+1)/2} C(n, 2b-1)*C(2b, b)/(b+1).
%F 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.
%F a(n) = Sum_{k=0..n-1} Sum_{i=0..k} C(k, 2i)*A000108(i+1). - _Paul Barry_, Jul 18 2003
%F G.f.: 4*z/(1-z+sqrt(1-2*z-3*z^2))^2. - _Emeric Deutsch_, Dec 27 2003
%F a(n) = A005043(n+2) - A005043(n). - _Paul Barry_, Apr 17 2005
%F 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
%F a(n) ~ 3^(n+3/2) / (sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Feb 01 2014
%F 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
%F 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
%F 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
%t CoefficientList[Series[4x/(1-x+Sqrt[1-2x-3x^2])^2,{x,0,30}],x] (* _Harvey P. Dale_, Jul 18 2011 *)
%t 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 *)
%o (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
%Y Cf. A001006, A026300, A026107, row sums of A348840 and of A348869.
%Y A diagonal of triangle A020474.
%Y See A244884 for a variant.
%K nonn,easy,nice,changed
%O 0,3
%A _N. J. A. Sloane_
%E Additional comments from _Emeric Deutsch_, Dec 27 2003
|
