A348869 -id:A348869 - cp's OEIS frontend

A002026 Generalized ballot numbers (first differences of Motzkin numbers).

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

Offset: 0

N. J. A. Sloane

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

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).

T. D. Noe, Table of n, a(n) for n = 0..500
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Motzkin paths with a restricted first return decomposition, Integers (2019) Vol. 19, A46.
L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259.
J. B. Cosgrave, The Gauss-Factorial Motzkin connection (Maple worksheet, change suffix to .mw)
R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [hep-ph], 2013.
Wun-Seng Chou, Tian-Xiao He, and Peter J.-S. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.1.
Reinis Cirpons, James East, and James D. Mitchell, Transformation representations of diagram monoids, arXiv:2411.14693 [math.RA], 2024. See pp. 3, 33.
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
Gennady Eremin, Arithmetic on Balanced Parentheses: The case of Ordered Motzkin Words, arXiv:1911.01673 [math.CO], 2019. See p. 2.
Gennady Eremin, Generating function for Naturalized Series: The case of Ordered Motzkin Words, arXiv:2002.08067 [math.CO], 2020.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 19, 21.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], 2022; Journal of Physics A: Mathematical and Theoretical 55 012345, (33pp).
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
J. A. Sharp and N. J. A. Sloane, Correspondence, 1977

Cf. A001006, A026300, A026107, row sums of A348840 and of A348869.
A diagonal of triangle A020474.
See A244884 for a variant.

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 *)

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

a(n) = A001006(n+1) - A001006(n).
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.
a(n) = Sum_{k=0..n-1} Sum_{i=0..k} C(k, 2i)*A000108(i+1). - Paul Barry, Jul 18 2003
G.f.: 4*z/(1-z+sqrt(1-2*z-3*z^2))^2. - Emeric Deutsch, Dec 27 2003
a(n) = A005043(n+2) - A005043(n). - Paul Barry, Apr 17 2005
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
a(n) ~ 3^(n+3/2) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 01 2014
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

Additional comments from Emeric Deutsch, Dec 27 2003

A086615 Antidiagonal sums of triangle A086614.

Original entry on oeis.org

1, 2, 4, 8, 17, 38, 89, 216, 539, 1374, 3562, 9360, 24871, 66706, 180340, 490912, 1344379, 3701158, 10237540, 28436824, 79288843, 221836402, 622599625, 1752360040, 4945087837, 13988490338, 39658308814, 112666081616

Offset: 0

Paul D. Hanna, Jul 24 2003

nonn

Partial sums of the Motzkin sequence (A001006). - Emeric Deutsch, Jul 12 2004
a(n) is the number of distinct ordered trees obtained by branch-reducing the ordered trees on n+1 edges. - David Callan, Oct 24 2004
a(n) is the number of consecutive horizontal steps at height 0 of all Motzkin paths from (0,0) to (n,0) starting with a horizontal step. - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007
This sequence (with offset 1 instead of 0) occurs in Section 7 of K. Grygiel, P. Lescanne (2015), see g.f. N. - N. J. A. Sloane, Nov 09 2015
Also number of plain (untyped) normal forms of lambda-terms (terms that cannot be further beta-reduced.) [Bendkowski et al., 2016]. - N. J. A. Sloane, Nov 22 2017
If interpreted with offset 2, the INVERT transform is A002026 with offset 1. - R. J. Mathar, Nov 02 2021

			a(0)=1, a(1)=2, a(2)=3+1=4, a(3)=4+4=8, a(4)=5+10+2=17, a(5)=6+20+12=38, are upward antidiagonal sums of triangle A086614:
{1},
{2,1},
{3,4,2},
{4,10,12,5},
{5,20,42,40,14},
{6,35,112,180,140,42}, ...
For example, with n=2, the 5 ordered trees (A000108) on 3 edges are
|...|..../\.../\.../|\..
|../.\..|......|........
|.......................
Suppressing nonroot vertices of outdegree 1 (branch-reducing) yields
|...|..../\.../\../|\..
.../.\.................
of which 4 are distinct. So a(2)=4.
a(4)=8 because we have HHHH, HHUD, HUDH, HUHD

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6
Maciej Bendkowski, K. Grygiel, and P. Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682, 2016
K. Grygiel and P. Lescanne, A natural counting of lambda terms, SOFSEM 2016. Preprint 2015

Cf. A086614 (triangle), A086616 (row sums), A348869 (Seq. Transf.).
Cf. A001006.
Cf. A136788.

A086615 := proc(n)
    option remember;
    if n <= 3 then
        2^n;
    else
        3*(-n-1)*procname(n-1) +(-n+4)*procname(n-2) +3*(n-1)*procname(n-3) ;
        -%/(n+2) ;
    end if;
end proc:
seq(A086615(n),n=0..20) ; # R. J. Mathar, Nov 02 2021

CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(2*x-2*x^2)/x, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 13 2014 *)

G.f.: A(x) = 1/(1-x)^2 + x^2*A(x)^2.
a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+1, 2k+1)*binomial(2k, k)/(k+1). - Paul Barry, Nov 29 2004
a(n) = n + 1 + Sum_k a(k-1)*a(n-k-1), starting from a(n)=0 for n negative. - Henry Bottomley, Feb 22 2005
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(j)*C(n-k, 2j). - Paul Barry, Aug 19 2005
From Paul Barry, May 31 2006: (Start)
G.f.: c(x^2/(1-x)^2)/(1-x)^2, c(x) the g.f. of A000108;
a(n) = Sum_{k=0..floor(n/2)} C(n+1,n-2k)*C(k). (End)
Binomial transform of doubled Catalan sequence 1,1,1,1,2,2,5,5,14,14,... - Paul Barry, Nov 17 2005
Row sums of Pascal-Catalan triangle A086617. - Paul Barry, Nov 17 2005
g(z) = (1-z-sqrt(1-2z-3z^2))/(2z-2z^2)/z - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007, corrected by Vaclav Kotesovec, Feb 13 2014
D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n+4)*a(n-2) +3*(n-1)*a(n-3)=0. - R. J. Mathar, Nov 30 2012
a(n) ~ 3^(n+5/2) / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014

Edited by N. J. A. Sloane, Oct 16 2006

cp's OEIS Frontend

A002026 Generalized ballot numbers (first differences of Motzkin numbers).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions