Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mmintl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!amdcad!amdimage!prls!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP (Frank Adams)
Newsgroups: net.math
Subject: Re: Combinatorics question...
Message-ID: <1201@mmintl.UUCP>
Date: Thu, 13-Mar-86 07:29:28 EST
Article-I.D.: mmintl.1201
Posted: Thu Mar 13 07:29:28 1986
Date-Received: Mon, 17-Mar-86 03:53:13 EST
References: <736@harvard.UUCP>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT
Lines: 39

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 is a brief discussion concerning the number P(n,k) of n by n matrices
of 0's and 1's with exactly k 1's in each row and column in a book called
_Advanced_Combinatorics_, by Louis Comtet (D. Riedel Publishing Company, 1974;
translated from the French by J. W. Nienhuys).  He refers to them in general
as "multipermutations" (since the case k=1 is one representation for a
permutation).

Comtet gives a simple summation for P(n,2), and a more complex summation for
P(n,3).  "There is little known about P(n,k) except the asymptotic result"

          (kn)!          2
P(n,k) ~ -------   -(k-1) /2
            2n    e
          k!

"for fixed k and n [goes to infinity]."

A chart for n <= 8 follows; values up to n=7 are from Comtet; the values
for n=8 are my own calculation, except for k=4, which I take from the recent
posting of Lambert Meertens.

n\k| 0     1         2           3            4           5         6     7 8
---+-------------------------------------------------------------------------
 0 | 1
 1 | 1     1
 2 | 1     2         1
 3 | 1     6         6           1
 4 | 1    24        90          24            1
 5 | 1   120      2040        2040          120           1
 6 | 1   720     67950      297200        67950         720         1
 7 | 1  5040   3110940     6893800      6893800     3110940      5040     1
 8 | 1 40320 187530840 24046189440 116963796250 24046189440 187530840 40320 1

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108