How many different dispositions (up to rotation and reflection of the board) are there of K queens on an N...

competition/games/chess/queen.dispositions New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many different dispositions (up to rotation and reflection of the
board) are there of K queens on an N x N chessboard?

[ Editor: the queens need not be non-attacking; this counts all sets
of K squares, positions that differ by a symmetry of the board counted
once.  From "Different Dispositions in the ChessBoard" by Timothy Chow
and Mario Velucchi (16 Nov. 1995), forwarded to the archive. ]

Show solution

The answer is in the "Polya's Theorem".  The wanted number is 1/8th of
the coefficient of

a^K * b^(N^2-K) in these polynomials:

if N is even
p(a,b,N) := (a+b)^(N^2) + 2*(a+b)^N*(a^2+b^2)^((N^2-N)/2)
            + 3*(a^2+b^2)^(N^2/2) + 2*(a^4+b^4)^(N^2/4)

if N is odd
p(a,b,N) := (a+b)^(N^2) + 2*(a+b)*(a^4+b^4)^((N^2-1)/4)
            + (a+b)*(a^2+b^2)^((N^2-1)/2)
            + 4*(a+b)^N*(a^2+b^2)^((N^2-N)/2)

Note: the total number of dispositions is equal to: Binomial
coefficient(N^2, K) and the number of different dispositions is near
1/8th.

Samples (K = N):
for N = 1           different dispositions = 1
for N = 2           different dispositions = 2
for N = 3           different dispositions = 16
for N = 4           different dispositions = 252
for N = 5           different dispositions = 6814
for N = 6           different dispositions = 244344
for N = 7           different dispositions = 10746377
for N = 8           different dispositions = 553319048
for N = 9           different dispositions = 32611596056
for N = 10          different dispositions = 2163792255680
...
for N = 14          different dispositions = 110066314584030859544
for N = 15          different dispositions = 11375695977099383509351
...

-- Timothy Chow and Mario Velucchi <velucchi@cli.di.unipi.it>