Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 exptools; site ihnet.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!ihnet!eklhad
From: eklhad@ihnet.UUCP (K. A. Dahlke)
Newsgroups: net.math
Subject: Re: Combinatorics question...
Message-ID: <397@ihnet.UUCP>
Date: Thu, 20-Mar-86 11:35:28 EST
Article-I.D.: ihnet.397
Posted: Thu Mar 20 11:35:28 1986
Date-Received: Sat, 22-Mar-86 06:02:15 EST
References: <736@harvard.UUCP> <269@anucsd.OZ> <990@h-sc1.UUCP>
Organization: AT&T Bell Laboratories
Lines: 44

> 						Thomas.
> Let me ask a similar question: how many nxn matrices of 0's and 1's are
> there in which each row and column has at least one 1?

This question is considerably easier than the original.
The trick is to generalize the problem.  Although this technique usually
increases complexity, sometimes ...

Define F(m,n) to be the number of mxn binary matrices with at least
one 1 in each row and column.  We can now derive a recurrence relation.

Consider any "legal" mxn matrix, and temporarily ignore the last column.
Suppose the truncated m by n-1 matrix has i rows containing at least one 1,
leaving m-i rows of all 0's.
The number of such truncated matrices is F(i,n-1) * c(m,i),
where c(m,i) is m choose i.
Now fill in the last column.  The m-i rows of 0's leave us no choice.
The corresponding entries in the last column must equal 1.
The i nonzero rows leav the last column unconstrained.
Thus, we multiply by 2^i.  Sum these terms as i goes from 0 to m.
When i = 0 and m, boundary conditions distort the formula slightly.
A rather inefficient Unix bc(1) implementation follows.
Better implementations will run in polynomial time (and space).

define c(n,k){
auto i,t
t=1
for(i=n-k+1;i<=n;i=i+1) t=t*i
for(i=2;i<=k;i=i+1) t=t/i
return (t)
}

define f(m,n){
auto i,t
if(n==1) return (1)
t=0
for(i=1;i<m;i=i+1)  t=t+c(m,i)*f(i,n-1)*2^i
t=t+f(m,n-1)*(2^i-1)
return (t)
}
-- 
	The moon is more important than the sun, because
	the moon gives us light at night; when we really need it!
			Karl Dahlke    ihnp4!ihnet!eklhad