A001002 Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.

1, 1, 3, 10, 38, 154, 654, 2871, 12925, 59345, 276835, 1308320, 6250832, 30142360, 146510216, 717061938, 3530808798, 17478955570, 86941210950, 434299921440, 2177832612120, 10959042823020, 55322023332420, 280080119609550, 1421744205767418, 7234759677699954

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n+1) is number of (2,3)-rooted trees on n nodes.

This sequence appears to be a transform of the Fibonacci numbers A000045. This sequence is to the Fibonacci numbers as the Catalan numbers A000108 is to the all ones sequence. See link to Mathematica program. - Mats Granvik, Dec 30 2017

a(n) is the number of parking functions of size n avoiding the patterns 231, 312, and 321. - Lara Pudwell, Apr 10 2023

Examples

			a(3)=10 because a convex pentagon can be dissected in 5 ways into triangles (draw 2 diagonals from any of the 5 vertices) and in 5 ways into a triangle and a quadrilateral (draw any of the 5 diagonals).
		

References

• F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 211 (3.2.73-74)
• 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

• Alois P. Heinz, Table of n, a(n) for n = 0..1372 (first 101 terms from T. D. Noe)
• Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
• Paul Barry, On the Central Coefficients of Bell Matrices, J. Int. Seq. 14 (2011) # 11.4.3, example 7.
• D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
• I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
• I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
• I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
• I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy].
• A. Erdelyi and I. M. H. Etherington, Some problems of non-associative combinations (II), Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.
• Mats Granvik, Mathematica program to compute the sequence as a transform of the Fibonacci numbers.
• Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
• Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 395
• Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
• T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
• T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
• Thomas M. Richardson, The three 'R's and Dual Riordan Arrays, arXiv:1609.01193 [math.CO], 2016.
• A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv preprint arXiv:1401.7194 [math.CO], 2014.
• Index entries for reversions of series

Crossrefs

n*a(n) = A038112(n-1), n > 0.

Cf. A104978, A181997, A181998, A209441, A209442, A213684 (log).

Programs

GAP

List([0..25], n->Sum([0..Int(n/2)],k->Binomial(2*n-k,n+k)*Binomial(n+k,k)/(n+1))); # Muniru A Asiru, Mar 30 2018

Maple

a:= proc(n) option remember; `if`(n<2, 1, (n*(22*n-11)*
      a(n-1) + (9*n-6)*(3*n-4)*a(n-2))/(5*n*(n+1)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 21 2021

Mathematica

Rest[CoefficientList[InverseSeries[Series[y - y^2 - y^3, {y, 0, 30}], x], x]]
a[n_] := CatalanNumber[n]*Hypergeometric2F1[1/2-n/2, -n/2, -2n, -4]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 20 2015, after Peter Luschny *)
a[n_] := a[n] = If[n == 0, 1, Sum[a[i] a[n - 1 - i], {i, 0, n - 1}] + Sum[a[i] a[j] a[n - 2 - i - j], {i, 0, n - 2}, {j, 0, n - 2 - i}]];
Table[a[n], {n, 0, 30}] (* Li Han, Jan 02 2021 *)

Maxima

T(n,k):=if n<0 or k<0 then 0 else if nVladimir Kruchinin, Oct 03 2014 */

PARI

a(n)=if(n<0,0,polcoeff(serreverse(x-x^2-x^3+x^2*O(x^n)),n+1))

PARI

a(n)=if(n<0,0,sum(k=0,n\2,(2*n-k)!/k!/(n-2*k)!)/(n+1)!)

PARI

a(n)=sum(k=0,n\2,binomial(2*n-k,n+k)*binomial(n+k,k))/(n+1) \\ Hanna

PARI

{Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A=1+(1/x)*sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/m!)); polcoeff(A, n)}  \\ Paul D. Hanna, Jun 22 2012

PARI

{Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A=exp(sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/x/m!)+x*O(x^n))); polcoeff(A, n)}  \\ Paul D. Hanna, Jun 22 2012

Sage

A001002 = lambda n: catalan_number(n)*hypergeometric([1/2-n/2, -n/2], [-2*n], -4) if n>0 else 1
[A001002(n).n(100).round() for n in range(24)] # Peter Luschny, Oct 03 2014

Formula

G.f. (offset 1) is series reversion of x - x^2 - x^3.

a(n) = (1/(n+1))*Sum_{k=ceiling(n/2)..n} binomial(n+k, k)*binomial(k, n-k). - Len Smiley

D-finite with recurrence 5*n*(n+1) * a(n) = 11*n*(2*n-1) * a(n-1) + 3*(3*n-2)*(3*n-4) * a(n-2). - Len Smiley

G.f.: (4*sin(asin((27*x+11)/16)/3)-1)/(3*x). - Paul Barry, Feb 02 2005

G.f. satisfies: A(x) = 1 + x*A(x)^2 + x^2*A(x)^3. - Paul D. Hanna, Jun 22 2012

Antidiagonal sums of triangle A104978 which has g.f. F(x,y) that satisfies: F = 1 + x*F^2 + x*y*F^3. - Paul D. Hanna, Mar 30 2005

a(n) = Sum_{k=0..floor(n/2)} C(2*n-k, n+k)*C(n+k, k)/(n+1). - Paul D. Hanna, Mar 30 2005

G.f. satisfies: x = Sum_{n>=1} 1/(1+x*A(x))^(2*n) * Product_{k=1..n} (1 - 1/(1+x*A(x))^k). - Paul D. Hanna, Apr 05 2012

G.f.: 1 + (1/x)*Sum_{n>=1} d^(n-1)/dx^(n-1) (x^2+x^3)^n/n!. - Paul D. Hanna, Jun 22 2012

G.f.: exp( Sum_{n>=1} d^(n-1)/dx^(n-1) ((x^2+x^3)^n/x)/n! ). - Paul D. Hanna, Jun 22 2012

Logarithmic derivative yields A213684. - Paul D. Hanna, Jun 22 2012

a(n) ~ 3^(3*n+3/2) / (2 * sqrt(2*Pi) * 5^(n+1/2) * n^(3/2)). - Vaclav Kotesovec, Mar 09 2014

a(n) = Catalan(n)*hypergeom([1/2-n/2, -n/2], [-2*n], -4) for n>0. - Peter Luschny, Oct 03 2014

a(n) = [x^n] 1/(1 - x - x^2)^(n+1)/(n + 1). - Ilya Gutkovskiy, Mar 29 2018

a(n) = -Sum_{i=1..n} A217596(i) * a(n-i) for n>0. - Muhammed Sefa Saydam, Jan 27 2025

a(n) = -Sum_{i=1..n+2} A217596(i) * A217596(n-i+2) for n >= 0. - Muhammed Sefa Saydam, Jul 24 2025

Extensions

Revised by Emeric Deutsch and Len Smiley, Jun 05 2005