Is there a way to calculate the number of equivalence classes given the number of non-zero elements in a binary matrix?

Question

Searching the answer to my question I've found the question 2183520 that I use to illustrate the point.

With the help of Burnside's lemma we can find the total number of orbits (in this context equivalence classes). There are 7 of the classes in the example of 2x2 binary matrices (out of total 16 instances). See below.

$$ \begin{bmatrix}0&0\\0&0\end{bmatrix}\tag1$$$$ \begin{bmatrix}1&0\\0&0\end{bmatrix}\sim \begin{bmatrix}0&1\\0&0\end{bmatrix}\sim \begin{bmatrix}0&0\\0&1\end{bmatrix} \sim\begin{bmatrix}0&0\\1&0\end{bmatrix}\tag2$$$$ \begin{bmatrix}1&1\\0&0\end{bmatrix}\sim \begin{bmatrix}0&0\\1&1\end{bmatrix}\tag3$$$$ \begin{bmatrix}1&0\\1&0\end{bmatrix}\sim \begin{bmatrix}0&1\\0&1\end{bmatrix}\tag4$$$$ \begin{bmatrix}1&0\\0&1\end{bmatrix}\sim \begin{bmatrix}0&1\\1&0\end{bmatrix}\tag5$$$$ \begin{bmatrix} 1 & 0 \\\ 1 & 1 \end{bmatrix} \sim \begin{bmatrix} 1 & 1 \\\ 1 & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 1 \\\ 0 & 1 \end{bmatrix} \sim \begin{bmatrix} 0 & 1 \\\ 1 & 1 \end{bmatrix}\tag6$$$$ \begin{bmatrix}1&1\\1&1\end{bmatrix}\tag7$$

My question is: how to calculate the number of equivalence classes given the number of non-zero elements in a binary matrix? In example, if I take only instances with two $1$s, I can find only three classes.

In other words I'm interested in distributions of orbits like in a table:

   instances: 1 4 6 4 1
number of 1s: 0 1 2 3 4
      orbits: 1 1 3 1 1

It seems like Burnside's algorithms use different approach to calculation and do not address the issue. Any tips will be welcome as well. (This is not a homework - I'm checking the properties of eccentricity, in Atkin's sense, in binary matrices).

Answer 1

Burnside’s lemma is indeed up to this task.

I closed that other question as a duplicate of the two that had been provided in a comment long ago. The answers to those two questions explain how to compute the cycle index for $S_n\times S_m$, so I won’t repeat that here; I’ll only show how to use it for your purposes.

So say you want to do this for $3\times3$ matrices. Applying the approach in said answers yields the cycle index

$$ \left(\frac16a_1^3+\frac12a_1a_2+\frac13a_3\right)\times\left(\frac16b_1^3+\frac12b_1b_2+\frac13b_3\right)\\\to\frac1{36}c_1^9+\frac16c_1^3c_2^3+\frac19c_3^3+\frac14c_1c_2^4+\frac13c_3c_6+\frac19c_3^3 $$

for $S_3\times S_3$. Now in that other case you could simply substitute the number $q$ of colours for each variable, since each cycle could be coloured in $q$ ways. Here it’s just slightly more complicated. We have $k$ ones, and each cycle must be either all ones or all zeros. So in this case the number of invariant matrices is the number of ways that the cycles can be combined into two sets such that one contains $k$ elements (and the other $9-k$). Here’s a table with those counts, and in the last column the result of substituting them into the cycle index:

\begin{array}{c|cccccc|c} k&c_1^9&c_1^3c_2^3&c_3^3&c_1c_2^4&c_3c_6&c_3^3&Z\\\hline 0&1&1&1&1&1&1&1\\ 1&9&3&0&1&0&0&1\\ 2&36&6&0&4&0&0&3\\ 3&84&10&3&4&1&3&6\\ 4&126&12&0&6&0&0&7 \end{array}

It’s not too hard to check that these are indeed the numbers of equivalence classes of $3\times3$ matrices with $k$ ones. (The numbers for $k\gt4$ follow by switching ones and zeros.)