cp's OEIS Frontend

A220881 Number of nonequivalent dissections of an n-gon into n-3 polygons by nonintersecting diagonals up to rotation.

%I A220881 #29 Jan 19 2021 11:48:00
%S A220881 1,1,4,12,43,143,504,1768,6310,22610,81752,297160,1086601,3991995,
%T A220881 14732720,54587280,202997670,757398510,2834510744,10637507400,
%U A220881 40023636310,150946230006,570534578704,2160865067312,8199711378716,31170212479588,118686578956272
%N A220881 Number of nonequivalent dissections of an n-gon into n-3 polygons by nonintersecting diagonals up to rotation.
%C A220881 This is almost identical to A003444, but has a different offset and a more precise definition.
%C A220881 In other words, the number of almost-triangulations of an n-gon modulo the cyclic action.
%C A220881 Equivalently, the number of edges of the (n-3)-dimensional associahedron modulo the cyclic action.
%C A220881 The dissection will always be composed of one quadrilateral and n-4 triangles. - _Andrew Howroyd_, Nov 25 2017
%C A220881 Also number of necklaces of 2 colors with 2n-4 beads and n black ones. - _Wouter Meeussen_, Aug 03 2002
%D A220881 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A220881 D. Bowman and A. Regev, <a href="http://arxiv.org/abs/1209.6270">Counting symmetry classes of dissections of a convex regular polygon</a>, arXiv:1209.6270 [math.CO], 2012.
%H A220881 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 A220881 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.
%F A220881 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
%p A220881 C:=n->binomial(2*n,n)/(n+1);
%p A220881 T2:= proc(n) local t1; global C;
%p A220881 t1 :=  (n-3)*C(n-2)/(2*n);
%p A220881 if n mod 4 = 0 then t1:=t1+C(n/4-1)/2 fi;
%p A220881 if n mod 2 = 0 then t1:=t1+C(n/2-1)/4 fi;
%p A220881 t1; end;
%p A220881 [seq(T2(n),n=4..40)];
%t A220881 c[n_] := Binomial[2*n, n]/(n+1);
%t A220881 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];
%t A220881 Table[T2[n], {n, 4, 40}] (* _Jean-François Alcover_, Nov 23 2017, translated from Maple *)
%t A220881 a[n_] := Sum[EulerPhi[d]*Binomial[(2n-4)/d, n/d], {d, Divisors[GCD[2n-4, n] ]}]/(2n-4);
%t A220881 Array[a, 30, 4] (* _Jean-François Alcover_, Dec 02 2017, after _Andrew Howroyd_ *)
%o A220881 (PARI)
%o A220881 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
%Y A220881 A diagonal of A295633.
%Y A220881 Cf. A003444, A003445.
%Y A220881 Cf. A003442, A003447, A003449.
%K A220881 nonn
%O A220881 4,3
%A A220881 _N. J. A. Sloane_, Dec 28 2012
%E A220881 Name clarified by _Andrew Howroyd_, Nov 25 2017