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
    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.2012-10-20
  • 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