|
%I M1280 N0491 #62 Dec 04 2022 20:32:41
%S 1,1,1,2,4,14,54,332,2246,18264,164950,1664354,18423144,222406776,
%T 2905943328,40865005494,615376173184,9880209206458,168483518571798,
%U 3041127561315224,57926238289970076,1161157777643184900,24434798429947993054,538583682082245127336
%N Number of inequivalent n-gons.
%C Here two n-gons are said to be equivalent if they differ in starting point, orientation, or by a rotation (but not by a reflection - for that see A000940).
%C Number of cycle necklaces on n vertices, defined as equivalence classes of (labeled, undirected) Hamiltonian cycles under rotation of the vertices. The path version is A275527. - _Gus Wiseman_, Mar 02 2019
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Georg Fischer, <a href="/A000939/b000939.txt">Table of n, a(n) for n = 1..450</a> (first 100 terms by T. D. Noe)
%H S. W. Golomb and L. R. Welch, <a href="http://www.jstor.org/stable/2308978">On the enumeration of polygons</a>, Amer. Math. Monthly, 67 (1960), 349-353.
%H S. W. Golomb and L. R. Welch, <a href="/A000939/a000939.pdf">On the enumeration of polygons</a>, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
%H Samuel Herman and Eirini Poimenidou, <a href="https://arxiv.org/abs/1905.04785">Orbits of Hamiltonian Paths and Cycles in Complete Graphs</a>, arXiv:1905.04785 [math.CO], 2019.
%H A. Stoimenow, <a href="https://doi.org/10.1142/S0218216598000073">Enumeration of chord diagrams and an upper bound for Vassiliev invariants</a>, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Polygon">Polygon</a>.
%H Gus Wiseman, <a href="/A000939/a000939.png">Inequivalent representatives of the a(6) = 14 cycle necklaces</a>.
%H Gus Wiseman, <a href="/A000939/a000939_1.png">Inequivalent representatives of the a(7) = 54 n-gons</a>.
%F For formula see Maple lines.
%F a(2*n + 1) = A002619(2*n + 1)/2 for n > 0; a(2*n) = (A002619(2*n) + A002866(n-1))/2 for n > 1. - _Andrew Howroyd_, Aug 17 2019
%F a(n) ~ sqrt(2*Pi)/2 * n^(n-3/2) / e^n. - _Ludovic Schwob_, Nov 03 2022
%e Possibilities for n-gons without distinguished vertex can be encoded as permutation classes of vertices, two permutations being equivalent if they can be obtained from each other by circular rotation, translation mod n or complement to n+1.
%e n=3: 123.
%e n=4: 1234, 1243.
%e n=5: 12345, 12354, 12453, 13524.
%e n=6: 123456, 123465, 123564, 123645, 123654, 124365, 124635, 124653, 125364, 125463, 125634, 126435, 126453, 135264.
%p with(numtheory):
%p # for n odd:
%p Ed:= proc(n) local t1, d; t1:=0; for d from 1 to n do
%p if n mod d = 0 then t1:= t1+phi(n/d)^2*d!*(n/d)^d fi od:
%p t1/(2*n^2)
%p end:
%p # for n even:
%p Ee:= proc(n) local t1, d; t1:= 2^(n/2)*(n/2)*(n/2)!; for d
%p from 1 to n do if n mod d = 0 then t1:= t1+
%p phi(n/d)^2*d!*(n/d)^d; fi od: t1/(2*n^2)
%p end:
%p A000939:= n-> if n mod 2 = 0 then ceil(Ee(n)) else ceil(Ed(n)); fi:
%p seq(A000939(n), n=1..25);
%t a[n_] := (t = If[OddQ[n], 0, 2^(n/2)*(n/2)*(n/2)!]; Do[If[Mod[n, d]==0, t = t+EulerPhi[n/d]^2*d!*(n/d)^d], {d, 1, n}]; t/(2*n^2)); a[1] := 1; a[2] := 1; Print[a /@ Range[1, 450]] (* _Jean-François Alcover_, May 19 2011, after Maple prog. *)
%t rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
%t Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* _Gus Wiseman_, Mar 02 2019 *)
%o (PARI) a(n)={if(n<3, n>=0, (if(n%2, 0, (n/2-1)!*2^(n/2-2)) + sumdiv(n, d, eulerphi(n/d)^2 * d! * (n/d)^d)/n^2)/2)} \\ _Andrew Howroyd_, Aug 17 2019
%Y Cf. A000940. Bisections give A094154, A094155.
%Y For star polygons see A231091.
%Y Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.
%K nonn,nice,easy
%O 1,4
%A _N. J. A. Sloane_
%E More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004
%E Added a(1) = 1 and a(2) = 1 by _Gus Wiseman_, Mar 02 2019
|
