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.

How many rectangular $m \times n$ $(0,1)$ matrix (where $n>m$) are there with prescribed row sums $r_i$ for $i=1$ to $m$ such that no two columns are the same.

share|improve this question
    
I'd be surprised if there were a simple formula for this. –  Gerry Myerson Aug 19 '12 at 23:42
    
A related (hard) problem is counting binary contingency tables, i.e. how many {0,1}-matrices of specified size have prescribed row and column sums. Here only row sums are specified, but columns are distinct. Thus there is a factor of $n!$ in the count because of conserving those properties under arbitrary column permutations. –  hardmath Aug 20 '12 at 18:08
    
There are also some symmetries related to the rows worth mentioning. For example, any row $i$ may be flipped to opposite parity, producing a row sum $n - r_i$ instead of $r_i$, yet preserving the distinctness of columns. Also the number of columns $n$ may be restricted $n \gt m$ in Arun's context, but this is not essential. Rather the natural restriction is $1 \le n \le 2^m$. If the columns represent subsets of $\{1,..,m\}$, an equivalence of problems for $n$ and $2^m - n$ such subsets/columns obtains by complementing those in the power set of $\{1,..,m\}$, $r_i \rightarrow 2^{m-1} - r_i$. –  hardmath Aug 23 '12 at 13:04

1 Answer 1

up vote 1 down vote accepted

The count of $m\times n$ binary matrices with specified row sums $r_i, i=1,\ldots,m$ and distinct columns can be expressed as a product:

$$ n! [1, 0, \ldots ,0] ( \Pi_{i=1}^m T_i ) [0, \ldots ,0, 1]^T $$

where each $T_i$ is a sparse upper triangular matrix depending only on $n$ and $r_i$.

The factor $n!$ accounts for permutations of the $n$ distinct columns. We suppress further consideration of that factor by requiring the columns to be ordered descendingly, taking the bit of an upper row to be more significant than one in a lower row.

The matrix $T_i$ is the adjacency matrix of a directed multigraph on states that are partitions of the number of columns $n$, ordered by refinement, and whose edges correspond to refining one partition to another by assigning $r_i$ ones to the next row of the matrix (potentially distinguishing some columns that were identical up to that row). Note that initially (before any rows are assigned) all columns are identical, which corresponds to the trivial partition $[n]$. After all rows are assigned we will have all columns distinct, which corresponds to the slightly less trivial partition $[1,1,\ldots ,1]$.

Note that this graph allows self-loops, but otherwise it has no cycles. Taking the product of matrices counts paths from one state to another, and we are interested in the count of paths from $[n]$ to $[1,1,\ldots ,1]$ as this corresponds (apart from column permutations) to the number of admissible binary matrices (specified row sums and distinct columns).

Still omitting the $n!$ factor, I calculated by hand (and checked with bits of Prolog code) small examples of the form $2k \times 2k$ binary matrices with all rows sums equal $k$. For $k=1$ we get 2 solutions. For $k=2$ there are 52 solutions. For $k=3$ there are 83,680 solutions.

As a practical matter we do not need to consider all possible partitions of $n$, only those that are attainable. Taking into account that the first row uniquely transitions from $[n]$ to $[r_1,n-r_1]$ reduces the matrix product by one index and limits the possible partitions. For case $k=4$ in the examples described above, only eight partitions are needed, and the transition matrix can take the form:

$$ T = \begin{pmatrix} 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 4 & 0 & 6 & 0 & 0 \\ 0 & 0 & 6 & 0 & 0 & 12 & 0 & 1 \\ 0 & 0 & 0 & 6 & 2 & 8 & 6 & 0 \\ 0 & 0 & 0 & 0 & 10 & 0 & 20 & 0 \\ 0 & 0 & 0 & 0 & 0 & 14 & 16 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 30 & 20 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 70 \end{pmatrix} $$

Thus for $k=4$ we'd get (apart from the factor $8!$) a count of $(T^7)_{1,8}$ or 13,849,902,752 solutions.

The usefulness of this approach will be limited by how many partitions/states are needed by given parameters $m, n, r_i$. I'd be happy to post my Prolog snippets and/or attempt a larger problem if anyone is interested.

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.