Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!houxm!whuxl!whuxlm!akgua!gatech!seismo!munnari!basser!anucsd!bdm
From: bdm@anucsd.UUCP
Newsgroups: net.math
Subject: Re: Combinatorics question...
Message-ID: <270@anucsd.OZ>
Date: Fri, 14-Mar-86 00:40:47 EST
Article-I.D.: anucsd.270
Posted: Fri Mar 14 00:40:47 1986
Date-Received: Mon, 17-Mar-86 04:42:50 EST
References: <736@harvard.UUCP> <6802@boring.UUCP>
Organization: Computer Science, Australian National Uni, Canberra
Lines: 37

In article <6802@boring.UUCP>, lambert@boring.uucp (Lambert Meertens) writes:
> 
> In article <736@harvard.UUCP> greg@harvard.UUCP writes:
> > How many 8x8 matrices of 0's and 1's are there in which each row and column
> > has precisely four 1's?
> 
>          116963796250 =
> 2.5^4.7^2.313.6101.
> Can someone corroborate this?
 
Yes.

> Have formulas or theories been developed for this type of enumeration?
> And: What is the general formula for (2m)x(2m) 0-1 matrices with m 1's in
> each row and column?  My program gave:
> 
>   F(1) = 2
>   F(2) = 90
>   F(3) = 297200
>   F(4) = 116963796250

There is no known such formula.  More generally, let M(n,k) be the number
of n x n 0-1 matrices with line sums k.
Formulas exist for k = 0,1,2,3, but for no larger k.  For F(m), values
are known up to F(10)  (92 digits), and the asymptotic value is known
(probably - Andy, is it done?) but no general formula of any use has
been found.

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 ]