login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000939 Number of inequivalent n-gons.
(Formerly M1280 N0491)
15
1, 1, 1, 2, 4, 14, 54, 332, 2246, 18264, 164950, 1664354, 18423144, 222406776, 2905943328, 40865005494, 615376173184, 9880209206458, 168483518571798, 3041127561315224, 57926238289970076, 1161157777643184900, 24434798429947993054, 538583682082245127336 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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).

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

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

LINKS

Georg Fischer, Table of n, a(n) for n = 1..450 (first 100 terms by T. D. Noe)

S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.

S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]

A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.

Eric Weisstein's World of Mathematics, Hamiltonian Cycle.

Wikipedia, Hamiltonian path.

Wikipedia, Polygon.

Gus Wiseman, Inequivalent representatives of the  a(6) = 14 cycle necklaces.

Gus Wiseman, Inequivalent representatives of the  a(7) = 54 n-gons.

FORMULA

For formula see Maple lines.

EXAMPLE

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.

n=3: 123.

n=4: 1234, 1243.

n=5: 12345, 12354, 12453, 13524.

n=6: 123456, 123465, 123564, 123645, 123654, 124365, 124635, 124653, 125364, 125463, 125634, 126435, 126453, 135264.

MAPLE

with(numtheory):

# for n odd:

Ed:= proc(n) local t1, d; t1:=0; for d from 1 to n do

       if n mod d = 0 then t1:= t1+phi(n/d)^2*d!*(n/d)^d fi od:

       t1/(2*n^2)

     end:

# for n even:

Ee:= proc(n) local t1, d; t1:= 2^(n/2)*(n/2)*(n/2)!; for d

       from 1 to n do if n mod d = 0 then t1:= t1+

       phi(n/d)^2*d!*(n/d)^d; fi od: t1/(2*n^2)

     end:

A000939:= n-> if n mod 2 = 0 then ceil(Ee(n)) else ceil(Ed(n)); fi:

seq(A000939(n), n=1..25);

MATHEMATICA

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. *)

rotgra[g_, m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m, 1, k+1])];

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 *)

CROSSREFS

Cf. A000940. Bisections give A094154, A094155.

For star polygons see A231091.

Cf. A000031, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.

Sequence in context: A183949 A131180 A047990 * A109154 A030853 A306150

Adjacent sequences:  A000936 A000937 A000938 * A000940 A000941 A000942

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

Added a(1) = 1 and a(2) = 1 by Gus Wiseman, Mar 02 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 22:38 EDT 2019. Contains 322380 sequences. (Running on oeis4.)