cp's OEIS Frontend

A003441 Number of nonequivalent dissections of a polygon into n triangles by nonintersecting diagonals rooted at a cell up to rotation.

%I A003441 M2840 #39 Jan 19 2021 11:48:00
%S A003441 1,1,3,10,30,99,335,1144,3978,14000,49742,178296,643856,2340135,
%T A003441 8554275,31429068,115997970,429874830,1598952498,5967382200,
%U A003441 22338765540,83859016956,315614844558,1190680751376,4501802224520,17055399281284
%N A003441 Number of nonequivalent dissections of a polygon into n triangles by nonintersecting diagonals rooted at a cell up to rotation.
%C A003441 Number of dissections of regular (n+2)-gon into n polygons without reflection and rooted at a cell. - _Sean A. Irvine_, May 05 2015
%D A003441 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003441 Andrew Howroyd, <a href="/A003441/b003441.txt">Table of n, a(n) for n = 1..200</a>
%H A003441 Paul Drube and Puttipong Pongtanapaisan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html">Annular Non-Crossing Matchings</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
%H A003441 F. Harary, E. M. Palmer, R. C. Read, <a href="/A000108/a000108_20.pdf">On the cell-growth problem for arbitrary polygons, computer printout, circa 1974</a>
%H A003441 F. Harary, E. M. Palmer and R. C. Read, <a href="http://dx.doi.org/10.1016/0012-365X(75)90041-2">On the cell-growth problem for arbitrary polygons</a>, Discr. Math. 11 (1975), 371-389.
%H A003441 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 A003441 R. C. Read, <a href="/A001004/a001004.pdf">On general dissections of a polygon</a>, Preprint (1974)
%H A003441 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 A003441 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).
%F A003441 Numbers so far suggest that two trisections of sequence agree with those of A050181. - _Ralf Stephan_, Mar 28 2004
%p A003441 [seq(combstruct[count]([C, {C=Cycle(BT,card=3),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];
%t A003441 a[n_] := DivisorSum[GCD[3, n-1], EulerPhi[#] Binomial[(2n+1)/#, (n-1)/#]/ (2n+1)&];
%t A003441 Array[a, 30] (* _Jean-François Alcover_, Jul 02 2018 *)
%o A003441 (PARI) catalan(n) = binomial(2*n, n)/(n+1);
%o A003441 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
%Y A003441 Column k=3 of A295222.
%K A003441 nonn
%O A003441 1,3
%A A003441 _N. J. A. Sloane_
%E A003441 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
%E A003441 Name edited by _Andrew Howroyd_, Nov 20 2017