3
$\begingroup$

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.

  • 1
    Or the number of non-isomorphic bipartite graphs with $k$ edges partitioned into distinguishable subsets of $r$ and $c$ vertices of even degree.2012-10-20

1 Answers 1

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.