I'm interested in counting the number of n×n 0-1 matrices with a given number of 1s up to rotation and reflection. What is the best way to do this if n is not too small?
For example, consider 4×4 matrices with 7 1s. There are ${16\choose7}=11440$ such matrices in total, but most equivalence classes under reflection and rotation have 8 members, so the total is closer to 11440/8 = 1430. In fact if I am correct the total is 1465.
One method would be enumerating all such matrices, counting the number of distinct matrices resulting from each of the eight symmetries. But this takes too long, even for a computer, for n > 6 or so.
Burnside's lemma seems promising, but this requires counting fixed points and I do not know how to do this rapidly. In any case I have very little familiarity with group theory and so pointers, even basic ones, would be appreciated.
Perhaps there are other methods which can be used as well. I have seen this described as an easy problem, so I must be missing something (unless it was mischaracterized!).
Burnside's lemma is indeed helpful here. What you have is the group $D_4$ (the group of symmetries on the square) acting on the set of $n\times n$ 0-1 matrices with $k$ ones, and you want to count the number of orbits. By Burnside's lemma this is $$\frac18\sum\limits_{g\in D_4}|X^g|$$ where $X^g$ is the set of matrices fixed by the element $g\in D_4$. Since $D_4$ has only $8$ elements, this calculation is fairly easy. I shall illustrate the case $n=4, k=6$.
We can view the $4\times 4$ matrix as a block matrix $$\begin{pmatrix} A & B \\ C & D\end{pmatrix}$$ where each block is a $2\times 2$ matrix. Clearly the identity fixes all $\binom{16}{6}=8008$ matrices. Rotation by $90^\circ$ counterclockwise permutes this to give $$\begin{pmatrix} B & D \\ A & C\end{pmatrix}$$ so the matrix is fixed iff $A=B=D=C$. But this means the number of ones in the matrix is a multiple of $4$, yet $k$ is not divisible by $4$, thus no matrices are fixed by rotation by $90^\circ$. It is easy to see that the result is the same for rotation by $270^\circ$. Rotation by $180^\circ$ permutes the original matrix to $$\begin{pmatrix} D & C \\ B & A\end{pmatrix}$$ which is the same as the original iff $A=D$ and $B=C$. Thus since $k=6$ we can either have $3$ ones in $A$, $2$ in $A$ and $1$ in $B$, $1$ in $A$ and $2$ in $B$, or $3$ in $B$. Since choosing $A$ and $B$ completely determines the matrix, the number of matrices fixed by rotation by $180^\circ$ is $$\binom43\binom40+\binom42\binom41+\binom41\binom42+\binom40\binom43=56.$$ Now for reflection. Vertical or horizontal reflection is easy; a matrix is fixed iff its left (upper) half is the same as its right (lower) half, so each half must have $3$ ones and the number of matrices fixed by each is $\binom83=56$. Note that reflection across the main diagonal is a standard operation in linear algebra called transposition, which is denoted by a superscript $t$. A matrix equal to its own transpose is called symmetric, and a symmetric matrix is determined entirely by its main diagonal and bottom left entries, of which there are $4$ and $6$ respectively. If we let $d$ be the number of ones on the diagonal and $b$ the number of ones in the bottom left, we have $k=d+2b$, thus we can have $d=0$ and $b=3$, $d=2$ and $b=2$ or $d=4$ and $b=1$. The number of such matrices is $\binom4d\binom6b$ for each value of $b$ and $d$, thus the number of matrices fixed by transposition is $$\binom40\binom63+\binom42\binom62+\binom44\binom61=116.$$ It is easy to see that the result for reflection across the other diagonal is the same. Thus we have $$|X/D_4|=\frac18\sum\limits_{g\in D_4}|X^g|=\frac{1}{8}(8008+0+56+0+56+56+116+116)=1051.$$ This result agrees with oeis.org/A054252. It also shows some interesting dependence of $|X/D_4|$ on the divisibility of $k$ by $2$ and $4$.