Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.