Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!whuxl!whuxlm!akgua!gatech!seismo!munnari!basser!anucsd!bdm
From: bdm@anucsd.UUCP
Newsgroups: net.math
Subject: Re: Combinatorics question...
Message-ID: <301@anucsd.OZ>
Date: Tue, 25-Mar-86 18:59:12 EST
Article-I.D.: anucsd.301
Posted: Tue Mar 25 18:59:12 1986
Date-Received: Sat, 29-Mar-86 16:22:30 EST
References: <736@harvard.UUCP> <269@anucsd.OZ> <990@h-sc1.UUCP>
Organization: Computer Science, Australian National Uni, Canberra
Lines: 37
Summary: solution

In article <990@h-sc1.UUCP>, breuel@h-sc1.UUCP (thomas breuel) writes:
> 
> 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?
> 
Let K(n) be this number.  We can determine K(n) by inclusion-exclusion.
There are 2^(n^2) 0-1 matrices altogether.  If we take one such at
random, and a specified set of i distinct rows and j distinct columns,
the probability that those rows and columns (and possibly others) are
all zero is exactly  (1/2)^(n*i+n*j-i*j), since n*i+n*j-i*j is the
number of matrix entries involved.  There are exactly
(n choose i)*(n choose j) ways of choosing those rows and columns.
Thus, by inclusion-exclusion,

 K(n) = 2^(n^2) SUM[ (-1)^(i+j) (n choose i) (n choose j) (1/2)^(n*i+n*j-i*j) ]

where the sum is over 0 <= i <= n, 0 <= j <= n.  One of the sums can be done 
(binomial theorem) to get

 K(n) = SUM[ (-1)^j (n choose j) (2^(n-j) - 1)^n ],  sum over 0 <= j <= n. 

I don't know how to do that sum (does anybody?).  The asymptotics are
dominated by the first term.

Incidentally, I have prepared a short summary of what is known about the
asymptotics for the earlier problem (0-1 matrices of specified row/column
sum).  Requests via e-mail.

Brendan McKay.
Computer Science Department, Australian National University, 
GPO Box 4, Canberra, ACT 2601, Australia.

ACSnet: bdm@anucsd.anu.oz	  	       ARPA:  bdm%anucsd.anu.oz@seismo	
CSNET:  bdm@anucsd.anu.oz@csnet-relay.csnet    JANET: anucsd.anu.oz!bdm@ukc
UUCP:   {decvax,vax135,pesnta,eagle}!mulga!anucsd.anu.oz!bdm           or
        {seismo,ubc-vision,ukc,mcvax,prlb2}!munnari!anucsd.anu.oz!bdm
       	  [ UUCP routes through munnari prefered ]