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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Angela Richardson Oct 20 '12 at 7:18
  • 1
    $\begingroup$ Or the number of non-isomorphic bipartite graphs with $k$ edges partitioned into distinguishable subsets of $r$ and $c$ vertices of even degree. $\endgroup$ – joriki Oct 20 '12 at 7:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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