A089066 -id:A089066 - 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)!!).

A099030 Number of tone-rows in n-tone music.

Original entry on oeis.org

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

Offset: 3

Ralf Stephan, Sep 27 2004

Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 08 2006, Table of n, a(n) for n = 3..38
Samuel Herman, Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
H. Fripertinger, Enumeration in musical theory, Séminaire Lotharingien de Combinatoire, B26a (1991), 14 pp.

Apart from initial terms, same as A089066. - Ray Jerome, Feb 25 2005

a[n_] := If[OddQ[n], (n-1)! + (n-1)!!, (n-1)! + (n/2 + 1)*(n-2)!!] / 4;
Table[a[n], {n, 3, 38}] (* Jean-François Alcover, Aug 01 2016 *)

doubfact(n)=if(n<2, 1, n*doubfact(n-2));
for(n=3,50,if(n%2==1,print1(((n-1)!+doubfact(n-1))/4,","),print1(((n-1)!+(n/2+1)*doubfact(n-2))/4,","))) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 02 2006

(1/4) [(n-1)!+(n-1)!! ] if n odd, (1/4) [(n-1)!+(n/2+1)(n-2)!! ] if even.

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 02 2006

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

A099030 Number of tone-rows in n-tone music.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions