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

1 Answer 1

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.

It might be possible to use Burnside's lemma (aka Cauchy-Frobenius lemma) to count the number of isomorphism classes under row permutations. I will have to think about this, or maybe someone else can do it. To count the number of classes under row and column permutations seems more difficult.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.