login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054500 Indicator sequence for classification of nonattacking queens on n X n toroidal board. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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 kXk 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.

REFERENCES

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).

LINKS

Table of n, a(n) for n=1..32.

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

EXAMPLE

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.

CROSSREFS

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

Sequence in context: A095798 A136142 A136162 * A082684 A096379 A098761

Adjacent sequences:  A054497 A054498 A054499 * A054501 A054502 A054503

KEYWORD

nonn,nice,hard

AUTHOR

Matthias Engelhardt

EXTENSIONS

More terms from Matthias Engelhardt, Jan 11 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 12:33 EST 2019. Contains 329916 sequences. (Running on oeis4.)