A003446 Number of nonequivalent dissections of a polygon into n triangles by nonintersecting diagonals rooted at a cell up to rotation and reflection.
0, 1, 1, 2, 6, 16, 52, 170, 579, 1996, 7021, 24892, 89214, 321994, 1170282, 4277352, 15715249, 57999700, 214939846, 799478680, 2983699498, 11169391168, 41929537871, 157807451672, 595340479694, 2250901216266, 8527700012092, 32369067177176
Offset: 0
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751.
- S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]
- F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
- F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
- P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
- Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388, Table 1.
- P. K. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
- P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]
Crossrefs
Column k=3 of A295259.
Programs
-
Mathematica
c[x_] = (1 - Sqrt[1 - 4*x])/(2*x); d[x_] = 1 + x*c[x^2]; f[x_] = (x/6)*(c[x]^3 + 2*c[x^3] + 3*d[x]*c[x^2]); CoefficientList[ Series[ f[x], {x, 0, 27}], x] (* Jean-François Alcover, Sep 30 2011, after g.f. *)
Formula
Let c(x) = (1-sqrt(1-4*x))/(2*x) = g.f. for Catalan numbers (A000108), let d(x) = 1+x*c(x^2). Then g.f. is (x/6)*(c^3+2*subs(x=x^3, c)+3*d*subs(x=x^2, c)).
Recurrence: n*(n+1)*(n+2)*(12*n^10 - 396*n^9 + 5713*n^8 - 47417*n^7 + 250708*n^6 - 883176*n^5 + 2104831*n^4 - 3368071*n^3 + 3489712*n^2 - 2133004*n + 587808)*a(n) = 2*(n-1)*n*(n+1)*(24*n^10 - 756*n^9 + 10262*n^8 - 78647*n^7 + 374743*n^6 - 1154043*n^5 + 2323495*n^4 - 3057578*n^3 + 2632172*n^2 - 1456776*n + 412560)*a(n-1) + 4*(n-1)*n*(12*n^11 - 384*n^10 + 5377*n^9 - 43234*n^8 + 219811*n^7 - 731024*n^6 + 1576767*n^5 - 2055172*n^4 + 1195025*n^3 + 527398*n^2 - 1223056*n + 534240)*a(n-2) - 2*(72*n^13 - 2484*n^12 + 37950*n^11 - 339019*n^10 + 1971954*n^9 - 7887993*n^8 + 22425262*n^7 - 46437513*n^6 + 71577166*n^5 - 83189763*n^4 + 71509420*n^3 - 41716412*n^2 + 13543200*n - 1451520)*a(n-3) - 4*(n-1)*n*(2*n - 7)*(24*n^10 - 756*n^9 + 10262*n^8 - 78647*n^7 + 374743*n^6 - 1154043*n^5 + 2323495*n^4 - 3057578*n^3 + 2632172*n^2 - 1456776*n + 412560)*a(n-4) - 8*(n-1)*(2*n - 9)*(12*n^11 - 384*n^10 + 5377*n^9 - 43234*n^8 + 219811*n^7 - 731024*n^6 + 1576767*n^5 - 2055172*n^4 + 1195025*n^3 + 527398*n^2 - 1223056*n + 534240)*a(n-5) + 16*(n-6)*(2*n - 11)*(2*n - 9)*(12*n^10 - 276*n^9 + 2689*n^8 - 14529*n^7 + 48009*n^6 - 101629*n^5 + 142510*n^4 - 137838*n^3 + 93836*n^2 - 39760*n + 6720)*a(n-6). - Vaclav Kotesovec, Aug 13 2013
a(n) ~ 4^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013
Extensions
Name edited by Andrew Howroyd, Nov 20 2017
Comments