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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A220881 Number of nonequivalent dissections of an n-gon into n-3 polygons by nonintersecting diagonals up to rotation. 6
1, 1, 4, 12, 43, 143, 504, 1768, 6310, 22610, 81752, 297160, 1086601, 3991995, 14732720, 54587280, 202997670, 757398510, 2834510744, 10637507400, 40023636310, 150946230006, 570534578704, 2160865067312, 8199711378716, 31170212479588, 118686578956272 (list; graph; refs; listen; history; text; internal format)
OFFSET

4,3

COMMENTS

This is almost identical to A003444, but has a different offset and a more precise definition.

In other words, the number of almost-triangulations of an n-gon modulo the cyclic action.

Equivalently, the number of edges of the (n-3)-dimensional associahedron modulo the cyclic action.

The dissection will always be composed of one quadrilateral and n-4 triangles. - Andrew Howroyd, Nov 25 2017

Also number of necklaces of 2 colors with 2n-4 beads and n black ones. - Wouter Meeussen, Aug 03 2002

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=4..30.

D. Bowman and A. Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv:1209.6270 [math.CO], 2012.

P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.

C. R. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.

FORMULA

a(n) = (1/(2n-4)) Sum_{d |(2n-4, n)} phi(d)*binomial((2n-4)/d, n/d) for n >= 4. - Wouter Meeussen, Aug 03 2002

MAPLE

C:=n->binomial(2*n, n)/(n+1);

T2:= proc(n) local t1; global C;

t1 :=  (n-3)*C(n-2)/(2*n);

if n mod 4 = 0 then t1:=t1+C(n/4-1)/2 fi;

if n mod 2 = 0 then t1:=t1+C(n/2-1)/4 fi;

t1; end;

[seq(T2(n), n=4..40)];

MATHEMATICA

c[n_] := Binomial[2*n, n]/(n+1);

T2[n_] := Module[{t1}, t1 = (n-3)*c[n-2]/(2*n); If[Mod[n, 4] == 0, t1 = t1 + c[n/4-1]/2]; If[Mod[n, 2] == 0, t1 = t1 + c[n/2-1]/4]; t1];

Table[T2[n], {n, 4, 40}] (* Jean-François Alcover, Nov 23 2017, translated from Maple *)

a[n_] := Sum[EulerPhi[d]*Binomial[(2n-4)/d, n/d], {d, Divisors[GCD[2n-4, n] ]}]/(2n-4);

Array[a, 30, 4] (* Jean-François Alcover, Dec 02 2017, after Andrew Howroyd *)

PROG

(PARI)

a(n) = if(n>=4, sumdiv(gcd(2*n-4, n), d, eulerphi(d)*binomial((2*n-4)/d, n/d))/(2*n-4)) \\ Andrew Howroyd, Nov 25 2017

CROSSREFS

A diagonal of A295633.

Cf. A003444, A003445.

Cf. A003442, A003447, A003449.

Sequence in context: A197659 A292287 A003444 * A149355 A149356 A149357

Adjacent sequences:  A220878 A220879 A220880 * A220882 A220883 A220884

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Dec 28 2012

EXTENSIONS

Name clarified by Andrew Howroyd, Nov 25 2017

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 15:05 EDT 2019. Contains 322209 sequences. (Running on oeis4.)