A003441 Number of nonequivalent dissections of a polygon into n triangles by nonintersecting diagonals rooted at a cell up to rotation.
1, 1, 3, 10, 30, 99, 335, 1144, 3978, 14000, 49742, 178296, 643856, 2340135, 8554275, 31429068, 115997970, 429874830, 1598952498, 5967382200, 22338765540, 83859016956, 315614844558, 1190680751376, 4501802224520, 17055399281284
Offset: 1
Keywords
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..200
- Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
- 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.
- R. C. Read, On general dissections of a polygon, Preprint (1974)
- Ronald C. Read, On general dissections of a polygon, Aequat. Math. 18 (1978) 370-388.
Crossrefs
Column k=3 of A295222.
Programs
-
Maple
[seq(combstruct[count]([C, {C=Cycle(BT,card=3),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)]; -
Mathematica
a[n_] := DivisorSum[GCD[3, n-1], EulerPhi[#] Binomial[(2n+1)/#, (n-1)/#]/ (2n+1)&]; Array[a, 30] (* Jean-François Alcover, Jul 02 2018 *)
-
PARI
catalan(n) = binomial(2*n, n)/(n+1); a(n) = binomial(2*n+1, n-1)/(2*n+1) + 2/3*(if ((n-1) % 3, 0, catalan((n-1)/3))); \\ Michel Marcus, Jan 23 2016
Formula
a(n) = number of necklaces of n-1 white beads and n+2 black beads. a(n) = binomial(2n+1, n-1)/(2n+1) + (2/3)*C((n-1)/3) where C is the Catalan number A000108 (assumed to be 0 for nonintegral argument). G.f.: ( ((1-sqrt(1-4x))/2)^3 + (1-sqrt(1-4x^3)) )/(3x^2).
Numbers so far suggest that two trisections of sequence agree with those of A050181. - Ralf Stephan, Mar 28 2004
Extensions
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
Name edited by Andrew Howroyd, Nov 20 2017
Comments