|
%I #17 Sep 04 2023 11:35:09
%S 1,5,7,11,13,13,13,13,17,17,17,17,17,19,19,19,23,23,23,25,25,25,25,25,
%T 25,25,25,29,29,29,29,29
%N Indicator sequence for classification of nonattacking queens on n X n toroidal board.
%C 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.
%C For brevity, let i(n) = A054500(n) (indicator sequence), m(n) = A054501(n) (multiplicity) and c(n) = A054502(n) (count).
%C 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).
%C 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.
%D 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).
%H Manuel Kauers and Christoph Koutschan, <a href="https://arxiv.org/abs/2202.07966">Guessing with Little Data</a>, arXiv:2202.07966 [cs.SC], 2022.
%H I. Rivin, I. Vardi and P. Zimmermann, <a href="https://www.jstor.org/stable/2974691">The n-queens problem</a>, Amer. Math.Monthly, 101 (1994), 629-639 (for finding the solutions).
%e 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.
%Y Cf. A054501, A054502, A053994, A007705, A006841.
%K nonn,nice,hard
%O 1,2
%A _Matthias Engelhardt_
%E More terms from _Matthias Engelhardt_, Jan 11 2001
|
