login
Number of nonequivalent dissections of an n-gon into (n-3) polygons by nonintersecting diagonals rooted at a cell up to rotation.
(Formerly M2002)
5

%I M2002 #39 Jan 19 2021 11:48:00

%S 1,2,11,48,208,858,3507,14144,56698,226100,898942,3565920,14124496,

%T 55887930,220985795,873396480,3450940830,13633173180,53855628554,

%U 212750148000,840496068160,3320817060132,13122294166126,51860761615488

%N Number of nonequivalent dissections of an n-gon into (n-3) polygons by nonintersecting diagonals rooted at a cell up to rotation.

%C Number of dissections of regular n-gon into n-3 polygons without reflection and rooted at a cell. - _Sean A. Irvine_, May 05 2015

%C The conditions imposed mean that the dissection will always be composed of one quadrilateral and n-4 triangles. - _Andrew Howroyd_, Nov 23 2017

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

%H Andrew Howroyd, <a href="/A003442/b003442.txt">Table of n, a(n) for n = 4..200</a>

%H P. Lisonek, <a href="http://dx.doi.org/10.1006/jsco.1995.1066">Closed forms for the number of polygon dissections</a>, Journal of Symbolic Computation 20 (1995), 595-601.

%H Ronald C. Read, <a href="http://dx.doi.org/10.1007/BF03031688">On general dissections of a polygon</a>, Aequat. math. 18 (1978) 370-388.

%H Andrey Zabolotskiy, <a href="/A003442/a003442.png">Illustration for n = 4,5,6</a>

%e Case n=5: A pentagon can be dissected into 1 quadrilateral and 1 triangle. Either one of these can be chosen as the root cell so a(n)=2. - _Andrew Howroyd_, Nov 23 2017

%o (PARI)

%o DissectionsModCyclicRooted(v)={my(n=#v);

%o my(q=vector(n)); q[1]=serreverse(x-sum(i=3,#v,x^i*v[i])/x + O(x*x^n));

%o for(i=2, n, q[i]=q[i-1]*q[1]);

%o my(vars=variables(q[1]));

%o my(u(m,r)=substvec(q[r]+O(x^(n\m+1)), vars, apply(t->t^m,vars)));

%o my(p=O(x*x^n) + sum(i=3, #v, my(c=v[i]); if(c, c*sumdiv(i, d, eulerphi(d)*u(d,i/d))/i)));

%o vector(n,i,polcoeff(p,i))}

%o { my(v=DissectionsModCyclicRooted(apply(i->if(i>=3&&i<=4,y^(i-3) + O(y^2)), [1..25]))); apply(p->polcoeff(p,1), v[4..#v]) } \\ _Andrew Howroyd_, Nov 22 2017

%Y Cf. A003443, A003454, A220881, A295622.

%K nonn

%O 4,2

%A _N. J. A. Sloane_

%E More terms from _Sean A. Irvine_, May 05 2015

%E Name clarified by _Andrew Howroyd_, Nov 22 2017