Re: enumerating binary matrices

On Mar 18, 9:40 pm, canadan <dan_l...@xxxxxxxxxxx> wrote:
Hello,

I need to count the number of m X n matrices with entries in {0,1}
such that:

1) the rows are distinct
2) the columns are non-constant (i.e. no column has all 1's or all
0's)

I think that I can count the number of matrices satisfying either
condition on it's own, but not both.

Can you help me? Any ideas or pointers to references are appreciated.

Thanks.

dan

Let us write B(n, m) for the binomial coefficient `n choose m'.

Let us fix m >= 1 and put

M(n,m) = number of binary matrices of m rows and n columns
such that (i) the rows are distinct and (ii) there
are no constant columns.

Let us call such matrices `good'.

Let I = {1, ..., n}, let P be the set of all subsets of I.
Define two functions f, g : P --> Z putting

f(X) = number of binary matrices of m rows and n columns
such that (i) the rows are distinct and (ii) the
columns indexed by the elements of X are precisely
the constant columns.

g(X) = number of binary matrices of m rows and n columns
such that (i) the rows are distinct and (ii) the
columns indexed by the elements of X are constant.

for each X in P.

Notice that if X is in P, and X has i elements, then

g(X) = 2^i B(2^(n-i), m) m!

Indeed, to construct a matrix as those that g(X)
enumerates, one needs to pick an element of {0, 1}
for each column indexed by X, and then complete
the rows by filling them with the binary digits
corresponding to m different numbers taken from
{0, ..., 2^(n-i) - 1}, one per row.

Moreover, it is clear that

(*) g(X) = sum_{Y such that X subset Y subset I} f(Y).

for all X in P.

Let mu : P x P --> Z be the Moebius function of the
poset P. It is well known (see for example Stanley's
`Enumerative Combinatorics', vol. 1) that

mu(X, Y) = (-1)^(|Y| - |X|)

whenever X subset Y subset I; here |X| is the
cardinal of X, as usual.

The Moebius inversion formula tells us that (*)
implies that

(*) f(X) = sum_{Y such that X subset Y subset I} mu(X, Y) g(Y).

for all X in P. In particular,

f(empty set) = sum_{Y subset I} mu(empty set, I) g(Y)

= sum_{Y subset I} (-1)^|Y| 2^|Y| B(2^(n-|Y|), m) m!

and, since there are B(n, i) subsets of I of cardinal
i for each i in {0, ..., n}, this is

= m! sum_{0 <= i <= n} (-1)^i 2^i B(n, i) B(2^(n-i), m)

Since M_n is precisely f(empty set), we conclude that

M(n,m) = m! sum_{0 <= i <= n} (-2)^i B(n, i) B(2^(n-i), m)

Alternatively, by considering the ways in which an
n-by-(m+1) good matrix can be built by adding an extra
row at the bottom to an n-by-m good matrix, we get
the recurrence

M(n, m+1)

= M(n, m) (2^n - m) + 2^n sum_{1 <= i <= n} M(n-i, m) B(n, i)

and considering the ways in which an (n+1)-by-m good
matrix can be built from a good n-by-m matrix
by adding a column at the end, we get

M(n+1, m)

= M(n, m) (2^m - 2) + m! sum_{1 <= i < m} M(n,i) B(i, m-i) 2^(2i-
m) / i!

It is trivial that

M(n, 1) = 0 for all n >= 1

and

M(1, m) = 0 if n != 2
2 otherwise

Clearly, the last four relations completely determine M.

I haven't looked too hard for a closed formula...

-- m
.