|
|
A000939
|
|
Number of inequivalent n-gons.
(Formerly M1280 N0491)
|
|
17
|
|
|
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
|
|
|
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:
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
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
|
|
|
|