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

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,3

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

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 211 (3.2.73-74)

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 (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.

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, 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]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.

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

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

Example

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

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

Prog

(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
(Maxima)
T(n, k):=if n<0 or k<0 then 0 else if n<k then 0 else if n=k then 1 else  if k=0 then 0 else  T(n-1, k-1)+T(n, k+1)+T(n, k+2);
makelist(T(n, 1), n, 1, 10); /* Vladimir Kruchinin, Oct 03 2014 */
(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
(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

Crossrefs

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

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

Sequence in context: A151061 A109085 A259690 * A151062 A000902 A151063

Adjacent sequences: A000999 A001000 A001001 * A001003 A001004 A001005

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Revised by Emeric Deutsch and Len Smiley, Jun 05 2005

Status

approved