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: <268@anucsd.OZ>
Date: Thu, 13-Mar-86 20:04:27 EST
Article-I.D.: anucsd.268
Posted: Thu Mar 13 20:04:27 1986
Date-Received: Mon, 17-Mar-86 04:42:20 EST
References: <736@harvard.UUCP>
Organization: Computer Science, Australian National Uni, Canberra
Lines: 34
Summary: solution

In article <736@harvard.UUCP>, greg@harvard.UUCP (Greg) writes:
> 
> How many 8x8 matrices of 0's and 1's are there in which each row and column
> has precisely four 1's?
There are precisely 116963796250 such matrices.  This number, and answers to
all similar questions for square matrices to 20 x 20 can be found in

B. D. McKay, Applications of a technique for labelled enumeration, 
   Congressus Numerantium, vol. 40 (1983) 207-221.

The 8 x 8 problem can probably be handled by exhaustive enumeration if care is
taken to factor the problem into equivalent subproblems.  For example, one
can assume that the entries a[1..4,1] and a[1,1..4] hold ones, then multiply
the result by (8 choose 4)*(7 choose 3), and so on.
It is also probably within the range of most symbolic algebra systems to
compute it thus:
	Take the coefficient of x^4 in (1+xa)(1+xb)...(1+xh), raise that to the
	eighth power and extract the coefficient of a^4b^4...h^4.
The method used in the paper above is more complicated, but suitable for
much larger problems.

There is also some asymptotics work in progress on this problem by various
people.  e-mail me for details.


Brendan McKay.
Computer Science Dept., 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 ]