A032522 -id:A032522 - cp's OEIS frontend

A002562 Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once).

1, 0, 0, 1, 2, 1, 6, 12, 46, 92, 341, 1787, 9233, 45752, 285053, 1846955, 11977939, 83263591, 621012754, 4878666808, 39333324973, 336376244042, 3029242658210, 28439272956934, 275986683743434, 2789712466510289, 29363495934315694

Offset: 1

N. J. A. Sloane

			a(4) = 1:
  +---------+
  | . . Q . |
  | Q . . . |
  | . . . Q |
  | . Q . . |
  +---------+
a(5) = 2:
  +-----------+ +-----------+
  | . . . Q . | | . . . Q . |
  | . Q . . . | | Q . . . . |
  | . . . . Q | | . . Q . . |
  | . . Q . . | | . . . . Q |
  | Q . . . . | | . Q . . . |
  +-----------+ +-----------+
a(6) = 1:
  +-------------+
  | . . . . Q . |
  | . . Q . . . |
  | Q . . . . . |
  | . . . . . Q |
  | . . . Q . . |
  | . Q . . . . | - _Hugo Pfoertner_, Mar 17 2019
  +-------------+
a(7) = 6:
  +---------------+  +---------------+  +---------------+
  | Q . . . . . . |  | Q . . . . . . |  | . Q . . . . . |
  | . . Q . . . . |  | . . . Q . . . |  | . . . Q . . . |
  | . . . . Q . . |  | . . . . . . Q |  | Q . . . . . . |
  | . . . . . . Q |  | . . Q . . . . |  | . . . . . . Q |
  | . Q . . . . . |  | . . . . . Q . |  | . . . . Q . . |
  | . . . Q . . . |  | . Q . . . . . |  | . . Q . . . . |
  | . . . . . Q . |  | . . . . Q . . |  | . . . . . Q . |
  +---------------+  +---------------+  +---------------+
.
  +---------------+  +---------------+  +---------------+
  | . Q . . . . . |  | . Q . . . . . |  | . Q . . . . . |
  | . . . . Q . . |  | . . . . Q . . |  | . . . . . Q . |
  | Q . . . . . . |  | . . . . . . Q |  | . . Q . . . . |
  | . . . Q . . . |  | . . . Q . . . |  | . . . . . . Q |
  | . . . . . . Q |  | Q . . . . . . |  | . . . Q . . . |
  | . . Q . . . . |  | . . Q . . . . |  | Q . . . . . . |
  | . . . . . Q . |  | . . . . . Q . |  | . . . . Q . . |
  +---------------+  +---------------+  +---------------+
- _Hugo Pfoertner_, Mar 18 2019

Martin Gardner, Fractal Music, Hypercards and More, Freeman, NY, 1991, p. 231-233.
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).
M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.

J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651-656. [Annotated scanned copy]
J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651-656.
P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
V. Chvatal, All solutions to the problem of eight queens
V. Chvatal, All solutions to the problem of eight queens [Cached copy, pdf format, with permission]
Popular Computing (Calabasas, CA), 8 Queens, Vol. 2, No. 13, Apr 1974, page PC13-1. Illustrates a(8)=12.
Popular Computing (Calabasas, CA), 8 Queens, Vol. 2, No. 13, Apr 1974, page PC13-2.
Popular Computing (Calabasas, CA), 8 Queens, Vol. 2, No. 13, Apr 1974, page PC13-3.
Popular Computing (Calabasas, CA), 8 Queens, Vol. 2, No. 13, Apr 1974, page PC13-4.
Thomas Preusser, Queens%40TUD-Project
E. M. Reingold, Letter to N. J. A. Sloane, Dec 27 1973
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 47. [Incomplete annotated scan of title page and pages 18-51]
Eric Weisstein's World of Mathematics, Queens Problem.
M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]
Wikipedia, Eight queens puzzle.

Cf. A000170, A032522, A033148.

a(n) = (1/8) * (Q(n) + P(n) + 2 * R(n)), where Q(n) = A000170(n) [all solutions], P(n) = A032522(n) [point symmetric solutions] and R(n) = A033148(n) [rotationally symmetric solutions].

a(17) and a(18) found by Ulrich Schimke in Goettingen, Germany (UlrSchimke(AT)aol.com)
Formula and a(19) to a(23) added by Matthias Engelhardt in Nuremberg, Germany, Jan 23 2000
Terms (calculated from formula) added by Thomas B. Preußer, Dec 15 2008
a(26) (derived from formula after recent extension of A000170) added by Thomas B. Preußer, Jul 12 2009
a(27) (derived from formula after recent extension of A000170) added by Thomas B. Preußer, Sep 23 2016

A037223 Number of solutions to non-attacking rooks problem on n X n board that are invariant under 180-degree rotation.

Original entry on oeis.org

1, 1, 2, 2, 8, 8, 48, 48, 384, 384, 3840, 3840, 46080, 46080, 645120, 645120, 10321920, 10321920, 185794560, 185794560, 3715891200, 3715891200, 81749606400, 81749606400, 1961990553600, 1961990553600, 51011754393600, 51011754393600, 1428329123020800, 1428329123020800

Offset: 0

Miklos SZABO (mike(AT)ludens.elte.hu)

This is just A000165 doubled up. Normally such sequences do not get their own entry in the OEIS. This is an exception. - N. J. A. Sloane, Sep 23 2006
Also the number of permutations of (1,2,3,...,n) for which the reverse of the inverse is the same as the inverse of the reverse. - Ian Duff, Mar 09 2007
Conjecture: a(n) = Product_{1<=i<=n and phi(i)<=floor(i/2)}i. - Enrique Pérez Herrero, May 31 2012. This conjecture is WRONG, counterexample is n=105. [Vaclav Kotesovec, Sep 07 2012]

E. Lucas, Theorie des nombres, Gauthiers-Villars, Paris, 1891, Vol 1, p. 221.

Alois P. Heinz, Table of n, a(n) for n = 0..500
E. Lucas, Théorie des nombres, Gauthiers-Villars, Paris, 1891, Vol 1, p. 221.
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
M. Szabo, Non-attacking Queens Problem Page

Cf. A000165, A033148, A037224, A032522, A037223.

[Factorial((n div 2) -1)*2^((n div 2)-1): n   in [2..35]]; // Vincenzo Librandi, Nov 17 2018

For Maple program see A000903.
# second Maple program:
a:= n-> (r-> r!*2^r)(iquo(n, 2)):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 23 2013

f[n_]:=Times@@Select[Range[n],EulerPhi[#]<=Floor[#/2]&]; Table[f[n],{n,1,30}] (* Conjectured: Enrique Pérez Herrero, May 31 2012 *)(* This conjecture and also program is WRONG for n=105, Vaclav Kotesovec, Sep 07 2012 *)
a[n_] := (2*Floor[n/2])!!; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Dec 23 2013, after N. J. A. Sloane's comment *)

a(2n) = a(2n+1) = n!*2^n.
E.g.f.: 1 + x + (1 + x + x^2)*exp(x^2/2)*sqrt(Pi/2)*erf(x/sqrt(2)), where erf denotes the error function. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 01 2002
For asymptotics see the Robinson paper.
E.g.f.: Q(0)  where Q(k)= 1 + x/(2*k + 1 - x*(2*k+1)/(x+1/Q(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 21 2012
E.g.f.: 1/(W(0)-x)  where W(k)= x + 1/(1 + x/(2*k + 1 - x*(2*k+1)/W(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 22 2012
a(n) = Product_{i=1..floor(n/2)} 2*i. - Wesley Ivan Hurt, Oct 19 2014
D-finite with recurrence: a(n) +a(n-1) -n*a(n-2) +(-n+2)*a(n-3)=0. - R. J. Mathar, Feb 20 2020

More terms from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 01 2002

Edited by N. J. A. Sloane, Sep 23 2006

A037224 Number of permutations p of {1,2,3...,n} that are fixed points under the operation of first reversing p, then taking the inverse.

Original entry on oeis.org

1, 0, 0, 2, 2, 0, 0, 12, 12, 0, 0, 120, 120, 0, 0, 1680, 1680, 0, 0, 30240, 30240, 0, 0, 665280, 665280, 0, 0, 17297280, 17297280, 0, 0, 518918400, 518918400, 0, 0, 17643225600, 17643225600, 0, 0, 670442572800, 670442572800, 0, 0, 28158588057600

Offset: 1

Miklos SZABO (mike(AT)ludens.elte.hu)

A122670 is an essentially identical sequence.
Also the number of rotationally symmetric solutions to non-attacking rooks problem on an n X n board.
Reversal of a permutation reflects the associated permutation matrix through an axis parallel to its sides, while inversion reflects the matrix through its main diagonal. The composition of these two operations is rotation by 90 degrees, and so permutations fixed by this composition correspond to rotationally symmetric rook diagrams by taking the associated permutation matrix. [Ian Duff, Mar 09 2007 and Joel B. Lewis, Jun 10 2009]
Equivalently, the number of permutations fixed by first inverting and then reversing. We may also replace "reversing" with "complementing" in the preceding sentences, where the complement of (w(1), ..., w(n)) is (n + 1 - w(1), ..., n + 1 - w(n)). [Joel B. Lewis, Jun 10 2009]

			Let p be the permutation {11,1,9,3,7,5,8,6,10,4,12,2} of {1,2,3,..,12}. Then the reverse Rp of p is {2,12,4,10,6,8,5,7,3,9,1,11} and the inverse IRp of Rp is {11,1,9,3,7,5,8,6,10,4,12,2}. Thus p counts as one of the a(12)=120 fixed-points for n=12.

C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
M. Szabo, Non-attacking Queens Problem Page

Cf. A001813, A033148, A032522, A037223, A122670.

a:= n-> `if`(irem(n, 4, 'm')>1, 0,
        `if`(m=0, 1, (2*m-1)! * 2/(m-1)!)):
seq(a(n), n=1..99);  # Alois P. Heinz, Jan 21 2011

{1}~Join~Table[If[MemberQ[{0, 1}, Mod[n, 4]], (2 # - 1)!*2/(# - 1)! &[Floor[n/4]], 0], {n, 2, 44}] (* Michael De Vlieger, Oct 05 2016 *)

a(n)=
{
    if ( n%4>=2, return(0) );
    n = n\4;
    if ( n==0, return(1) );
    return( (2*n-1)!*2/(n-1)! );
}
vector(55,n,a(n)) /* Joerg Arndt, Jan 21 2011 */

a(4n) = a(4n+1) = (2n-1)!*2/(n-1)!, a(4n+2) = a(4n+3) = 0.

Edited by N. J. A. Sloane, Jun 12 2009, incorporating comments from John W. Layman, Sep 17 2004

A033148 Number of rotationally symmetric solutions for queens on n X n board.

Original entry on oeis.org

1, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 8, 8, 0, 0, 64, 128, 0, 0, 480, 704, 0, 0, 3328, 3264, 0, 0, 32896, 43776, 0, 0, 406784, 667904, 0, 0, 5845504, 8650752, 0, 0, 77184000, 101492736, 0, 0, 1261588480, 1795233792, 0, 0, 21517426688, 35028172800, 0, 0, 406875119616, 652044443648, 0, 0, 8613581094912, 12530550128640, 0, 0, 194409626533888, 291826098503680, 0, 0

Offset: 1

Miklos SZABO (mike(AT)ludens.elte.hu)

From Don Knuth, Jul 17 2015: (Start)
Ahrens proved that a(n)=0 unless n=4k or 4k+1. He also proved that in the latter case, a(n) is a multiple of 2^k. He found all solutions when n was less than 20.
Kraitchik carried the calculations further (for n less than 28). In his book he tabulated only the values a(n)/2^k. He had correct entries for n=21 and n=25, but his values for n=20 and n=24 were 1 too small -- of course he had calculated everything by hand! (End)

W. Ahrens, Mathematische Unterhaltungen und Spiele, 2nd edition, volume 1, Teubner, 1910, pages 249-258.
Maurice Kraitchik, Le problème des reines, Bruxelles: L'Échiquier, 1926, page 18.

Tricia M. Brown, Kaleidoscopes, Chessboards, and Symmetry, Journal of Humanistic Mathematics, Volume 6 Issue 1 ( January 2016), pages 110-126.
P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]
Gheorghe Coserea, Solutions for n=20.
Gheorghe Coserea, Solutions for n=24.
Gheorghe Coserea, MiniZinc model for generating solutions.
YuhPyng Shieh, Cyclic Complete Mappings Counting Problems
M. Szabo, Non-attacking Queens Problem Page

Cf. A002562, A032522, A037223, A037224, A260189.

More terms from Jieh Hsiang and YuhPyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 20 2002

A260189 a(n) = A033148(n) / 2^floor(n/4).

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 4, 8, 0, 0, 15, 22, 0, 0, 52, 51, 0, 0, 257, 342, 0, 0, 1589, 2609, 0, 0, 11417, 16896, 0, 0, 75375, 99114, 0, 0, 616010, 876579, 0, 0, 5253278, 8551800, 0, 0, 49667373, 79595269, 0, 0, 525731268, 764804085, 0, 0, 5932910966, 8905825760, 0, 0

Offset: 1

Vaclav Kotesovec, following a suggestion of Don Knuth, Jul 18 2015

W. Ahrens, Mathematische Unterhaltungen und Spiele, 2nd edition, volume 1, Teubner, 1910, pages 249-258.
Maurice Kraitchik, Le probleme des reines, Bruxelles: L'Échiquier, 1926, 18.

P. Capstick and K. McCann, The problem of the n queens, apparently unpublished, no date (circa 1990?) [Scanned copy]

Cf. A002562, A032522, A033148, A037223, A037224.

cp's OEIS Frontend

A000017 Erroneous version of A032522.

Views

Author

Keywords

A002562 Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A037223 Number of solutions to non-attacking rooks problem on n X n board that are invariant under 180-degree rotation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A037224 Number of permutations p of {1,2,3...,n} that are fixed points under the operation of first reversing p, then taking the inverse.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A033148 Number of rotationally symmetric solutions for queens on n X n board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A260189 a(n) = A033148(n) / 2^floor(n/4).

Views

Author

Keywords

References

Links

Crossrefs