A003111 -id:A003111 - cp's OEIS frontend

A006717 Number of ways of arranging 2n+1 nonattacking semi-queens on a (2n+1) X (2n+1) toroidal board.

1, 3, 15, 133, 2025, 37851, 1030367, 36362925, 1606008513, 87656896891, 5778121715415, 452794797220965, 41609568918940625

Offset: 0

N. J. A. Sloane

Also the number of "good" permutations on 2n+1 elements [Novakovich]. - N. J. A. Sloane, Feb 22 2011
Also the number of transversals of a cyclic Latin square of order 2n+1 and the number of orthomorphisms of the cyclic group of order 2n+1. - Ian Wanless, Oct 07 2001
Also the number of complete mappings of a cyclic group of order 2n+1; also (2n+1) times the number of "standard" complete mappings of cyclic group of order 2n+1. - Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
See A003111 for further information.
A very simple model using only addition mod n: Let i=index vector (0,1,..n-1) on any set of n distinct values, and j=index vector for the values after reordering. Then j = (i + d) mod n, where d is the vector of distances moved, and a(n) = number of reorderings that give an equidistributed set d (i.e., 1 instance of each distance moved). Since a(n)=0 for all even n, taking only odd n gives the sequence above - Ross Drewe, Sep 03 2017
All broken diagonals and antidiagonals of cyclic Latin square are transversals, so a(n) >= 2*n for all n > 1 for which cyclic Latin squares exist. - Eduard I. Vatutin, Mar 23 2022

Yuh Pyng Shieh, Jieh Hsiang and D. Frank Hsu, On the enumeration of Abelian k-complete mappings, vol. 144 of Congressus Numerantium, 2000, pp. 67-88.
Yuh Pyng Shieh, Partition Strategies for #P-complete problem with applications to enumerative combinatorics, PhD thesis, National Taiwan University, 2001.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 118.

Christian Carley, The Name Tag Problem, Mathematics Undergraduate Theses (Boise State University, 2019).
N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.
S. Eberhard, F. Manners, and R. Mrazovic, Additive Triples of Bijections, or the Toroidal Semiqueens Problem , arxiv:1510.05987, [math.CO], 2016.
Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, Cyclic Complete Mappings Counting Problems, National Taiwan University 2014/8/21.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013.
N. Yu. Kuznetsov, Using the Monte Carlo Method for Fast Simulation of the Number of "Good" Permutations on the SCIT-4 Multiprocessor Computer Complex, Cybernetics and Systems Analysis, January 2016, Volume 52, Issue 1, pp 52-57.
B. D. McKay, J. C. McLeod and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, (2006) 269-284.
D. Novakovic, Computation of the number of complete mappings for permutations, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
D. S. Stones and I. M. Wanless, Compound orthomorphisms of the cyclic group, Finite Fields Appl. 16 (2010), 277-289.
Eric Weisstein's World of Mathematics, Queens Problem.

Cf. A003111, A007705.

k = 6; A = zeros(1,k); for i = 1:k; n = 2*i-1; x = [0: n-1]; allP = perms(x); T = size(allP,1); X = repmat(x, T, 1); Y = mod(X + allP, n); Y = sort(Y, 2); L = ~(sum(Y ~= X, 2)); A(i) = sum(L); end; A
% 1st 6 terms by testing all n! possible distance vectors
% Ross Drewe, Sep 03 2017

Suppose n is odd and let b(n)=a((n-1)/2). Then b(n) is odd; if n>3 and n is not 1 mod 3 then b(n) is divisible by 3n; b(n)=-2n mod n^2 in n is prime; b(n) is divisible by n^2 if n is composite; b(n) is asymptotically in between 3.2^n and 0.62^n n!. [Cavenagh, Wanless], [McKay, McLeod, Wanless], [Stones, Wanless] - Ian Wanless, Jul 30 2010
b(n) is asymptotic to e^(-1/2) n!^2/n^(n-1) [Eberhard, Manners, Mrazovic]. - Sam Spiro, Apr 16 2019; corrected by Sean Eberhard, Jul 21 2023
a(n) = (2*n+1) * A003111(n). - Andrew Howroyd, Sep 28 2020

More terms from Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
a(12) added from A003111 by N. J. A. Sloane, Mar 29 2007
Definition clarified by Vaclav Kotesovec, Sep 16 2014

A003110 a(n) = number of special odd permutations of 2*n+1.

Original entry on oeis.org

0, 2, 2, 108, 2028, 32870, 1213110, 46493784, 2310521000, 137466038346, 9842687925450, 832295357128500

Offset: 1

N. J. A. Sloane

a(n) is the number of odd permutations, pi(0),...,pi(2*n), of 0,...,2*n such that pi(0) = 0 and p(k) = k + pi(k) (mod 2*n+1), k=0,...,2*n is also a permutation of 0,...,2*n. - Sean A. Irvine, Jan 31 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. H. Lehmer, Some properties of circulants, J. Number Theory 5 (1973), 43-54.

Cf. A003109 (special even permutations), A003110 (total).

Name clarified and offset corrected by Sean A. Irvine, Jan 31 2015
a(8)-a(9) from Sean A. Irvine, Jan 31 2015
a(10)-a(12) from Vaclav Kotesovec, May 17 2019 (using the terms of A003111 and A003112)

A003109 a(n) = number of special even permutations of 2*n+1.

Original entry on oeis.org

1, 1, 17, 117, 1413, 46389, 1211085, 47977305, 2302999889, 137682614769, 9844042388505, 832087399629125

Offset: 1

N. J. A. Sloane

a(n) is the number of even permutations, pi(0),...,pi(2*n), of 0,...,2*n such that pi(0) = 0 and p(k) = k + pi(k) (mod 2*n+1), k=0,...,2*n is also a permutation of 0,...,2*n. - Sean A. Irvine, Jan 30 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. H. Lehmer, Some properties of circulants, J. Number Theory 5 (1973), 43-54.

Cf. A003110 (special odd permutations), A003111 (total).

a(8)-a(9) from Sean A. Irvine, Jan 31 2015

a(10)-a(12) from Vaclav Kotesovec, May 17 2019 (using the terms of A003111 and A003112)

A071608 Number of complete mappings f(x) of Z_{2n+1} such that -(-id+f)^(-1)=f.

Original entry on oeis.org

1, 1, 0, 4, 0, 0, 80, 48, 0, 3328, 1920, 0, 270080, 131328, 0, 3257736, 16379904, 0, 5750476800, 2942582784, 0, 1376249266176, 706948005888, 0, 430415593603072

Offset: 0

J. Hsiang, D. F. Hsu and Y. P. Shieh (arping(AT)turing.csie.ntu.edu.tw), Jun 03 2002

nonn

A complete mapping of a cyclic group (Zn,+) is a permutation f(x) of Zn such that f(0)=0 and that f(x)-x is also a permutation.

			f(x)=3x in (Z_7,+) is a complete mapping of Z_7 since f(0)=0 and f(x)-x (=2x) is also a permutation of Z_7. And -(-id+f)^(-1)(x)=f(x).

Y. P. Shieh, "Partition strategies for #P-complete problems with applications to enumerative combinatorics", PhD thesis, National Taiwan University, 2001.
Y. P. Shieh, J. Hsiang and D. F. Hsu, "On the enumeration of Abelian k-complete mappings", vol. 144 of Congressus Numerantium, 2000, pp. 67-88.

Y. P. Shieh, Cyclic complete mappings counting problems

Cf. A003111.

A343868 Number of semicyclic Latin squares of order n with the first row in ascending order.

Original entry on oeis.org

0, 0, 0, 8, 40, 338, 1512, 11368, 84960, 828972, 7291900, 85823668, 958954152, 12930529446, 176651211776, 2631044069296, 41847091313152

Offset: 1

Andrew Howroyd, May 08 2021

A semicyclic Latin square is cyclic in one or more directions but not in every direction. Cyclic Latin squares which are cyclic in essentially every direction are excluded. A direction here means any constant row and column displacement on the torus. See the reference in A343867 for additional information.

Each symbol occupies the same pattern of squares up to translation on the torus.

			The permutation 164253 can be shown in a 6 X 6 grid:
    X . . . . .
    . . . . . X
    . . . X . .
    . X . . . .
    . . . . X .
    . . X . . .
This permutation gives the following 4 semicyclic squares.
    1 2 3 4 5 6   1 4 2 5 3 6   1 4 3 6 2 5   1 4 5 2 3 6
    2 3 4 5 6 1   2 5 3 6 4 1   3 6 2 5 4 1   2 5 6 3 4 1
    4 5 6 1 2 3   3 6 4 1 5 2   5 2 4 1 3 6   6 3 4 1 2 5
    6 1 2 3 4 5   4 1 5 2 6 3   4 1 6 3 5 2   4 1 2 5 6 3
    3 4 5 6 1 2   5 2 6 3 1 4   6 3 5 2 1 4   5 2 3 6 1 4
    5 6 1 2 3 4   6 3 1 4 2 5   2 5 1 4 6 3   3 6 1 4 5 2
In the third example, moving one cell down and two across increases the cell value by 1 (cyclically) and in the fourth example the displacement is 3 rows down and 2 across. Symbols can then be rearranged to give 4 distinct semicyclic squares with the first row in ascending order.

Andrew Howroyd, Order 6 semicyclic Latin squares
Andrew Howroyd, PARI Program

Cf. A000010 (phi), A001615, A003111, A343867.

PARI
```
\\ See Links
```

a(n) >= 2*((n-1)! - phi(n)).

a(p) = 2*(p-1)! + (p-1)*(A003111((p-1)/2) - p) for odd prime p.

A006204 Number of starters in cyclic group of order 2n+1.

Original entry on oeis.org

1, 1, 3, 9, 25, 133, 631, 3857, 25905, 188181, 1515283, 13376125, 128102625, 1317606101, 14534145947, 170922533545, 2138089212789

Offset: 1

N. J. A. Sloane

A complete mapping of a cyclic group (Z_m,+) is a permutation f(x) of Z_m with f(0)=0 such that f(x)-x is also a permutation. a(n) is the number of complete mappings f(x) of the cyclic group Z_{2n+1} such that f^(-1)=f.

In other words, a(n) is the number of complete mappings fixed under the reflection operator R, where R(f)=f^(-1). Reflection R is not only a symmetry operator of complete mappings, but also one of the (Toroidal)-(semi) N-Queen problems and of the strong complete mappings problem.

			f(x)=6x in (Z_7,+) is a complete mapping of Z_7 since f(0)=0 and f(x)-x (=5x) is also a permutation of Z_7. f^(-1)(x)=6x=f(x). So f(x) is fixed under reflection.

CRC Handbook of Combinatorial Designs, 1996, p. 469.
CRC Handbook of Combinatorial Designs, 2nd edition, 2007, p. 624.
J. D. Horton, Orthogonal starters in finite Abelian groups, Discrete Math., 79 (1989/1990), 265-278.
V. Linja-aho and Patric R. J. Östergård, Classification of starters, J. Combin. Math. Combin. Comput. 75 (2010), 153-159.
Y. P. Shieh, "Partition strategies for #P-complete problems with applications to enumerative combinatorics", PhD thesis, National Taiwan University, 2001.
Y. P. Shieh, J. Hsiang and D. F. Hsu, "On the enumeration of Abelian k-complete mappings", vol. 144 of Congressus Numerantium, 2000, pp. 67-88.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Bill Butler, Durango Bill's Bridge Probabilities and Combinatorics
Jieh Hsiang, Yuhpyng Shieh, Yaochiang Chen, Cyclic complete mappings counting problems, National Taiwan University, Taipei, April 2003.
Vesa Linja-aho, Patric R. J. Östergård, Classification of starters, J. Combin. Math. Combin. Comput. 75 (2010), 153-159.

Cf. A006717, A071607, A071608, A071706, A003111.

Additional comments and one more term from J. Hsiang, D. F. Hsu and Y. P. Shieh (arping(AT)turing.csie.ntu.edu.tw), Jun 03 2002
Corrected and extended by Roland Bacher, Dec 18 2007
Extended by Vesa Linja-aho (vesa.linja-aho(AT)tkk.fi), May 06 2009

A006609 Number of cyclic neofields of order n.

Original entry on oeis.org

1, 2, 3, 8, 19, 64, 225, 928, 3441, 17536, 79259, 454016, 2424195, 15628288, 94471089, 679156224, 4613520889, 36563599360, 275148653115

Offset: 4

N. J. A. Sloane, Simon Plouffe

Also the number of (n-1,1)-partial orthomorphisms. - Pei Jisheng, Dec 06 2012; corrected by Max Alekseyev, May 17 2025

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. F. Hsu, Cyclic Neofields and Combinatorial Designs, Lect. Notes Math. 824 (1980). See p. 189.
D. S. Stones, I. M. Wanless, A congruence connecting Latin rectangles and partial orthomorphisms, Ann. Comb. 16, No. 2, 349-365 (2012).

a(2n) = A003111(n-1). - Max Alekseyev, May 17 2025

a(22) from A003111 added by Max Alekseyev, May 17 2025

A190141 The number of conjugacy classes of the symmetric group S_{0..n-1}, containing at least one complete bijection.

Original entry on oeis.org

2, 4, 5, 8, 10, 18, 22, 34, 41, 63, 77, 111, 135, 190, 231

Offset: 3

Bert Schaaf, May 05 2011

X = {0..n-1}, and n >= 3. Suppose c is a cycle on X, with length L>1, and support C. Define a map e(c) : X --> X, by ec(x) = x for x not in C, and supposing x = ck, 0 <= k < L, we define ec(x) = cs, with s == ( k + ck) Mod L. If e(c) is a bijection on X, we call e(c) a complete bijection.

			n = 6, a(6) = 5. We have:
e((1->3->5->2->4)) = (1->3->4->5), ec((0->3->1->4->2)) = (1->4)(2->3),
ec((1->2->4->5)) = (1->2->5), ec((1->3)) = (1->3) and ec((0->2))= identity.
The remaining conjugacy classes don't contain a complete bijection.

Cf. A003111

cp's OEIS Frontend

A006717 Number of ways of arranging 2n+1 nonattacking semi-queens on a (2n+1) X (2n+1) toroidal board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A003110 a(n) = number of special odd permutations of 2*n+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A003109 a(n) = number of special even permutations of 2*n+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A071608 Number of complete mappings f(x) of Z_{2n+1} such that -(-id+f)^(-1)=f.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A343868 Number of semicyclic Latin squares of order n with the first row in ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A006204 Number of starters in cyclic group of order 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A006609 Number of cyclic neofields of order n.

Views

Author

Keywords

Comments

References

Links

Formula

Extensions

A190141 The number of conjugacy classes of the symmetric group S_{0..n-1}, containing at least one complete bijection.

Views

Author

Keywords

Comments

Examples

Crossrefs