A006841 -id:A006841 - cp's OEIS frontend

A003223 Erroneous version of A006841.

Original entry on oeis.org

1, 2, 4, 10, 28, 130

Offset: 3

N. J. A. Sloane

dead

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 171.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

V. Meally, Letter to N. J. A. Sloane, Feb 1975.
E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.

Cf. A003224, A003225, A006841 (correct version).

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Original entry on oeis.org

1, 2, 4, 10, 28, 136, 726, 5100, 40362, 363288, 3628810, 39921044, 479001612, 6227066928, 87178295296, 1307675013928, 20922789888016, 355687438476444, 6402373705728018, 121645100594641896, 2432902008177690360, 51090942175425331320, 1124000727777607680022

Offset: 1

Antti Karttunen, May 02 2001

If permutations are converted to (i,p(i)) permutation arrays, then this automorphism is obtained by their "SW-NE diagonal toroidal shifts" (see Matthias Engelhardt's Java program in A006841), while the Maple procedure below converts each permutation to a siteswap pattern (used in juggling), rotates it by one digit and converts the resulting new (or same) siteswap pattern back to a permutation.
When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.
The number of conjugacy classes of the symmetric group of degree n when conjugating only with the cyclic permutation group of degree n. - Attila Egri-Nagy, Aug 15 2014
Also the number of equivalence classes of permutations of {1...n} under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514). - Gus Wiseman, Mar 04 2019

			If I have a five-element permutation like 25431, in cycle notation (1 2 5)(3 4), I mark the numbers 1-5 clockwise onto a circle and draw directed edges from 1 to 2, from 2 to 5, from 5 to 1 and a double-way edge between 3 and 4. All the 5-element permutations that produce some rotation (discarding the labels of the nodes) of that chord diagram belong to the same equivalence class with 25431. The sequence gives the count of such equivalence classes.

Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul).
A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.
A064636 (derangements-the same automorphism).
A061417[n] = A064649[n]/n.
Cf. A000031, A000939, A002995, A008965, A060223, A064640, A086675 (digraphical necklaces), A179043, A192332, A275527 (path necklaces), A323858, A323859, A323870, A324513, A324514 (aperiodic permutations).

List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014

a061417 = sum . a047917_row  -- Reinhard Zumkeller, Mar 19 2014

Algebraic formula: with(numtheory); SSRPCC := proc(n) local d,s; s := 0; for d in divisors(n) do s := s + phi(n/d)*((n/d)^d)*(d!); od; RETURN(s/n); end;
Empirically: with(group); SiteSwapRotationPermutationCycleCounts := proc(upto_n) local b,u,n,a,r; a := []; for n from 1 to upto_n do b := []; u := n!; for r from 0 to u-1 do b := [op(b),1+PermRank3R(SiteSwap2Perm1(rotateL(Perm2SiteSwap2(PermUnrank3Rfix(n,r)))))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
PermUnrank3Rfixaux := proc(n,r,p) local s; if(0 = n) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Rfixaux(n-1, r-(s*((n-1)!)), permul(p,[[n,n-s]]))); fi; end;
PermUnrank3Rfix := (n,r) -> convert(PermUnrank3Rfixaux(n,r,[]),'permlist',n);
SiteSwap2Perm1 := proc(s) local e,n,i,a; n := nops(s); a := []; for i from 1 to n do e := ((i+s[i]) mod n); if(0 = e) then e := n; fi; a := [op(a),e]; od; RETURN(convert(invperm(convert(a,'disjcyc')),'permlist',n)); end;

a[n_] := (1/n)*Sum[ EulerPhi[n/d]*(n/d)^d*d!, {d, Divisors[n]}]; Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Oct 09 2012, from formula *)
Table[Length[Select[Permutations[Range[n]],#==First[Sort[NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]]]&]],{n,8}] (* Gus Wiseman, Mar 04 2019 *)

a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017

from sympy import divisors, factorial, totient
def a(n):
    return sum(totient(n//d)*(n//d)**d*factorial(d) for d in divisors(n))//n
print([a(n) for n in range(1, 22)]) # Indranil Ghosh, Apr 10 2017

a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).

A053994 Nonattacking queens on a 2n+1 X 2n+1 toroidal board, solutions which differ only by rotation, reflection or torus shift count only once.

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 11, 0, 97, 354, 0, 31381, 395551, 0, 90120677

Offset: 0

Matthias Engelhardt, Apr 05 2000

A. P. Street and R. Day, Sequential binary arrays II: Further results on the square grid, pp. 392-418 of Combinatorial Mathematics IX. Proc. Ninth Australian Conference (Brisbane, August 1981). Ed. E. J. Billington, S. Oates-Williams and A. P. Street. Lecture Notes Math., 952. Springer-Verlag, 1982 (for getting equivalence classes).

I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639 (for finding the solutions).

A007705, A006841, A051906.

More terms from Matthias Engelhardt, Jan 11 2001

A054500 Indicator sequence for classification of nonattacking queens on n X n toroidal board.

Original entry on oeis.org

1, 5, 7, 11, 13, 13, 13, 13, 17, 17, 17, 17, 17, 19, 19, 19, 23, 23, 23, 25, 25, 25, 25, 25, 25, 25, 25, 29, 29, 29, 29, 29

Offset: 1

Matthias Engelhardt

The three sequences A054500/A054501/A054502 are used to classify solutions to the problem of "Nonattacking queens on a 2n+1 X 2n+1 toroidal board" by their symmetry; solutions are considered equivalent iff they differ only by rotation, reflection or torus shift.
For brevity, let i(n) = A054500(n) (indicator sequence), m(n) = A054501(n) (multiplicity) and c(n) = A054502(n) (count).
i(n) = k means that there are solutions for the k X k board and that m(n) and c(n) refer to it. There are c(n) inequivalent solutions which may be extended to m(n) different representations each (i.e., m(n) permutations).
This gives two formulas: A007705(n) = Sum (c(k) * m(k)), A053994(n) = Sum (c(k)), where the sum is taken over all k for which i(k) = 2n+1, for both formulas. Note that m(n) is always a divisor of 8 * i(n)^2.

			For a 19 X 19 toroidal board, you have three entries in the indicator sequence A054500; their count terms (A054502) give 354 = 4 + 132 + 218 inequivalent solutions; together with their multiplicity (A054501) they add up to 4*76 + 132*1444 + 218*2888 = 820496 solutions at all.

A. P. Street and R. Day, Sequential binary arrays II: Further results on the square grid, pp. 392-418 of Combinatorial Mathematics IX. Proc. Ninth Australian Conference (Brisbane, August 1981). Ed. E. J. Billington, S. Oates-Williams and A. P. Street. Lecture Notes Math., 952. Springer-Verlag, 1982 (for getting equivalence classes).

Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math.Monthly, 101 (1994), 629-639 (for finding the solutions).

Cf. A054501, A054502, A053994, A007705, A006841.

More terms from Matthias Engelhardt, Jan 11 2001

A003224 The number of superpositions of cycles of order n of the groups E_3 and D_n.

Original entry on oeis.org

1, 5, 24, 391, 9549, 401547, 22597671, 1646431048, 149640359575, 16597459048676, 2206178465445432, 346212403086248325, 63333787189956042080, 13359470726804093346852, 3218846593376516669825536, 878566295178157438213870011

Offset: 3

N. J. A. Sloane

Palmer and Robinson, Table 2, has incorrect a(8) = 401691. - Sean A. Irvine, Oct 25 2017

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 171.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.

Cf. A000940, A006841, A003225.

a(8) corrected and more terms from Sean A. Irvine, Oct 25 2017

A003225 The number of superpositions of cycles of order n of the groups S_3 and D_n.

Original entry on oeis.org

1, 3, 9, 89, 1705, 67750, 3771993, 274460137, 24940556932, 2766249007425, 367696475451179, 57702068070938071, 10555631209951650809, 2226578454651253107758, 536474432232188713033347, 146427715863075641229151764, 44945602048024898356307332914

Offset: 3

N. J. A. Sloane

Palmer and Robinson, Table 2, has incorrect a(8) = 67774. - Sean A. Irvine, Oct 25 2017

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 171.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.

Cf. A003224, A006841.

a(8) corrected and more terms from Sean A. Irvine, Oct 25 2017

A054501 Multiplicity sequence for classification of nonattacking queens on n X n toroidal board.

Original entry on oeis.org

1, 10, 28, 44, 26, 52, 338, 676, 34, 68, 578, 1156, 2312, 76, 1444, 2888, 92, 2116, 4232, 50, 100, 250, 500, 1000, 1250, 2500, 5000, 58, 116, 1682, 3364, 6728

Offset: 1

Matthias Engelhardt

See comments and references for A054500.

Cf. A054500, A054502, A053994, A007705, A006841.

More terms from Matthias Engelhardt, Jan 11 2001

A054502 Counting sequence for classification of nonattacking queens on n X n toroidal board.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 5, 1, 3, 23, 30, 40, 4, 132, 218, 5, 1859, 29517, 1, 2, 9, 18, 51, 470, 7170, 387830, 1, 6, 1215, 121487, 89997968

Offset: 1

Matthias Engelhardt

See comments and references for A054500.

Cf. A054500, A054501, A053994, A007705, A006841.

More terms from Matthias Engelhardt, Jan 11 2001

A062164 Number of ways of placing n nonattacking (normal) queens on n X n board; solutions congruent on the torus count only once.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 3, 6, 20, 40, 191, 953, 4604, 24660, 158466, 1009395

Offset: 1

Matthias Engelhardt

In this sequence two n-queens solutions p and q are considered equivalent iff there are natural numbers x and y such that, for all k from {0, ..., n-1}, q (k + x mod n) = p (k) + y mod n, or q is a rotation or a reflection of such a q.
In other words, besides rotations and reflections, also torus shifts are allowed. The sequence reduces the objects of A002562 and via that of A000170. The reduction of A000170 to this sequence is exactly the same as from A007705 to A053994 for torus queens; however, a solution for torus queens remains always a solution after a shift while a normal queens solutions does so only sometimes.
Note that the equivalence classes of this sequence are a subset of A006841. Moreover they are a subset of A062167.

M. Engelhardt, The N queens problem

Updated link that is transferred from people.freenet.de/nQueens to www.nqueens.de Matthias Engelhardt, Apr 21 2010

cp's OEIS Frontend

A003223 Erroneous version of A006841.

Views

Author

Keywords

References

Links

Crossrefs

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Python

Formula

A053994 Nonattacking queens on a 2n+1 X 2n+1 toroidal board, solutions which differ only by rotation, reflection or torus shift count only once.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A054500 Indicator sequence for classification of nonattacking queens on n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A003224 The number of superpositions of cycles of order n of the groups E_3 and D_n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A003225 The number of superpositions of cycles of order n of the groups S_3 and D_n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A054501 Multiplicity sequence for classification of nonattacking queens on n X n toroidal board.

Views

Author

Keywords

Crossrefs

Extensions

A054502 Counting sequence for classification of nonattacking queens on n X n toroidal board.

Views

Author

Keywords

Crossrefs

Extensions

A062164 Number of ways of placing n nonattacking (normal) queens on n X n board; solutions congruent on the torus count only once.

Views

Author

Keywords

Comments

Links

Extensions