A000939 - OEIS

%I M1280 N0491 #63 Feb 16 2025 08:32:22

%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="https://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,changed

%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