

A005043


Riordan numbers: a(n) = (n1)*(2*a(n1) + 3*a(n2))/(n+1).
(Formerly M2587)


170



1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Also called Motzkin summands or ring numbers.
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).
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
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
Number of Motzkin paths of length n with no horizontal steps at level 0.  Emeric Deutsch, Nov 09 2003
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
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
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
a(n) = number of 321avoiding permutations on [n] in which each lefttoright 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
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
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
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 nth central moment of X is E[(X+1)^n] = a(n).  Andrew V. Sutherland, Dec 02 2007
Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the nth tensor power of V is a(n).  Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008
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
a(n) has the following standardYoungtableaux (SYT) interpretation: binomial(n+1,k)*binomial(nk1,k1)/(n+1)=f^(k,k,1^{n2k}) where f^lambda equals the number of SYT of shape lambda.  Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010
a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n2k}) for all 1 <= k <= floor(n/2).  Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010
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+1z(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+113)=0.  Emeric Deutsch, May 29 2010
Apparently: Number of Dyck 2npaths with all ascents length 2 and no descent length 2.  David Scambler, Apr 17 2012
This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck npaths to those Dyck (2n)paths in which each ascent is of length 2. It sends descents of length 1 in the npath to descents of length 2 in the (2n)path. But Dyck npaths with no descents of length 1 are equinumerous with Riordan npaths (Motzkin npaths with no flatsteps at ground level) as follows. Given a Dyck npath 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
From Nolan Wallach, Aug 20 2014: (Start)
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,k1)*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).
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 Shur 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 Shur 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).
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^(2n2j) 2^j])*(1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2p_2)/2)^n. But ((p_1)^2p_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).
(End)
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
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1x) = P[x], and C(x)= [1sqrt(14x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1x).
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)].
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).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(1)(x) = P[Cinv(x)].
Fib(x) = Fin[Cinv(Cinv(x))] = P[Cinv(x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1xx^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).
Various relations among the o.g.f.s may be easily constructed, such as Fib[Mot(x)] = P[P(x)] = x/(12*x) a generating fct for 2^n.
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,1t]], and that for A104597, Pinv[Cinv(x),t+1]. (End)
Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the noncrossing partitions he describes.  Tom Copeland, Nov 09 2014
The number of lattice paths from (0,0) to (n,0) that do not cross below the xaxis and use upstep=(1,1) and downsteps=(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
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
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
The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2Gorenstein 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 projectiveinjective module equals the number of Riordan paths, that is, Motzkin paths without levelsteps at height zero, of length n."  Eric M. Schmidt, Dec 16 2017
A connection to the ThueMorse sequence: (1)^a(n) = (1)^A010060(n) * (1)^A010060(n+1) = A106400(n) * A106400(n+1).  Vladimir Reshetnikov, Jul 21 2019
Named by Bernhart (1999) after the American mathematician John Riordan (19031988).  Amiram Eldar, Apr 15 2021


REFERENCES

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


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
Prarit Agarwal and June Nahmgoong, Singlets in the tensor product of an arbitrary number of Adjoint representations of SU(3), arXiv:2001.10826 [math.RT], 2020.
O. Aichholzer, A. Asinowski, and T. Miltzow, Disjoint compatibility graph of noncrossing matchings of points in convex position, arXiv preprint arXiv:1403.5546 [math.CO], 2014.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 25442563.
Gert Almkvist, Warren Dicks, and Edward Formanek, Hilbert series of fixed free algebras and noncommutative classical invariant theory, J. Algebra 93 (1985), no. 1, 189214.
D. L. Andrews, Letter to N. J. A. Sloane, Apr 10 1978.
D. L. Andrews and T. Thirunamachandran, On threedimensional rotational averages, J. Chem. Phys., 67 (1977), 50265033.
D. L. Andrews and T. Thirunamachandran, On threedimensional rotational averages, J. Chem. Phys., 67 (1977), 50265033. [Annotated scanned copy]
J.L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Riordan arrays, the Amatrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
Paul Barry, On the Central Antecedents of Integer (and Other) Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.3.
Paul Barry and Aoife Hennessy, Fourterm Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2.  From N. J. A. Sloane, Sep 21 2012
Frank R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73112.
Frank R. Bernhart, Fundamental chromatic numbers, Unpublished. (Annotated scanned copy)
Frank R. Bernhart & N. J. A. Sloane, Correspondence, 1977
Frank R. Bernhart & N. J. A. Sloane, Emails, AprilMay 1994
Tom Braden and Artem Vysogorets, KazhdanLusztig polynomials of matroids under deletion, arXiv:1909.09888 [math.CO], 2019.
David Callan, Riordan numbers are differences of trinomial coefficients, September 25, 2006.
D. Callan, Pattern avoidance in "flattened" partitions, Discrete Math., 309 (2009), 41874191.
David Callan, Bijections for Dyck paths with all peak heights of the same parity, arXiv:1702.06150 [math.CO], 2017.
XiangKe Chang, X.B. Hu, H. Lei, and Y.N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
W. Y. C. Chen, E. Y. P. Deng and L. L. M. Yang, Riordan paths and derangements, arXiv:math/0602298 [math.CO], 2006.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
Eliahu Cohen, Tobias Hansen, and Nissan Itzhaki, From Entanglement Witness to Generalized Catalan Numbers, arXiv:1511.06623 [quantph], 2015 (see equation (23)).
Benoit Collins, Ion Nechita, and Deping Ye, The absolute positive partial transpose property for random induced states, arXiv preprint arXiv:1108.1935 [mathph], 2011.
Nicolas Crampe, Julien Gaboriaud, and Luc Vinet, Racah algebras, the centralizer Z_n(sl_2) and its HilbertPoincaré series, arXiv:2105.01086 [math.RT], 2021.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.  From N. J. A. Sloane, May 11 2012
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 [cs.DM], 2013.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191215.
I. Dolinka, J. East, and R. D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291301.
S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169191.
Mauricio Fernández, On the Orientation Average Based on Central Orientation Density Functions for Polycrystalline Materials, Journal of Elasticity (2019).
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, SatoTate distributions and Galois endomorphism modules in genus 2, arXiv preprint arXiv:1110.6638 [math.NT], 2011.
Yibo Gao, Principal specializations of Schubert polynomials and pattern containment, arXiv:1910.08872 [math.CO], 2019.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced knoncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019) Article 111705. doi:10.1016/j.disc.2019.111705
Phil Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383426.
B. Howard, J. Millson, A. Snowden and R. Vakil, The projective invariants of ordered points on the line, arXiv:math.AG/0505096, 2005.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 423
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, Lpolynomials and random matrices, arXiv:0803.4462 [math.NT], 20082010.
Hana Kim and R. P. Stanley, A refined enumeration of hex trees and related polynomials, Preprint 2015, European Journal of Combinatorics, Volume 54, May 2016, Pages 207219..
Sergey Kitaev, Pavel Salimov, Christopher Severs, and Henning Ulfarsson, Restricted rooted nonseparable planar maps, arXiv preprint arXiv:1202.1790 [math.CO], 2012.
S. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, Restricted nonseparable planar maps and some pattern avoiding permutations, 2012.  From N. J. A. Sloane, Jan 01 2013
D. E. Knuth, Letter to L. W. Shapiro, R. K. Guy. N. J. A. Sloane, R. P. Stanley, H. Wilf regarding A001006 and A005043
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Boyu Li, Asymptotic Distributions for Block Statistics on Noncrossing Partitions, Master's Thesis, Univ. Waterloo, 2013.
Nanna Holmgaard List, Timothé Romain Léo Melin, Martin van Horn, and Trond Saue, Beyond the electricdipole approximation in simulations of Xray absorption spectroscopy: Lessons from relativistic theory, arXiv:2001.10738 [physics.chemph], 2020.
Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227238.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Zhousheng Mei and Suijie Wang, Pattern Avoidance of Generalized Permutations, arXiv:1804.06265 [math.CO], 2018.
J. Menashe, Bijections on Riordan objects [From Tom Copeland, Nov 07 2014]
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301320.
S. Morrison, E. Peters, and N. Snyder, Categories generated by a trivalent vertex, arXiv preprint arXiv:1501.06869 [math.QA], 2015.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combinat. Theory, Ser A, 19, 214222, 1975.
E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013.
E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique
E. Royer, Interprétation combinatoire des moments négatifs des valeurs de fonctions L au bord de la bande critique, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601620.
Martin Rubey and Christian Stump, Double deficiencies of Dyck paths via the BilleyJockuschStanley bijection, arXiv:1708.05092 [math.CO], 2017.
J. Salas and A. D. Sokal, Transfer Matrices and PartitionFunction Zeros for Antiferromagnetic Potts Models. V. Further Results for the SquareLattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279373, arXiv:0711.1738 [math.QA]. Mentions this sequence.  N. J. A. Sloane, Mar 14 2014
L. W. Shapiro & N. J. A. Sloane, Correspondence, 1976
L. W. Shapiro and C. J. Wang, A bijection between 3Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.
M. Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93101.
H. C. H. Schubert, Allgemeine Anzahlfunctionen für Kegelschnitte, Flächen und Räume zweiten Grades in n Dimensionen, Math. Annalen, June 1894, Volume 45, Issue 2, pp 153206.
Hua Sun and Yi Wang, A Combinatorial Proof of the LogConvexity of CatalanLike Numbers, J. Int. Seq. 17 (2014) # 14.5.2
Yidong Sun and Fei Ma, Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths, arXiv preprint arXiv:1305.2015 [math.CO], 2013.
D.N. Verma, Towards Classifying Finite PointSet Configurations, 1997, Unpublished. [Scanned copy of annotated version of preprint given to me by the author in 1997.  N. J. A. Sloane, Oct 03 2021]
ChaoJen Wang, Applications of the GouldenJackson cluster method to counting Dyck paths by occurrences of subwords.
Eric Weisstein's World of Mathematics, Isotropic Tensor.
F. Yano and H. Yoshida, Some set partition statistics in noncrossing partitions and generating functions, Discr. Math., 307 (2007), 31473160.


FORMULA

a(n) = Sum_{k=0..n} (1)^(nk)*binomial(n, k)*A000108(k). a(n) = (1/(n+1)) * Sum_{k=0..ceiling(n/2)} binomial(n+1, k)*binomial(nk1, k1), 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).]
G.f.: (1 + x  sqrt(12*x3*x^2))/(2*x*(1+x)).
G.f.: 2/(1+x+sqrt(12*x3*x^2)).  Paul Peart (ppeart(AT)fac.howard.edu), May 27 2000
a(n+1) + (1)^n = a(0)*a(n) + a(1)*a(n1) + ... + a(n)*a(0).  Bernhart
a(n) = (1/(n+1)) * Sum_{i} (1)^i*binomial(n+1, i)*binomial(2*n2*i, ni).  Bernhart
G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
E.g.f.: exp(x)*(BesselI(0, 2*x)  BesselI(1, 2*x)).  Vladeta Jovovic, Apr 28 2003
a(n) = A001006(n1)  a(n1).
a(n+1) = Sum_{k=0..n} (1)^k*A026300(n, k), where A026300 is the Motzkin triangle.
a(n) = Sum_{k=0..n} (1)^k*binomial(n, k)*binomial(k, floor(k/2)).  Paul Barry, Jan 27 2005
a(n) = Sum_{k>=0} A086810(nk, k).  Philippe Deléham, May 30 2005
a(n+2) = Sum_{k>=0} A064189(nk, k).  Philippe Deléham, May 31 2005
Moment representation: a(n) = (1/(2*Pi))*Int(x^n*sqrt((1+x)(3x))/(1+x),x,1,3).  Paul Barry, Jul 09 2006
Inverse binomial transform of A000108 (Catalan numbers).  Philippe Deléham, Oct 20 2006
a(n) = (2/Pi)* Integral_{t_0..Pi} (4*cos^2(x)1)^n*sin^2(x) dx.  Andrew V. Sutherland, Dec 02 2007
G.f.: 1/(1x^2/(1xx^2/(1xx^2/(1xx^2/(1.....(continued fraction).  Paul Barry, Jan 22 2009
G.f.: 1/(1+xx/(1x/(1+xx/(1x/(1+xx/(1... (continued fraction).  Paul Barry, May 16 2009
G.f.: 1/(1x^2/(1x/(1x/(1x^2/(1x/(1x/(1x^2/(1x/(1... (continued fraction).  Paul Barry, Mar 02 2010
a(n) = (1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(3).  Mark van Hoeij, Jul 02 2010
a(n) = (1)^n*hypergeometric([n,1/2],[2],4).  Peter Luschny, Aug 15 2012
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 length1 ascents.  Joerg Arndt, Aug 19 2012 and Apr 16 2013
a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)).  Vaclav Kotesovec, Oct 02 2012
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
Dfinite (an alternative): (n+1)*a(n) = 3*(n2)*a(n3) + (5*n7)*a(n2) + (n2)*a(n1), n >= 3.  Fung Lam, Mar 22 2014
Asymptotics: a(n) = 3^(n+2)/sqrt(3*n*Pi)/(8*n)*(121/(16*n) + O(1/n^2)) (with contribution by Vaclav Kotesovec).  Fung Lam, Mar 22 2014
a(n) = T(2*n1,n)/n, where T(n,k) = triangle of A180177.  Vladimir Kruchinin, Sep 23 2014
a(n) = (1)^n*JacobiP(n,1,n3/2,7)/(n+1).  Peter Luschny, Sep 23 2014
a(n) = Sum_{k=0..n} C(n,k)*(C(k,nk)C(k,nk1)).  Peter Luschny, Oct 01 2014
a(n) = A002426(n)  A005717(n), n > 0.  Mikhail Kurkov, Feb 24 2019
a(n) = A309303(n) + A309303(n+1).  Vladimir Reshetnikov, Jul 22 2019
From Peter Bala, Feb 11 2022: (Start)
a(n) = A005773(n+1)  2*A005717(n) for n >= 1.
Conjectures: for n >= 1, n divides a(2*n+1) and 2*n1 divides a(2*n). (End)


EXAMPLE

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.
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 + ...
From Gus Wiseman, Nov 15 2022: (Start)
The a(0) = 1 through a(6) = 15 lonechildavoiding (no vertices of outdegree 1) ordered rooted trees with n + 1 vertices (ranked by A358376):
o . (oo) (ooo) (oooo) (ooooo) (oooooo)
((oo)o) ((oo)oo) ((oo)ooo)
(o(oo)) ((ooo)o) ((ooo)oo)
(o(oo)o) ((oooo)o)
(o(ooo)) (o(oo)oo)
(oo(oo)) (o(ooo)o)
(o(oooo))
(oo(oo)o)
(oo(ooo))
(ooo(oo))
(((oo)o)o)
((o(oo))o)
((oo)(oo))
(o((oo)o))
(o(o(oo)))
(End)


MAPLE

A005043 := proc(n) option remember; if n <= 1 then 1n else (n1)*(2*A005043(n1)+3*A005043(n2))/(n+1); fi; end;
Order := 20: solve(series((xx^2)/(1x+x^2), x)=y, x); # outputs g.f.


MATHEMATICA

a[0]=1; a[1]=0; a[n_]:= a[n] = (n1)*(2*a[n1] + 3*a[n2])/(n+1); Table[ a[n], {n, 0, 30}] (* Robert G. Wilson v, Jun 14 2005 *)
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 *)
RecurrenceTable[{a[0]==1, a[1]==0, a[n]==(n1) (2a[n1]+3a[n2])/(n+1)}, a, {n, 30}] (* Harvey P. Dale, Sep 27 2013 *)
a[ n_]:= SeriesCoefficient[2/(1+x +Sqrt[12x3x^2]), {x, 0, n}]; (* Michael Somos, Aug 21 2014 *)
a[ n_]:= If[n<0, 0, 3^(n+3/2) Hypergeometric2F1[3/2, n+2, 2, 4]/I]; (* Michael Somos, Aug 21 2014 *)
Table[3^(n+3/2) CatalanNumber[n] (4(5+2n)Hypergeometric2F1[3/2, 3/2, 1/2n, 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 *)
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 *)


PROG

(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 */
(Maxima) a[0]:1$
a[1]:0$
a[n]:=(n1)*(2*a[n1]+3*a[n2])/(n+1)$
makelist(a[n], n, 0, 12); /* Emanuele Munarini, Mar 02 2011 */
(Haskell)
a005043 n = a005043_list !! n
a005043_list = 1 : 0 : zipWith div
(zipWith (*) [1..] (zipWith (+)
(map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
 Reinhard Zumkeller, Jan 31 2012
(PARI) N=66; Vec(serreverse(x/(1+x*sum(k=1, N, x^k))+O(x^N))) \\ Joerg Arndt, Aug 19 2012
(Sage)
A005043 = lambda n: (1)^n*jacobi_P(n, 1, n3/2, 7)/(n+1)
[simplify(A005043(n)) for n in (0..29)]
# Peter Luschny, Sep 23 2014
(Sage)
def ms():
a, b, c, d, n = 0, 1, 1, 1, 1
yield 1
while True:
yield b + (1)^n*d
n += 1
a, b = b, (3*(n1)*n*a+(2*n1)*n*b)/((n+1)*(n1))
c, d = d, (3*(n1)*c(2*n1)*d)/n
A005043 = ms()
print([next(A005043) for _ in range(32)]) # Peter Luschny, May 16 2016
(Python)
from functools import cache
@cache
def A005043(n: int) > int:
if n <= 1: return 1  n
return (n  1) * (2 * A005043(n  1) + 3 * A005043(n  2)) // (n + 1)
print([A005043(n) for n in range(32)]) # Peter Luschny, Nov 20 2022


CROSSREFS

Row sums of triangle A020474, first differences of A082395.
First diagonal of triangular array in A059346.
Binomial transform of A126930.  Philippe Deléham, Nov 26 2009
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
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^(n2) 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
Cf. A187306 (selfconvolution), A348210 (column 1).
Cf. A000045, A000108, A000957, A001006, A005717, A005773, A007317, A057078, A091867, A104597, A126120, A178514, A249548, A309303.
Bisections: A099251, A099252.
Sequence in context: A052827 A033192 A174297 * A099323 A342912 A058534
Adjacent sequences: A005040 A005041 A005042 * A005044 A005045 A005046


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29 2004
Name changed to Riordan numbers following a suggestion from Ira M. Gessel.  N. J. A. Sloane, Jul 24 2020


STATUS

approved



