A262480 -id:A262480 - cp's OEIS frontend

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

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)

A000940 Number of n-gons with n vertices.

Original entry on oeis.org

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

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

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

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

A000940 Number of n-gons with n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions