A000940 -id:A000940 - cp's OEIS frontend

A094157 Bisection of A000940.

2, 12, 202, 9468, 836017, 111255228, 20433309147, 4940118795869, 1520564059349452, 580578894859915650, 269291841184184374868, 149146250420586942401004, 97222048664558428304285193, 73681349947834075264704425280, 64240926985765124116695616020874, 63847923667734462963941294951243328

Offset: 2

N. J. A. Sloane, May 05 2004

nonn

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

Cf. A000940, A094156.

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

A094156 Bisection of A000940.

Original entry on oeis.org

1, 4, 39, 1219, 83435, 9223092, 1453132944, 307690667072, 84241805734539, 28963120073957838, 12217399235411398127, 6204484017822892034404, 3734180195629471796396217, 2628347798377200707293720724, 2139135966227357959535426526975, 1993415431315860419823374898234950

Offset: 1

N. J. A. Sloane, May 05 2004

nonn

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

Cf. A000940, A094157.

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

A342533 a(n) is the number of n-gons in A000940 that display symmetry (reflection / rotation).

Original entry on oeis.org

1, 2, 4, 11, 24, 81, 193, 772, 1920, 8735, 23040

Offset: 3

Ian Mooney, Mar 14 2021

			Of the A000940(6)=12 hexagons, 11 have symmetry and 1 is asymmetric, so a(6)=11.

Cf. A000940.

a(p) = (2^((p-1)/2)*((p-1)/2)!)/2 for prime p.

A004577 Erroneous version of A000940.

Original entry on oeis.org

1, 2, 4, 7, 39, 202, 1219, 9468, 83435, 80017

Offset: 3

N. J. A. Sloane, Sep 09 2014

dead

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

R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971
R. C. Read, Letter to N. J. A. Sloane, 1992

A357602 a(n) is the number of n-gons in A000940 that are asymmetric.

Original entry on oeis.org

0, 0, 0, 1, 15, 121, 1026, 8696, 81515, 827282, 9200052

Offset: 3

Ian Mooney, Oct 05 2022

			Of the A000940(6) = 12 hexagons, 11 have symmetry and 1 is asymmetric, so a(6)=1.

Cf. A000940, A342533.

a(n) = A000940(n) - A342533(n).

a(p) = ((((p-1)! + 1)/p) + p - 2 - (2^((p-1)/2)*((p-1)/2)!))/4 for prime p. See A007619.

A000939 Number of inequivalent n-gons.

Original entry on oeis.org

1, 1, 1, 2, 4, 14, 54, 332, 2246, 18264, 164950, 1664354, 18423144, 222406776, 2905943328, 40865005494, 615376173184, 9880209206458, 168483518571798, 3041127561315224, 57926238289970076, 1161157777643184900, 24434798429947993054, 538583682082245127336

Offset: 1

N. J. A. Sloane

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

			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.

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

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]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
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.

Cf. A000940. Bisections give A094154, A094155.
For star polygons see A231091.
Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.

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

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

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

For formula see Maple lines.
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
a(n) ~ sqrt(2*Pi)/2 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

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

A002619 Number of 2-colored patterns on an n X n board.

Original entry on oeis.org

1, 1, 2, 3, 8, 24, 108, 640, 4492, 36336, 329900, 3326788, 36846288, 444790512, 5811886656, 81729688428, 1230752346368, 19760413251956, 336967037143596, 6082255029733168, 115852476579940152, 2322315553428424200, 48869596859895986108

Offset: 1

N. J. A. Sloane, Colin Mallows

Also number of orbits in the set of circular permutations (up to rotation) under cyclic permutation of the elements. - Michael Steyer, Oct 06 2001

Moser shows that (1/n^2)*Sum_{d|n} k^d*phi(n/d)^2*(n/d)^d*d! is an integer. Here we have k=1. - Michel Marcus, Nov 02 2012

			n=6: {(123456)}, {(135462), (246513), (351624)} and {(124635), (235146), (346251), (451362), (562413), (613524)} are 3 of the 24 orbits, consisting of 1, 3 and 6 permutations, respectively.

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).
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
K. Yordzhev, On the cardinality of a factor set in the symmetric group. Asian-European Journal of Mathematics, Vol. 7, No. 2 (2014) 1450027, doi: 10.1142/S1793557114500272, ISSN:1793-5571, E-ISSN:1793-7183, Zbl 1298.05035.

T. D. Noe, Table of n, a(n) for n = 1..100
M. Kazarian, E. Krasilnikov, S. Lando, and M. Shapiro, Generalized chord diagrams and weight systems, arXiv:2505.24491 [math.CO], 2025. See Theorem 5.3 p. 24.
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
W. O. J. Moser, A (modest) generalization of the theorems of Wilson and Fermat, Canad. Math. Bull. 33(1990), pp. 253-256.
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, Notes on A002618, A002619, etc.
András Szilárd, A combinatorial generalization of Wilson's theorem, Australasian Journal of Combinatorics, Volume 49 (2011), Pages 265-272. See Theorem 3.c p. 269.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
A. Vella, Pattern avoidance in permutations: linear and cyclic orders, Electron. J. Combin. 9 (2002/03), no. 2, #R18, 43 pp.
K. Yordzhev, On the cardinality of a factor set in the symmetric group, arXiv:1410.8408 [math.CO], 2014. See Table 2 p. 14.
Saeed Zakeri, Cyclic Permutations: Degrees and Combinatorial Types, arXiv:1909.03300 [math.DS], 2019. See Table 2 p. 10.

Cf. A002618, A047916, A064852, A064649.
Cf. A000010.
Cf. A000939, A000940, A089066, A262480, A275527 (other classes of permutations under various symmetries).

with(numtheory): a:=proc(n) local div: div:=divisors(n): sum(phi(div[j])^2*(n/div[j])!*div[j]^(n/div[j]),j=1..tau(n))/n^2 end: seq(a(n),n=1..23); # Emeric Deutsch, Aug 23 2005

a[n_] := EulerPhi[#]^2*(n/#)!*#^(n/#)/n^2 & /@ Divisors[n] // Total; a /@ Range[23] (* Jean-François Alcover, Jul 11 2011, after Emeric Deutsch *)

a(n)={sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d)/n^2} \\ Andrew Howroyd, Sep 09 2018

from sympy import totient, factorial, divisors
def A002619(n): return sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n,generator=True))//n**2 # Chai Wah Wu, Nov 07 2022

a(n) = Sum_{k|n} u(n, k)/(nk), where u(n, k) = A047918(n, k).
a(n) = (1/n^2)*Sum_{d|n} phi(d)^2*(n/d)!*d^(n/d), where phi is Euler's totient function (A000010). - Emeric Deutsch, Aug 23 2005
From Richard L. Ollerton, May 09 2021: (Start)
Let A(n,k) = (1/n^2)*Sum_{d|n} k^d*phi(n/d)^2*(n/d)^d*d!, then:
A(n,k) = (1/n^2)*Sum_{i=1..n} k^gcd(n,i)*phi(n/gcd(n,i))*(n/gcd(n,i))^gcd(n,i)*gcd(n,i)!.
A(n,k) = (1/n^2)*Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))^2*(gcd(n,i))^(n/gcd(n,i))*(n/gcd(n,i))!.
a(n) = A(n,1). (End)

A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

Original entry on oeis.org

1, 1, 1, 4, 12, 64, 360, 2544, 20160, 181632

Offset: 1

Olivier Gérard, Jul 31 2016

Let us consider two permutations to be equivalent if they can be obtained from each other by cyclic rotation (12345->(23451,34512,45123,51234) or n+1-complement (31254->35412), or a combination of those two transformations (they commute with each other). a(n) is the number of classes.
We obtain the same number of classes if the transformations are (addition of a constant modulo n and reversal (12345->54321)) but not the same set of representatives.
It seems probable that a(2n+1) = (2n)!/2
This sequence may be related to A113247 (and A113248) as they share a common dissection 1, 4, 64, 2544, 181632. The fact that they count permutation classes for the major index is a further indication.
Number of path necklaces, defined as equivalence classes of (labeled, undirected) Hamiltonian paths under rotation of the vertices. The cycle version is A000939. - Gus Wiseman, Mar 02 2019

			Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.
n=4 case addition mod n and reversal
1234, 1243, 1324, 1423.
n=4 case rotation and complement
1234, 1243, 1324, 1342.
.
n=5 case addition mod n and reversal
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.
n=5 case rotation and complement
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.

Wikipedia, Hamiltonian path.
Wikipedia, Necklace (combinatorics).
Gus Wiseman, Inequivalent representatives of the a(5) = 12 path necklaces.
Gus Wiseman, Inequivalent representatives of the a(6) = 54 path necklaces.

Cf. A000939, A000940, A002619, A089066, A262480 (other symmetry classes of permutations).
Cf. A193651 (inspiration for a(2n)).
Cf. A000031, A006125, A008965, A059966, A060223, A192332, A323858, A323870, A324461.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

(Conjecture). If n odd a(n)=((n - 1))!/2. If n even a(n)= 1/2 (n - 2)!! (1 + ( n - 1)!!).

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 27, 175, 1533, 14361, 151575, 1735869, 21594863, 289365383, 4158887007, 63822480809, 1041820050629, 18027531255745, 329658402237171, 6352776451924233, 128686951765990343, 2733851297673484765, 60781108703102022027, 1411481990523638719737

Offset: 1

Stewart Gordon, Nov 03 2013

For polygons in general see A000939 and A000949, and especially the Golomb-Welch reference. - N. J. A. Sloane, Nov 21 2013

			For n=5, only solution is the regular pentagram.
For n=6, only solution is the unicursal hexagram (see Wikipedia link).
For n=7, two regular heptagrams and three irregular forms are possible.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Stewart Gordon, The five possible stars for n=7 (SVG file)
Wikipedia, Unicursal hexagram

Cf. A000939 (if edges may join adjacent vertices), A000940, A002816 (rotations and reflections counted separately), A326411, A370459 (up to rotations and reflections), A370068 (directed edges).

Cf. A283184.

\\ Requires a370068 from A370068, b(n) is A283184.
b(n)={subst(serlaplace(polcoef((1 - x)/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)}
a(n)={(if(n%2==0 && n > 2, b(n/2-1)/2) + a370068(n))/2} \\ Andrew Howroyd, Mar 01 2024

a(n) = (A370068(n) + A283184(n/2-1)/2)/2 for even n >= 4; a(n) = A370068(n)/2 for odd n. - Andrew Howroyd, Feb 24 2024

a(15) onwards from Andrew Howroyd, Feb 23 2024

A089066 Number of distinct classes of permutations of length n under reversal, rotation and complement to n+1.

Original entry on oeis.org

1, 1, 1, 3, 8, 38, 192, 1320, 10176, 91296, 908160, 9985920, 119761920, 1556847360, 21794734080, 326920043520, 5230700052480, 88921882828800, 1600593472880640, 30411275613143040, 608225502973132800

Offset: 1

Ray Jerome, Dec 02 2003, Jul 17 2007

nonn

Contribution from Olivier Gérard, Jul 31 2016: (Start)
Let us consider two permutations to be equivalent if they can be obtained from each other by reversal (12345->54321), cyclic rotation (12345->(23451,34512,45123,51234), n+1-complement (31254->35412), or a combination of those three transformations (they commute with each other). a(n) is the number of classes. It is strictly inferior to (n-1)! for n>1.
If rotation is replaced by addition of a constant modulo n, one obtains the same number of classes but not exactly the same permutations starting n=5.
(End)
Original explanation by R. Jerome : Generate all permutations of a string of length n, such as 1234, which has length 4; there are n!=24 of these. Now remove all that have cycles less than 4 characters long; if you only use cyclic notation and not array notation then of the n! possibly only (n-1)! need to be considered. Then calculate the Inverse, Vertical reflection, [VErt reflection inverse], Rotation by 180 degree and [ROt by 180 deg inverse]. If any of these already exist on the list then this permutation is not distinct. Items in []'s are unnecessary since VE(x)=V(I(x))=I(V(x))=R(x) and RO(x)=R(I(x))=I(R(x))=V(x). There are some that are rotationally symmetric and some that are vertically symmetric (only possible for even lengths), but the majority are nonsymmetric.

			Examples of permutations (notations of R. Jerome):
Rotationally symmetric: x1=R(x1)=124356=VE(x1), I(x1)=165342=V(x1)=RO(x1)
Vertically symmetric: x2=V(x2)=132645=RO(x2)), I(x2)=154623=R(x2)=VE(x2)
Nonsymmetric: x3=135264, I(x3)=146253, R(x3)=152463=VE(x3), V(x3)=136425=RO(x3)
a(4)=3: there are 3 distinct permutations of exactly length 4, out of a field of 4!=24 possible permutations. In cyclic notation they are designated (1234), (1243) and (1324). The others, (1342), (1423) and (1432), are equal to inverses, vertical mirror images or 180-degree rotations of those 3. The remaining 18 have cycles of length 1, 2 or 3, such as (143)(2) having a permutation of length 3 and a fixed cycle and (14)(23) having 2 permutations of length 2.
Examples of permutation representatives (from Olivier Gerard)
The representative is chosen to be the first of the class in lexicographic order.
n=4 both cases
1234,1243,1324
n=5 case rotation, reversal, complement
12345,12354,12435,12453,12534,13425,13524,14325
n=5 case translation mod, reversal, complement
12345,12354,12435,12453,12534,13425,13452,13524

J. Gebel, Integer points on Mordell curves [Cached copy, after the original web site tnt.math.se.tmu.ac.jp was shut down in 2017]
Samuel Herman, Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
R. Jerome, Information for Unique Permutations.

Apart from initial terms, same as A099030. - Ray Jerome, Feb 25 2005
Cf. A000939 (same idea under (rotation, addition mod n and reversal) or (rotation, addition mod n and complement)).
Cf. A000940 (same idea under (rotation, addition mod n, reversal and complement)).
Cf. A001710 (shifted, same idea under (rotation and reversal) or (addition mod n and complement)).
Cf. A002619 (same idea under (rotation and addition mod n)).
Cf. A262480 (same idea under (reversal and complement)).
cf. A275527 (same idea under (rotation and complement) or (addition mod n and reversal)).

(* From the formula in A099030 *)
a[n_] := If[n < 3, 1, 1/4 If[Mod[n, 2] == 0,((n - 1)! + (n/2 + 1) (n - 2)!!), ((n - 1)! + (n - 1)!!)]]; Table[a[n], {n, 1, 20}]

Definition changed and cross-references added by Olivier Gérard, Jul 31 2016

cp's OEIS Frontend

A094157 Bisection of A000940.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A094156 Bisection of A000940.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A342533 a(n) is the number of n-gons in A000940 that display symmetry (reflection / rotation).

Views

Author

Keywords

Examples

Crossrefs

Formula

A004577 Erroneous version of A000940.

Views

Author

Keywords

References

Links

A357602 a(n) is the number of n-gons in A000940 that are asymmetric.

Views

Author

Keywords

Examples

Crossrefs

Formula

A000939 Number of inequivalent n-gons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A002619 Number of 2-colored patterns on an n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Views