A000131 Number of asymmetrical dissections of n-gon. (Formerly M1535 N0599)

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

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]

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

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

Prog

(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

Crossrefs

Cf. A000063.

Sequence in context: A246167 A359725 A000941 * A328041 A242785 A359672

Adjacent sequences: A000128 A000129 A000130 * A000132 A000133 A000134

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Extended by Joseph Myers, Jun 21 2012

Status

approved