login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001002 Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.
(Formerly M2852 N1146)
20
1, 1, 3, 10, 38, 154, 654, 2871, 12925, 59345, 276835, 1308320, 6250832, 30142360, 146510216, 717061938, 3530808798, 17478955570, 86941210950, 434299921440, 2177832612120, 10959042823020, 55322023332420, 280080119609550 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

T. D. Noe, Table of n, a(n) for n=0..100

P. Barry, On the Central Coefficients of Bell Matrices, J. Int. Seq. 14 (2011) # 11.4.3, example 7.

D. Birmajer, J. B. Gil, 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.

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

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

Index entries for reversions of series

FORMULA

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

a(n) = sum(binomial(n+k, k)*binomial(k, n-k), k=ceil(n/2)..n)/(n+1). - Len Smiley

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

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

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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 14:25 EST 2017. Contains 294893 sequences.