This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A005043 M2587 #552 Jun 24 2025 10:54:08
%S A005043 1,0,1,1,3,6,15,36,91,232,603,1585,4213,11298,30537,83097,227475,
%T A005043 625992,1730787,4805595,13393689,37458330,105089229,295673994,
%U A005043 834086421,2358641376,6684761125,18985057351,54022715451,154000562758,439742222071,1257643249140
%N A005043 Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).
%C A005043 Also called Motzkin summands or ring numbers.
%C A005043 The old name was "Motzkin sums", used in certain publications. The sequence has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g., A001006(4) = 9 = 3 + 6 = a(4) + a(5).
%C A005043 Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers). - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04 2000
%C A005043 Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - _Emeric Deutsch_, Mar 06 2002
%C A005043 Number of Motzkin paths of length n with no horizontal steps at level 0. - _Emeric Deutsch_, Nov 09 2003
%C A005043 Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - _Emeric Deutsch_, Dec 05 2003
%C A005043 Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09 2004
%C A005043 Difference between central trinomial coefficient and its predecessor. Example: a(6) = 15 = 141 - 126 and (1 + x + x^2)^6 = ... + 126*x^5 + 141*x^6 + ... (Catalan number A000108(n) is the difference between central binomial coefficient and its predecessor.) - _David Callan_, Feb 07 2004
%C A005043 a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e., is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - _David Callan_, Jul 20 2005
%C A005043 The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, ...]; example: Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1. - _Philippe Deléham_, May 28 2005
%C A005043 The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006
%C A005043 Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - _Andrew V. Sutherland_, Dec 02 2007
%C A005043 Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008
%C A005043 Starting with offset 3 = iterates of M * [1,1,1,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - _Gary W. Adamson_, Jan 08 2009
%C A005043 a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010
%C A005043 a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1 <= k <= floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010
%C A005043 a(n) is the number of derangements of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p) = (1/2)(3+1-1-3)=0. - _Emeric Deutsch_, May 29 2010
%C A005043 Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - _David Scambler_, Apr 17 2012
%C A005043 This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU with U, DD with D, UD with a blue flatstep (F), DU with a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. - _David Callan_, Apr 25 2012
%C A005043 From _Nolan Wallach_, Aug 20 2014: (Start)
%C A005043 Let ch[part1, part2] be the value of the character of the symmetric group on n letters corresponding to the partition part1 of n on the conjucgacy class given by part2. Let A[n] be the set of (n+1) partitions of 2n with parts 1 or 2. Then deleting the first term of the sequence one has a(n) = Sum_{k=1..n+1} binomial(n,k-1)*ch[[n,n], A[n][[k]]])/2^n. This via the Frobenius Character Formula can be interpreted as the dimension of the SL(n,C) invariants in tensor^n (wedge^2 C^n).
%C A005043 Explanation: Let p_j denote sum (x_i)^j the sum in k variables. Then the Frobenius formula says then (p_1)^j_1 (p_2)^j_2 ... (p_r)^j_r is equal to sum(lambda, ch[lambda, 1^j_12^j_2 ... r^j_r] S_lambda) with S_lambda the Schur function corresponding to lambda. This formula implies that the coefficient of S([n,n]) in (((p_1)^1+p_2)/2)^n in its expansion in terms of Schur functions is the right hand side of our formula. If we specialize the number of variables to 2 then S[n,n](x,y)=(xy)^n. Which when restricted to y=x^(-1) is 1. That is it is 1 on SL(2).
%C A005043 On the other hand ((p_1)^2+p_2)/2 is the complete homogeneous symmetric function of degree 2 that is tr(S^2(X)). Thus our formula for a(n) is the same as that of Samson Black above since his V is the same as S^2(C^2) as a representation of SL(2). On the other hand, if we multiply ch(lambda) by sgn you get ch(Transpose(lambda)). So ch([n,n]) becomes ch([2,...,2]) (here there are n 2's). The formula for a(n) is now (1/2^n)*Sum_{j=0..n} ch([2,..,2], 1^(2n-2j) 2^j])*(-1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2-p_2)/2)^n. But ((p_1)^2-p_2)/2 in n variables is the second elementary symmetric function which is the character of wedge^2 C^n and S_(2,...,2) is 1 on SL(n).
%C A005043 (End)
%C A005043 a(n) = number of noncrossing partitions (A000108) of [n] that contain no singletons, also number of nonnesting partitions (A000108) of [n] that contain no singletons. - _David Callan_, Aug 27 2014
%C A005043 From _Tom Copeland_, Nov 02 2014: (Start)
%C A005043 Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
%C A005043 Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].
%C A005043 Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
%C A005043 BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].
%C A005043 Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
%C A005043 Various relations among the o.g.f.s may be easily constructed, such as Fib[-Mot(-x)] = -P[P(-x)] = x/(1-2*x) a generating fct for 2^n.
%C A005043 Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1]. (End)
%C A005043 Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the non-crossing partitions he describes. - _Tom Copeland_, Nov 09 2014
%C A005043 The number of lattice paths from (0,0) to (n,0) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-k) where k is a positive integer. For example, a(4) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - _Nicholas Ham_, Aug 19 2015
%C A005043 A series created using 2*(a(n) + a(n+1)) + (a(n+1) + a(n+2)) has Hankel transform of F(2n), offset 3, F being a Fibonacci number, A001906 (Empirical observation). - _Tony Foster III_, Jul 30 2016
%C A005043 The series a(n) + A001006(n) has Hankel transform F(2n+1), offset n=1, F being the Fibonacci bisection A001519 (empirical observation). - _Tony Foster III_, Sep 05 2016
%C A005043 The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n. Moreover, the number of such algebras having the double centraliser property with respect to a minimal faithful projective-injective module equals the number of Riordan paths, that is, Motzkin paths without level-steps at height zero, of length n." - _Eric M. Schmidt_, Dec 16 2017
%C A005043 A connection to the Thue-Morse sequence: (-1)^a(n) = (-1)^A010060(n) * (-1)^A010060(n+1) = A106400(n) * A106400(n+1). - _Vladimir Reshetnikov_, Jul 21 2019
%C A005043 Named by Bernhart (1999) after the American mathematician John Riordan (1903-1988). - _Amiram Eldar_, Apr 15 2021
%D A005043 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005043 G. C. Greubel, <a href="/A005043/b005043.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..200 from T. D. Noe)
%H A005043 Katharine Adamyk, Scott Balchin, Miguel Barrero, Steven Scheirer, Noah Wisdom, and Valentina Zapata Castro, <a href="https://arxiv.org/abs/2506.11159">On minimal bases in homotopical combinatorics</a>, arXiv:2506.11159 [math.AT], 2025. See p. 16.
%H A005043 Prarit Agarwal and June Nahmgoong, <a href="https://arxiv.org/abs/2001.10826">Singlets in the tensor product of an arbitrary number of Adjoint representations of SU(3)</a>, arXiv:2001.10826 [math.RT], 2020.
%H A005043 Oswin Aichholzer, Andrei Asinowski, and Tillmann Miltzow, <a href="http://arxiv.org/abs/1403.5546">Disjoint compatibility graph of non-crossing matchings of points in convex position</a>, arXiv preprint arXiv:1403.5546 [math.CO], 2014.
%H A005043 Martin Aigner, <a href="http://dx.doi.org/10.1016/j.disc.2007.06.012">Enumeration via ballot numbers</a>, Discrete Math., 308 (2008), 2544-2563.
%H A005043 Gert Almkvist, Warren Dicks, and Edward Formanek, <a href="http://dx.doi.org/10.1016/0021-8693(85)90183-8">Hilbert series of fixed free algebras and noncommutative classical invariant theory</a>, J. Algebra 93 (1985), no. 1, 189-214.
%H A005043 D. L. Andrews, <a href="/A005043/a005043.pdf">Letter to N. J. A. Sloane</a>, Apr 10 1978.
%H A005043 D. L. Andrews and T. Thirunamachandran, <a href="http://dx.doi.org/10.1063/1.434725">On three-dimensional rotational averages</a>, J. Chem. Phys., 67 (1977), 5026-5033.
%H A005043 D. L. Andrews and T. Thirunamachandran, <a href="/A005043/a005043_1.pdf">On three-dimensional rotational averages</a>, J. Chem. Phys., 67 (1977), 5026-5033. [Annotated scanned copy]
%H A005043 Jean Luc Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.
%H A005043 Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, <a href="http://jl.baril.u-bourgogne.fr/narayana.pdf">Generalized Narayana arrays, restricted Dyck paths, and related bijections</a>, Univ. Bourgogne (France, 2025). See p. 20.
%H A005043 Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H A005043 Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.
%H A005043 Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Barry/barry444.html">On the Central Antecedents of Integer (and Other) Sequences</a>, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
%H A005043 Paul Barry, <a href="https://arxiv.org/abs/2307.00098">Moment sequences, transformations, and Spidernet graphs</a>, arXiv:2307.00098 [math.CO], 2023.
%H A005043 Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry1/barry202.html">Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays</a>, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
%H A005043 Frank R. Bernhart, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discr. Math., 204 (1999) 73-112.
%H A005043 Frank R. Bernhart, <a href="/A000296/a000296_1.pdf">Fundamental chromatic numbers</a>, Unpublished. (Annotated scanned copy)
%H A005043 Frank R. Bernhart & N. J. A. Sloane, <a href="/A001683/a001683.pdf">Correspondence, 1977</a>.
%H A005043 Frank R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>.
%H A005043 Jacob L. Bourjaily, Michael Plesser, and Cristian Vergu, <a href="https://arxiv.org/abs/2412.21189">The Many Colours of Amplitudes</a>, arXiv:2412.21189 [hep-th], 2024. See pp. 12, 52.
%H A005043 Tom Braden and Artem Vysogorets, <a href="https://arxiv.org/abs/1909.09888">Kazhdan-Lusztig polynomials of matroids under deletion</a>, arXiv:1909.09888 [math.CO], 2019.
%H A005043 Naim L. Braha and Toufik Mansour, <a href="https://doi.org/10.1016/j.jmaa.2024.128902">Some properties of new sequence spaces based on Riordan numbers</a>, Journal of Mathematical Analysis and Applications, Volume 543, Issue 2, Part 1, 128902, (2025).
%H A005043 David Callan, <a href="http://www.stat.wisc.edu/~callan/papersother/">Riordan numbers are differences of trinomial coefficients</a>, September 25, 2006.
%H A005043 David Callan, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.019">Pattern avoidance in "flattened" partitions</a>, Discrete Math., 309 (2009), 4187-4191.
%H A005043 David Callan, <a href="https://arxiv.org/abs/1702.06150">Bijections for Dyck paths with all peak heights of the same parity</a>, arXiv:1702.06150 [math.CO], 2017.
%H A005043 Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, <a href="https://doi.org/10.37236/4793">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H A005043 Xiaomei Chen, <a href="https://arxiv.org/abs/2412.00668">Counting humps and peaks in Motzkin paths with height k</a>, arXiv:2412.00668 [math.CO], 2024. See p. 11.
%H A005043 William Y. C. Chen, Eva Y. P. Deng, and Laura L. M. Yang, <a href="https://arxiv.org/abs/math/0602298">Riordan paths and derangements</a>, arXiv:math/0602298 [math.CO], 2006.
%H A005043 Johann Cigler and Christian Krattenthaler, <a href="https://arxiv.org/abs/2003.01676">Hankel determinants of linear combinations of moments of orthogonal polynomials</a>, arXiv:2003.01676 [math.CO], 2020.
%H A005043 Eliahu Cohen, Tobias Hansen, and Nissan Itzhaki, <a href="http://arxiv.org/abs/1511.06623">From Entanglement Witness to Generalized Catalan Numbers</a>, arXiv:1511.06623 [quant-ph], 2015 (see equation (23)).
%H A005043 Benoit Collins, Ion Nechita, and Deping Ye, <a href="http://arxiv.org/abs/1108.1935">The absolute positive partial transpose property for random induced states</a>, arXiv preprint arXiv:1108.1935 [math-ph], 2011.
%H A005043 Nicolas Crampe, Julien Gaboriaud, and Luc Vinet, <a href="https://arxiv.org/abs/2105.01086">Racah algebras, the centralizer Z_n(sl_2) and its Hilbert-Poincaré series</a>, arXiv:2105.01086 [math.RT], 2021.
%H A005043 D. E. Davenport, L. W. Shapiro and L. C. Woodson, <a href="https://doi.org/10.37236/2034">The Double Riordan Group</a>, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
%H A005043 Rodrigo De Castro, Andrés Ramírez, and José L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013. See also <a href="https://doi.org/10.7561/SACS.2014.1.137">Sci. Annals Comp. Sci.</a> (2014) Vol. XXIV, Issue 1, 137-171. See p. 150.
%H A005043 Emeric Deutsch and Bruce E. Sagan, <a href="https://arxiv.org/abs/math/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
%H A005043 Igor Dolinka, James East, and Robert D. Gray, <a href="http://arxiv.org/abs/1512.02279">Motzkin monoids and partial Brauer monoids</a>, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
%H A005043 Robert Donaghey and Louis 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 A005043 Serge Dulucq and Rodica Simion, <a href="http://dx.doi.org/10.1023/A:1008689811936">Combinatorial statistics on alternating permutations</a>, J. Algebraic Combinatorics, 8, 1998, 169-191.
%H A005043 László M. Fehér and András P. Juhász, <a href="https://arxiv.org/abs/2312.06430">Plücker formulas using equivariant cohomology of coincident root strata</a>, arXiv:2312.06430 [math.AG], 2023. See p. 21.
%H A005043 Mauricio Fernández, <a href="https://doi.org/10.1007/s10659-019-09754-8">On the Orientation Average Based on Central Orientation Density Functions for Polycrystalline Materials</a>, Journal of Elasticity (2019).
%H A005043 Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, <a href="http://arxiv.org/abs/1110.6638">Sato-Tate distributions and Galois endomorphism modules in genus 2</a>, arXiv preprint arXiv:1110.6638 [math.NT], 2011.
%H A005043 Sela Fried, <a href="https://arxiv.org/abs/2505.14196">Even-up words and their variants</a>, arXiv:2505.14196 [math.CO], 2025. See p. 11.
%H A005043 Yibo Gao, <a href="https://arxiv.org/abs/1910.08872">Principal specializations of Schubert polynomials and pattern containment</a>, arXiv:1910.08872 [math.CO], 2019.
%H A005043 Yousra Ghemit and Moussa Ahmia, <a href="https://www.researchgate.net/profile/Moussa-Ahmia/publication/387333985_TWO-CATALAN_NUMBERS_COMBINATORIAL_INTERPRETATION_AND_LOG-CONVEXITY/">Two-Catalan numbers: combinatorial interpretation and log-convexity</a>, UPB Sci. Bull., Series A (2024) Vol 86, Iss. 4. See p. 95.
%H A005043 Juan B. Gil and Jordan O. Tirrell, <a href="https://arxiv.org/abs/1806.09065">A simple bijection for classical and enhanced k-noncrossing partitions</a>, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
%H A005043 Taras Goy and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Shattuck/sh36.html">Determinants of Some Hessenberg-Toeplitz Matrices with Motzkin Number Entries</a>, J. Int. Seq., Vol. 26 (2023), Article 23.3.4.
%H A005043 Taras Goy and Mark Shattuck, <a href="https://doi.org/10.26493/2590-9770.1645.d36">Determinant identities for the Catalan, Motzkin and Schröder numbers</a>, Art Disc. Appl. Math. (2023).
%H A005043 Phil Hanlon, <a href="http://dx.doi.org/10.1090/S0002-9947-1982-0662044-8">Counting interval graphs</a>, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383-426.
%H A005043 Benjamin J. Howard, John Millson, Andrew Snowden, and Ravi Vakil, <a href="https://arxiv.org/abs/math/0505096">The projective invariants of ordered points on the line</a>, arXiv:math/0505096 [math.AG], 2005.
%H A005043 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=423">Encyclopedia of Combinatorial Structures 423</a>.
%H A005043 Kiran S. Kedlaya and Andrew V. Sutherland, <a href="http://arXiv.org/abs/0803.4462">Hyperelliptic curves, L-polynomials and random matrices</a>, arXiv:0803.4462 [math.NT], 2008-2010.
%H A005043 Hana Kim and R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/hextrees.pdf">A refined enumeration of hex trees and related polynomials</a>, Preprint 2015, European Journal of Combinatorics, Volume 54, May 2016, pp. 207-219.
%H A005043 Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, <a href="http://arxiv.org/abs/1202.1790">Restricted rooted non-separable planar maps</a>, arXiv preprint arXiv:1202.1790 [math.CO], 2012.
%H A005043 Sergei Kitaev, Pavel Salimov, Christopher Severs and Henning Úlfarsson, <a href="http://staff.ru.is/henningu/papers/maps/maps.pdf">Restricted non-separable planar maps and some pattern avoiding permutations</a>, 2012. - From _N. J. A. Sloane_, Jan 01 2013
%H A005043 D. E. Knuth, <a href="/A001006/a001006_3.pdf">Letter to L. W. Shapiro, R. K. Guy. N. J. A. Sloane, R. P. Stanley, H. Wilf regarding A001006 and A005043</a>.
%H A005043 Nadav Kohen, <a href="https://arxiv.org/abs/2403.00149">Uniform Recurrence in the Motzkin Numbers and Related Sequences mod p</a>, arXiv:2403.00149 [math.CO], 2024.
%H A005043 John W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H A005043 Boyu Li, <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/8179/Boyu_Li.pdf?sequence=1">http://hdl.handle.net/10012/8179</a>, Master's Thesis, Univ. Waterloo, 2013.
%H A005043 Nanna Holmgaard List, Timothé Romain Léo Melin, Martin van Horn, and Trond Saue, <a href="https://arxiv.org/abs/2001.10738">Beyond the electric-dipole approximation in simulations of X-ray absorption spectroscopy: Lessons from relativistic theory</a>, arXiv:2001.10738 [physics.chem-ph], 2020.
%H A005043 Ethan Liu, <a href="https://math.mit.edu/research/highschool/primes/materials/2023/October/7-1-Liu.pdf">On the Structure and Generators of the Chromatic Algebra</a>, Primes Conference, MIT (2023), p. 18/23.
%H A005043 Ethan Yi-Heng Liu, <a href="https://arxiv.org/abs/2401.06095">On the Structure and Generators of the nth-order Chromatic Algebra</a>, arXiv:2401.06095 [math.CO], 2024.
%H A005043 Piera Manara and Claudio Perelli Cippo, <a href="https://web.archive.org/web/20150911054805/http://www.mat.unisi.it/newsito/puma/public_html/22_2/manara_perelli-cippo.pdf">The fine structure of 4321 avoiding involutions and 321 avoiding involutions</a>, PU. M. A. Vol. 22 (2011), 227-238.
%H A005043 Toufik Mansour and Mark Shattuck, <a href="https://math.colgate.edu/~integers/z5/z5.pdf">Enumeration of Catalan and smooth words according to capacity</a>, Integers (2025) Vol. 25, Art. No. A5. See p. 25.
%H A005043 Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.
%H A005043 Zhousheng Mei and Suijie Wang, <a href="https://arxiv.org/abs/1804.06265">Pattern Avoidance of Generalized Permutations</a>, arXiv:1804.06265 [math.CO], 2018.
%H A005043 J. Menashe, <a href="https://www.whitman.edu/mathematics/SeniorProjectArchive/2007/menashjv.pdf">Bijections on Riordan objects</a>. [From Tom Copeland, Nov 07 2014]
%H A005043 Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, <a href="http://dx.doi.org/10.4153/CJM-1997-015-x">On some alternative characterizations of Riordan arrays</a>, Canad. J. Math., 49 (1997), 301-320.
%H A005043 Scott Morrison, Emily Peters, and Noah Snyder, <a href="http://arxiv.org/abs/1501.06869">Categories generated by a trivalent vertex</a>, arXiv preprint arXiv:1501.06869 [math.QA], 2015.
%H A005043 Rosa Orellana, Nancy Wallace, and Mike Zabrocki, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2024/50.pdf">Quasipartition and planar quasipartition algebras</a>, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 50. See p. 11.
%H A005043 L. Poulain d'Andecy, <a href="https://arxiv.org/abs/2304.00850">Centralisers and Hecke algebras in Representation Theory, with applications to Knots and Physics</a>, arXiv:2304.00850 [math.RT], 2023. See p. 64.
%H A005043 Jocelyn Quaintance and Harris Kwong, <a href="http://www.emis.de/journals/INTEGERS/papers/n29/n29.Abstract.html">A combinatorial interpretation of the Catalan and Bell number difference tables</a>, Integers, 13 (2013), #A29.
%H A005043 Marko Riedel et al., <a href="https://math.stackexchange.com/questions/4976413/">Derivation of the Riordan number asymptotics from an inequality of central trinomial coefficients by three Egorychev residues.</a>
%H A005043 J. Riordan, <a href="http://dx.doi.org/10.1016/S0097-3165(75)80010-0">Enumeration of plane trees by branches and endpoints</a>, J. Combinat. Theory, Ser A, 19, 214-222, 1975.
%H A005043 Eric Rowland and Reem Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013.
%H A005043 Emmanuel Royer, <a href="http://www.carva.org/emmanuel.royer">Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique</a>.
%H A005043 Emmanuel Royer, <a href="http://dx.doi.org/10.1016/S0012-9593(03)00024-7">Interprétation combinatoire des moments négatifs des valeurs de fonctions L au bord de la bande critique</a>, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620.
%H A005043 Martin Rubey and Christian Stump, <a href="https://arxiv.org/abs/1708.05092">Double deficiencies of Dyck paths via the Billey-Jockusch-Stanley bijection</a>, arXiv:1708.05092 [math.CO], 2017.
%H A005043 Jesus Salas and Alan D. Sokal, <a href="http://arxiv.org/abs/0711.1738">Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial</a>, J. Stat. Phys. 135 (2009) 279-373; arXiv:0711.1738 [math.QA], 2007-2009. Mentions this sequence. - _N. J. A. Sloane_, Mar 14 2014
%H A005043 Louis W. Shapiro & N. J. A. Sloane, <a href="/A006318/a006318_1.pdf">Correspondence, 1976</a>.
%H A005043 Louis W. Shapiro and Carol J. Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html">A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height</a>, JIS 12 (2009) 09.3.2.
%H A005043 Mark Shattuck, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_42_from93to101.pdf">On the zeros of some polynomials with combinatorial coefficients</a>, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101.
%H A005043 H. C. H. Schubert, <a href="http://dx.doi.org/10.1007/BF01446537">Allgemeine Anzahlfunctionen für Kegelschnitte, Flächen und Räume zweiten Grades in n Dimensionen</a>, Math. Annalen, June 1894, Volume 45, Issue 2, pp 153-206.
%H A005043 Hua Sun and Yi Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Wang/wang11.html">A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers</a>, J. Int. Seq. 17 (2014) # 14.5.2
%H A005043 Yidong Sun and Fei Ma, <a href="http://arxiv.org/abs/1305.2015">Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths</a>, arXiv preprint arXiv:1305.2015 [math.CO], 2013.
%H A005043 Paveł Szabłowski, <a href="https://cdm.ucalgary.ca/article/view/76214">Beta distributions whose moment sequences are related to integer sequences listed in the OEIS</a>, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 97.
%H A005043 D.-N. Verma, <a href="/A012249/a012249.pdf">Towards Classifying Finite Point-Set Configurations</a>, 1997, Unpublished. [Scanned copy of annotated version of preprint given to me by the author in 1997. - _N. J. A. Sloane_, Oct 03 2021]
%H A005043 Chao-Jen Wang, <a href="http://people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf">Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords</a>.
%H A005043 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IsotropicTensor.html">Isotropic Tensor</a>.
%H A005043 Fujine Yano and Hiroaki Yoshida, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.050">Some set partition statistics in non-crossing partitions and generating functions</a>, Discr. Math., 307 (2007), 3147-3160.
%F A005043 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*A000108(k). a(n) = (1/(n+1)) * Sum_{k=0..ceiling(n/2)} binomial(n+1, k)*binomial(n-k-1, k-1), for n > 1. - _Len Smiley_. [Comment from Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 02 2010: the latter sum should be over the range k=1..floor(n/2).]
%F A005043 G.f.: (1 + x - sqrt(1-2*x-3*x^2))/(2*x*(1+x)).
%F A005043 G.f.: 2/(1+x+sqrt(1-2*x-3*x^2)). - Paul Peart (ppeart(AT)fac.howard.edu), May 27 2000
%F A005043 a(n+1) + (-1)^n = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). - Bernhart
%F A005043 a(n) = (1/(n+1)) * Sum_{i} (-1)^i*binomial(n+1, i)*binomial(2*n-2*i, n-i). - Bernhart
%F A005043 G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
%F A005043 E.g.f.: exp(x)*(BesselI(0, 2*x) - BesselI(1, 2*x)). - _Vladeta Jovovic_, Apr 28 2003
%F A005043 a(n) = A001006(n-1) - a(n-1).
%F A005043 a(n+1) = Sum_{k=0..n} (-1)^k*A026300(n, k), where A026300 is the Motzkin triangle.
%F A005043 a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(k, floor(k/2)). - _Paul Barry_, Jan 27 2005
%F A005043 a(n) = Sum_{k>=0} A086810(n-k, k). - _Philippe Deléham_, May 30 2005
%F A005043 a(n+2) = Sum_{k>=0} A064189(n-k, k). - _Philippe Deléham_, May 31 2005
%F A005043 Moment representation: a(n) = (1/(2*Pi))*Int(x^n*sqrt((1+x)(3-x))/(1+x),x,-1,3). - _Paul Barry_, Jul 09 2006
%F A005043 Inverse binomial transform of A000108 (Catalan numbers). - _Philippe Deléham_, Oct 20 2006
%F A005043 a(n) = (2/Pi)* Integral_{x=0..Pi} (4*cos(x)^2-1)^n*sin(x)^2 dx. - _Andrew V. Sutherland_, Dec 02 2007
%F A005043 G.f.: 1/(1-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction). - _Paul Barry_, Jan 22 2009
%F A005043 G.f.: 1/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). - _Paul Barry_, May 16 2009
%F A005043 G.f.: 1/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-... (continued fraction). - _Paul Barry_, Mar 02 2010
%F A005043 a(n) = -(-1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(-3). - _Mark van Hoeij_, Jul 02 2010
%F A005043 a(n) = (-1)^n*hypergeometric([-n,1/2],[2],4). - _Peter Luschny_, Aug 15 2012
%F A005043 Let A(x) be the g.f., then x*A(x) is the reversion of x/(1 + x^2*Sum_{k>=0} x^k); see A215340 for the correspondence to Dyck paths without length-1 ascents. - _Joerg Arndt_, Aug 19 2012 and Apr 16 2013
%F A005043 a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 02 2012
%F A005043 G.f.: 2/(1+x+1/G(0)), where G(k) = 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 05 2013
%F A005043 D-finite (an alternative): (n+1)*a(n) = 3*(n-2)*a(n-3) + (5*n-7)*a(n-2) + (n-2)*a(n-1), n >= 3. - _Fung Lam_, Mar 22 2014
%F A005043 Asymptotics: a(n) = (3^(n+2)/(sqrt(3*n*Pi)*(8*n)))*(1-21/(16*n) + O(1/n^2)) (with contribution by Vaclav Kotesovec). - _Fung Lam_, Mar 22 2014
%F A005043 a(n) = T(2*n-1,n)/n, where T(n,k) = triangle of A180177. - _Vladimir Kruchinin_, Sep 23 2014
%F A005043 a(n) = (-1)^n*JacobiP(n,1,-n-3/2,-7)/(n+1). - _Peter Luschny_, Sep 23 2014
%F A005043 a(n) = Sum_{k=0..n} C(n,k)*(C(k,n-k)-C(k,n-k-1)). - _Peter Luschny_, Oct 01 2014
%F A005043 Conjecture: a(n) = A002426(n) - A005717(n), n > 0. - _Mikhail Kurkov_, Feb 24 2019 [The conjecture is true. - _Amiram Eldar_, May 17 2024]
%F A005043 a(n) = A309303(n) + A309303(n+1). - _Vladimir Reshetnikov_, Jul 22 2019
%F A005043 From _Peter Bala_, Feb 11 2022: (Start)
%F A005043 a(n) = A005773(n+1) - 2*A005717(n) for n >= 1.
%F A005043 Conjectures: for n >= 1, n divides a(2*n+1) and 2*n-1 divides a(2*n). (End)
%e A005043 a(5)=6 because the only dissections of a polygon with a total number of 6 edges are: five pentagons with one of the five diagonals and the hexagon with no diagonals.
%e A005043 G.f. = 1 + x^2 + x^3 + 3*x^4 + 6*x^5 + 15*x^6 + 36*x^7 + 91*x^8 + 232*x^9 + ...
%e A005043 From _Gus Wiseman_, Nov 15 2022: (Start)
%e A005043 The a(0) = 1 through a(6) = 15 lone-child-avoiding (no vertices of outdegree 1) ordered rooted trees with n + 1 vertices (ranked by A358376):
%e A005043 o . (oo) (ooo) (oooo) (ooooo) (oooooo)
%e A005043 ((oo)o) ((oo)oo) ((oo)ooo)
%e A005043 (o(oo)) ((ooo)o) ((ooo)oo)
%e A005043 (o(oo)o) ((oooo)o)
%e A005043 (o(ooo)) (o(oo)oo)
%e A005043 (oo(oo)) (o(ooo)o)
%e A005043 (o(oooo))
%e A005043 (oo(oo)o)
%e A005043 (oo(ooo))
%e A005043 (ooo(oo))
%e A005043 (((oo)o)o)
%e A005043 ((o(oo))o)
%e A005043 ((oo)(oo))
%e A005043 (o((oo)o))
%e A005043 (o(o(oo)))
%e A005043 (End)
%p A005043 A005043 := proc(n) option remember; if n <= 1 then 1-n else (n-1)*(2*A005043(n-1)+3*A005043(n-2))/(n+1); fi; end;
%p A005043 Order := 20: solve(series((x-x^2)/(1-x+x^2),x)=y,x); # outputs g.f.
%t A005043 a[0]=1; a[1]=0; a[n_]:= a[n] = (n-1)*(2*a[n-1] + 3*a[n-2])/(n+1); Table[ a[n], {n, 0, 30}] (* _Robert G. Wilson v_, Jun 14 2005 *)
%t A005043 Table[(-3)^(1/2)/6 * (-1)^n*(3*Hypergeometric2F1[1/2,n+1,1,4/3]+ Hypergeometric2F1[1/2,n+2,1,4/3]), {n,0,32}] (* cf. _Mark van Hoeij_ in A001006 *) (* _Wouter Meeussen_, Jan 23 2010 *)
%t A005043 RecurrenceTable[{a[0]==1,a[1]==0,a[n]==(n-1) (2a[n-1]+3a[n-2])/(n+1)},a,{n,30}] (* _Harvey P. Dale_, Sep 27 2013 *)
%t A005043 a[ n_]:= SeriesCoefficient[2/(1+x +Sqrt[1-2x-3x^2]), {x, 0, n}]; (* _Michael Somos_, Aug 21 2014 *)
%t A005043 a[ n_]:= If[n<0, 0, 3^(n+3/2) Hypergeometric2F1[3/2, n+2, 2, 4]/I]; (* _Michael Somos_, Aug 21 2014 *)
%t A005043 Table[3^(n+3/2) CatalanNumber[n] (4(5+2n)Hypergeometric2F1[3/2, 3/2, 1/2-n, 1/4] -9 Hypergeometric2F1[3/2, 5/2, 1/2 -n, 1/4])/(4^(n+3) (n+1)), {n, 0, 31}] (* _Vladimir Reshetnikov_, Jul 21 2019 *)
%t A005043 Table[Sqrt[27]/8 (3/4)^n CatalanNumber[n] Hypergeometric2F1[1/2, 3/2, 1/2 - n, 1/4], {n, 0, 31}] (* _Jan Mangaldan_, Sep 12 2021 *)
%o A005043 (PARI) {a(n) = if( n<0, 0, n++; polcoeff( serreverse( (x - x^3) / (1 + x^3) + x * O(x^n)), n))}; /* _Michael Somos_, May 31 2005 */
%o A005043 (PARI) my(N=66); Vec(serreverse(x/(1+x*sum(k=1,N,x^k))+O(x^N))) \\ _Joerg Arndt_, Aug 19 2012
%o A005043 (Maxima) a[0]:1$
%o A005043 a[1]:0$
%o A005043 a[n]:=(n-1)*(2*a[n-1]+3*a[n-2])/(n+1)$
%o A005043 makelist(a[n],n,0,12); /* _Emanuele Munarini_, Mar 02 2011 */
%o A005043 (Haskell)
%o A005043 a005043 n = a005043_list !! n
%o A005043 a005043_list = 1 : 0 : zipWith div
%o A005043 (zipWith (*) [1..] (zipWith (+)
%o A005043 (map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
%o A005043 -- _Reinhard Zumkeller_, Jan 31 2012
%o A005043 (Sage)
%o A005043 A005043 = lambda n: (-1)^n*jacobi_P(n,1,-n-3/2,-7)/(n+1)
%o A005043 [simplify(A005043(n)) for n in (0..29)]
%o A005043 # _Peter Luschny_, Sep 23 2014
%o A005043 (Sage)
%o A005043 def ms():
%o A005043 a, b, c, d, n = 0, 1, 1, -1, 1
%o A005043 yield 1
%o A005043 while True:
%o A005043 yield -b + (-1)^n*d
%o A005043 n += 1
%o A005043 a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)/((n+1)*(n-1))
%o A005043 c, d = d, (3*(n-1)*c-(2*n-1)*d)/n
%o A005043 A005043 = ms()
%o A005043 print([next(A005043) for _ in range(32)]) # _Peter Luschny_, May 16 2016
%o A005043 (Python)
%o A005043 from functools import cache
%o A005043 @cache
%o A005043 def A005043(n: int) -> int:
%o A005043 if n <= 1: return 1 - n
%o A005043 return (n - 1) * (2 * A005043(n - 1) + 3 * A005043(n - 2)) // (n + 1)
%o A005043 print([A005043(n) for n in range(32)]) # _Peter Luschny_, Nov 20 2022
%Y A005043 Row sums of triangle A020474, first differences of A082395.
%Y A005043 First diagonal of triangular array in A059346.
%Y A005043 Binomial transform of A126930. - _Philippe Deléham_, Nov 26 2009
%Y A005043 The Hankel transform of a(n+1) is A128834. The Hankel transform of a(n+2) is floor((2*n+4)/3) = A004523(n+2). - _Paul Barry_, Mar 08 2011
%Y A005043 The Kn11 triangle sums of triangle A175136 lead to A005043(n+2), while the Kn12(n) = A005043(n+4)-2^(n+1), Kn13(n) = A005043(n+6)-(n^2+9*n+56)*2^(n-2) and the Kn4(n) = A005043(2*n+2) = A099251(n+1) triangle sums are related to the sequence given above. For the definitions of these triangle sums see A180662. - _Johannes W. Meijer_, May 06 2011
%Y A005043 Cf. A187306 (self-convolution), A348210 (column 1).
%Y A005043 Cf. A000045, A000108, A000957, A001006, A005717, A005773, A007317, A057078, A091867, A104597, A126120, A178514, A249548, A309303.
%Y A005043 Bisections: A099251, A099252.
%K A005043 nonn,easy,nice
%O A005043 0,5
%A A005043 _N. J. A. Sloane_
%E A005043 Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29 2004
%E A005043 Name changed to Riordan numbers following a suggestion from _Ira M. Gessel_. - _N. J. A. Sloane_, Jul 24 2020