A094157 -id:A094157 - cp's OEIS frontend

A000940 Number of n-gons with n vertices.

1, 2, 4, 12, 39, 202, 1219, 9468, 83435, 836017, 9223092, 111255228, 1453132944, 20433309147, 307690667072, 4940118795869, 84241805734539, 1520564059349452, 28963120073957838, 580578894859915650, 12217399235411398127, 269291841184184374868, 6204484017822892034404

Offset: 3

N. J. A. Sloane

Number of inequivalent undirected Hamiltonian cycles in complete graph on n labeled nodes under action of dihedral group of order 2n acting on nodes.

			Label the vertices of a regular n-gon 1,2,...,n.
For n=3,4,5 representatives for the polygons counted here are:
  (1,2,3,1),
  (1,2,3,4,1), (1,2,4,3,1),
  (1,2,3,4,5,1), (1,2,3,5,4,1), (1,2,4,5,3,1), (1,3,5,2,4,1).
For n=6:
  (1,2,3,4,5,6,1), (1,2,3,4,6,5,1), (1,2,3,5,6,4,1),
  (1,2,3,6,5,4,1), (1,2,4,3,6,5,1), (1,2,4,6,3,5,1),
  (1,2,4,6,5,3,1), (1,2,5,3,6,4,1), (1,2,5,4,6,3,1),
  (1,2,5,6,3,4,1), (1,2,6,4,5,3,1), (1,3,5,2,6,4,1).

J. H. Kwak and J. Lee, Enumeration of graph coverings, surface branched coverings and related group theory, in Combinatorial and Computational Mathematics (Pohang, 2000), ed. S. Hong et al., World Scientific, Singapore 2001, pp. 97-161.
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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).

Ludovic Schwob, Table of n, a(n) for n = 3..500 (terms 3..100 from 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]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence, except he has a(6)=7 instead of 12)
R. C. Read, Letter to N. J. A. Sloane, 1992
R. C. Read, Combinatorial problems in theory of music, Discrete Math. 167 (1997), 543-551.
Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See p. 9.
N. J. A. Sloane, Illustration of initial terms [Annotated page from Golomb-Welch article]
Venta Terauds and J. Sumner, Circular genome rearrangement models: applying representation theory to evolutionary distance calculations, arXiv preprint arXiv:1712.00858 [q-bio.PE], 2017.
Venta Terauds and Jeremy Sumner, A new algebraic approach to genome rearrangement models, arXiv:2012.11665 [q-bio.PE], 2020.

Cf. A000939, A007619. Bisections give A094156, A094157.

For permutation classes under various symmetries see A089066, A262480, A002619.

with(numtheory);
# for n odd:
Sd:=proc(n) local t1,d; t1:=2^((n-1)/2)*n^2*((n-1)/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/(4*n^2); end;
# for n even:
Se:=proc(n) local t1,d; t1:=2^(n/2)*n*(n+6)*(n/2)!/4; 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/(4*n^2); end;
A000940:=n-> if n mod 2 = 0 then Se(n) else Sd(n); fi;

a[n_] := (t1 = If[OddQ[n], 2^((n - 1)/2)*n^2*((n - 1)/2)!, 2^(n/2)*n*(n + 6)*(n/2)!/4]; For[ d = 1 , d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[n/d]^2*d!*(n/d)^d]]; t1/(4*n^2)); Table[a[n], {n, 3, 25}] (* Jean-François Alcover, Jun 19 2012, after Maple *)

a(n)={if(n<3, 0, (2^(n\2-2)*(n\2)!*n*if(n%2, 4*n, n + 6) + sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d))/(4*n^2))} \\ Andrew Howroyd, Sep 09 2018

from sympy import factorial, divisors, totient
def A000940(n): return 1 if n == 3 else ((sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n,generator=True))+(1<<(k:=n>>1)-2)*n*(n<<2 if n&1 else (n+6))*factorial(k))>>2)//n//n # Chai Wah Wu, Nov 07 2022

For formula see Maple lines.
a(p) = ((((p-1)! + 1)/p) + p - 2 + (2^((p-1)/2)*((p-1)/2)!))/4 for prime p. See A007619. - Ian Mooney, Oct 05 2022
a(n) ~ sqrt(2*Pi)/4 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

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

A358329 Triangle read by rows: T(n,k) is the number of polygons with 2n sides, of which k run through the center of a circle, on the circumference of which the 2n vertices of the polygon are arranged at equal spacing, up to rotation and reflection.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 4, 3, 3, 2, 70, 60, 54, 12, 6, 2980, 3512, 2088, 704, 156, 28, 268444, 315840, 176928, 59204, 13488, 1920, 193, 36387789, 42112416, 22965696, 7722144, 1759104, 277344, 28992, 1743, 6789078267, 7716280320, 4153217280, 1393136640, 321814080, 53061120, 6216960, 483840, 20640

Offset: 0

Ludovic Schwob, Nov 09 2022

By "2*n-sided polygons" we mean the polygons that can be drawn by connecting 2*n equally spaced points on a circle.
T(0,0)=0 and T(0,1)=1 by convention.
The sequence is limited to even-sided polygons, since all odd-sided polygons have no side passing through the center.

			Triangle begins:
    0;
    0,   1;
    1,   0,   1;
    4,   3,   3,   2;
   70,  60,  54,  12,   6;

Ludovic Schwob, Table of n, a(n) for n = 0..5150

Row sums give A094157(n).

Cf. A330662.

cp's OEIS Frontend

A000940 Number of n-gons with n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A094156 Bisection of A000940.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A358329 Triangle read by rows: T(n,k) is the number of polygons with 2n sides, of which k run through the center of a circle, on the circumference of which the 2n vertices of the polygon are arranged at equal spacing, up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

cp's OEIS Frontend

A000940 Number of n-gons with n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A094156 Bisection of A000940.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A358329 Triangle read by rows: T(n,k) is the number of polygons with 2*n sides, of which k run through the center of a circle, on the circumference of which the 2*n vertices of the polygon are arranged at equal spacing, up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A358329 Triangle read by rows: T(n,k) is the number of polygons with 2n sides, of which k run through the center of a circle, on the circumference of which the 2n vertices of the polygon are arranged at equal spacing, up to rotation and reflection.