# The number of $(0,1)$ matrices with even row- and column sums.

Inspired by this question and some related ones here, I'd like to find the number of ways, $S(k, r, c)$, to place $k$ ones and $rc-k$ zeros in an $r\times c$ array so that the row sums and column sums are all even. Obviously, we'll require that $k\le rc$ and $k$ is even.

It seems reasonable to require that a solution that can be made from another by permuting the rows and the columns shouldn't be counted as distinct. For example, with $k=12, r=4, c=6$ we would have at least these inequivalent solutions: $$\left[\begin{array}{cccccc} 0 & 1 & 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{array}\right] \qquad\text{and}\qquad \left[\begin{array}{cccccc} 1 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right]$$ if for no other reason than no row or column permutation can change the one on the left to have a row consisting of all zeros.

-
The problem is equivalent to counting the number of non-isomorphic simple graphs with $\frac{k}{2}$ edges and $c$ vertices, coloured with up to $r$ colours so that no two edges with the same colour meet at any vertex and every vertex has even degree and no two such graphs can be made the same by swapping endpoints of edges of the same colour. – Angela Richardson Oct 20 '12 at 7:18
Or the number of non-isomorphic bipartite graphs with $k$ edges partitioned into distinguishable subsets of $r$ and $c$ vertices of even degree. – joriki Oct 20 '12 at 7:27

Suppose we want to consider matrices that differ by row and column permutations as distinct. Let $T(k,r,c)$ be the number of such matrices. Fix $r$ and $c$, and let $F(t)=\sum_k T(k,r,c)t^k$. Let $$A=\prod_{i=1}^r\prod_{j=1}^c (1+x_iy_jt).$$ Then $F(t)$ is equal to $1/2^{r+c}$ times the sum of all $2^{r+c}$ ways to set the $x_i$'s and $y_j$'s equal to $-1$ or $1$ in $A$. This will express $F(t)$ as an explicit linear combination of terms $(1-y)^a (1+t)^{rc-a}$. One can then extract the coefficient of $t^k$ as a double sum.