# How many $n\times m$ binary matrices are there, up to row and column permutations?

I'm interested in the number of binary matrices of a given size that are distinct with regard to row and column permutations.

If $\sim$ is the equivalence relation on $n\times m$ binary matrices such that $A \sim B$ iff one can obtain B from applying a permutation matrix to A, I'm interested in the number of $\sim$-equivalence classes over all $n\times m$ binary matrices.

I know there are $2^{nm}$ binary matrices of size $n\times m$, and $n!m!$ possible permutations, but somehow I fail to get an intuition on what this implies for the equivalence classes.

-
Intuitively, the average matrix has trivial stabilizer, so there ought to be roughly 2^{nm}/n!m! equivalence classes. This is probably a very hard question in general. –  Qiaochu Yuan Feb 15 '11 at 12:02
There is the set $S:=[m]\times[n]$ on which the group $G:=S_m\times S_n$ acts, and we have to color $S$ with colors $0$ and $1$. How many colorings are there when two colorings that differ by a $g\in G$ are considered the same? Now there is a famous theory that addresses exactly this kind of questions; it is called Polya counting theory. I could imagine that your problem is a standard example in the field. –  Christian Blatter Feb 15 '11 at 13:24
If you view A as the incidence matrix of an unweighted undirected bipartite graph. Then I think the question you're asking is how many unique bipartite graphs up to isomorphism are there with the two vertex groups having n,m vertices respectively. –  JSchlather Feb 15 '11 at 17:53
This is solved here using Pólya enumeration theory. For the square case ($n=m$), see this sequence.
Comment: I found these by searching for $1,2,7$ in the OEIS.