Re: enumerating binary matrices

On Mar 20, 5:52 pm, quasi <qu...@xxxxxxxx> wrote:
Chip Eastham wrote

[edited to correct the previously noted sign error]:

Let F(m,n) be the number of {0,1}-matrices
of size m by n (m rows and n columns), such that:

1) no two rows are the same
2) each column contains both a 0- and a 1-entry

Then for m >= 1:

F(m+1,n) - m F(m,n) = SUM C(n,k) C(k,i) 2^(k-i) F(m,k-i)

where the sum is over i,k s.t. 0 <= i <= k <= n.

The initial conditions are that F(1,0) = 1 and
otherwise F(1,n) = 0.

Your recursive form yields exactly the same numerical values as the
ones I previously posted for 1<=m<=10, 1<=n<=10.

Indeed, the (corrected) formula is equivalent to
my recursions coming from adding rows: let me write
G(n,m) for what Chip writes F(m,n)...

sum_{0 <= i <= k <= n} C(n,k) C(k,i) 2^(k-i) G(k-i,m)

= sum_{0 <= i <= n} sum_{i <= k <= n} C(n,k) C(k,i) 2^(k-i) G(k-i,m)

= sum_{0 <= i <= n} sum_{0 <= k <= n-i} C(n,k+i) C(k+i,i) 2^k G(k,m)

which, interchanging sums, is

= sum_{0 <= k <= n} 2^k G(k,m) (sum_{0 <= i <= n-k} C(n,k+i) C(k
+i,i))

and since we have that

sum_{0 <= i <= n-k} C(n,k+i) C(k+i,i) = 2^(n-k) C(n,k)

this is

= sum_{0 <= k <= n} 2^n C(n,k) G(k,m)

Therefore Chip's recursion is the same as

G(n,m+1) - m G(n,m) = 2^n sum_{0 <= k <= n} C(n,k) G(k,m)

which itself is easily seen to be by first recursion.

-- m

.

Quantcast