A019318 ? (Sorry - figured it out.)

Brendan McKay bdm at cs.anu.edu.au
Wed May 28 06:33:30 CEST 2003

* David Wilson <davidwwilson at attbi.com> [030528 06:53]:
> Brendan McKay wrote:
> > I agree with you about "queens", that really must go.  I suggest
> > "Inequivalent ways of choosing n squares of an n x n chessboard,
> > considering rotations and reflections."
> Or maybe chess has to go:
> "Ways of choosing n squares on an n x n grid up to rotation and reflection"

No, because many people regard an n x n grid as defining (n-1)^2 squares.
Usually people working with "grids" place things where the lines cross
and not in the spaces between the lines.

A problem with "chessboard" is that the squares are black and white
and it isn't clear whether that counts in defining equivalence.

Referring to a matrix is not ok either, because rotation and reflection
are not usual matrix operations.

So I propose:

   Inequivalent ways of choosing n locations on an n x n grid,
   where equivalence is defined by rotations and reflections of
   the grid.

Someone asked whether Burnside's Lemma could handle the 3-dimensional
version.  The answer is yes.  Burnside's Lemma (incidentally due to
some people other than Burnside, notably Frobenius) can handle all
similar problems.  The only question is whether the calculations are
easy or hard to carry out.

Here is Burnside's Lemma in English.  You have a group of equivalence
operations including the identity [in the example, 8 refections and
rotations of the n x n grid].  These operations act on some set of
configurations [placements of n objects on the grid].  The lemma says
that the number of equivalence classes of configurations equals the
average number of configurations preserved by the operations.  In the
example you would list the 8 reflections and rotations and for each of
them figure out how many placements of n objects are preserved by each
of them.  (For the identity operation, all placements are preserved.)
Add these 8 numbers and divide by 8.


More information about the SeqFan mailing list