A000131 Number of asymmetrical dissections of n-gon.

2, 5, 21, 61, 214, 669, 2240, 7330, 24695, 83257, 284928, 981079, 3410990, 11937328, 42075242, 149171958, 531866972, 1905842605, 6861162880, 24805692978, 90035940227, 327987890608, 1198853954688, 4395797189206, 16165195705544, 59609156824273, 220373268471398, 816677398144221

Offset: 7

Author

N. J. A. Sloane

Keywords

• nonn

Comments

This sequence, U_n in Guy's 1958 paper, counts triangulations of a regular n-gon into n-2 triangles with no nonidentity symmetries. Triangulations related by a symmetry of the underlying n-gon do not count as distinct. - Joseph Myers, Jun 21 2012

References

• R. K. Guy, Dissecting a polygon into triangles, Bull. Malayan Math. Soc., Vol. 5, pp. 57-60, 1958.
• R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
• 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

• Joseph Myers, Table of n, a(n) for n = 7..1000
• 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]
• R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967. [Annotated scanned copy]

Crossrefs

Cf. A000063.

Programs

Mathematica

catalan[n_] := Block[{c = Binomial[2 n, n]/(n + 1)}, If[IntegerQ[c], c, 0]]; f[n_] := (catalan[n - 2] - (n/2) catalan[n/2 - 1] - n*catalan[Floor[n/2] - 1] - (n/3)*catalan[n/3 - 1] + n*catalan[n/4 - 1] + n*catalan[n/6 - 1])/(2 n); Array[f, 28, 7] (* Robert G. Wilson v, Jun 23 2014 *)

PARI

C(n)=if(denominator(n)==1,binomial(2*n,n)/(n+1),0)
a(n)=(C(n-2)/n-C(n/2-1)/2-C(n\2-1)-C(n/3-1)/3+C(n/4-1)+C(n/6-1))/2 \\ Charles R Greathouse IV, Apr 05 2013

Formula

a(n) = (Catalan(n-2) - (n/2)*Catalan(n/2 - 1) - n*Catalan(floor(n/2) - 1) - (n/3)*Catalan(n/3 - 1) + n*Catalan(n/4 - 1) + n*Catalan(n/6 - 1))/(2*n), where Catalan(x) = 0 for noninteger x (derived from Guy's 1958 paper). - Joseph Myers, Jun 21 2012

Extensions

Extended by Joseph Myers, Jun 21 2012