greg@harvard.UUCP (Greg) (02/25/86)
While playing with the little 8x8 patterns on my Macintosh, the following question occured to me: How many 8x8 matrices of 0's and 1's are there in which each row and column has precisely four 1's? -- gregregreg
lambert@boring.uucp (Lambert Meertens) (02/27/86)
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? This reminds me of a problem posed some time ago in this newsgroup: How many ways are there to deal a deck of cards to four people such that each person has at least four cards of each suit? While I do not know how to tackle that one, the 8x8 problem can be solved by actual enumeration. A program I wrote returned 116963796250 = 2.5^4.7^2.313.6101. So, modulo the correctness of the program (which might well contain bugs since it contains several speed-up tricks), this is the answer. Can someone corroborate this? A more important question: 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 The sequence is not in Sloane's handbook. -- Lambert Meertens ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam
az@inmet.UUCP (03/02/86)
57648010000000
franka@mmintl.UUCP (03/07/86)
In article <6802@boring.UUCP> lambert@boring.UUCP (Lambert Meertens) writes: >This reminds me of a problem posed some time ago in this newsgroup: How >many ways are there to deal a deck of cards to four people such that each >person has at least four cards of each suit? I think you must have misquoted the problem. As stated, the answer is simple: zero. For four people to each have four cards in a suit, there must be at least 16 cards in the suit. But in fact, there are only 13 cards in each suit. Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
lambert@boring.UUCP (03/09/86)
In article <1184@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes: > In article <6802@boring.UUCP> lambert@boring.UUCP (Lambert Meertens) writes: >> This reminds me of a problem posed some time ago in this newsgroup: How >> many ways are there to deal a deck of cards to four people such that each >> person has at least four cards of each suit? > > I think you must have misquoted the problem. As stated, the answer is > simple: zero. For four people to each have four cards in a suit, there > must be at least 16 cards in the suit. But in fact, there are only 13 > cards in each suit. Indeed. As Jan Kok pointed out to me, the problem as originally posted required every person to have at least TWO cards of each suit. For the problem of the number of (2m)x(2m) 0-1 matrices in which all colums and rows add up to m, Evangelos Kranakis showed me a simple proof of lower and upper bounds. If {2m;m} stands for that number, and (2m;m) for "2m over m", then m 2m-1 (2m;m) <= {2m;m} <= (2m;m) The upper bound is obtained by considering all ways to fill the first 2m-1 rows so that they add up to m. The entries in the last row are then determined by the column-sum requirement. The lower bound follows from the fact that after filling the first m rows, one can complete this to a correct design by copying the complement of the top half into the bottom half. -- Lambert Meertens ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam
anthony@utcsstat.uucp (Anthony Ayiomamitis) (03/10/86)
franka@mmitl <1184@mmintl.UUCP> writes: > > In article <6802@boring.UUCP> lambert@boring.UUCP (Lambert Meertens) writes: > >This reminds me of a problem posed some time ago in this newsgroup: How > >many ways are there to deal a deck of cards to four people such that each > >person has at least four cards of each suit? > > I think you must have misquoted the problem. As stated, the answer is > simple: zero. For four people to each have four cards in a suit, there > must be at least 16 cards in the suit. But in fact, there are only 13 > cards in each suit. > > Frank Adams ihnp4!philabs!pwa-b!mmintl!franka > Multimate International 52 Oakland Ave North E. Hartford, CT 06108 > I don't think it was a requirement that all players have the same suit. -- {allegra,ihnp4,linus,decvax}!utzoo!utcsstat!anthony {ihnp4|decvax|utzoo|utcsrgv}!utcs!utzoo!utcsstat!anthony
franka@mmintl.UUCP (Frank Adams) (03/13/86)
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
bdm@anucsd.UUCP (03/14/86)
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 ]
bdm@anucsd.UUCP (03/14/86)
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? (continuation of earlier response) If one only considers equivalence classes of such matrices under the operations of row permutation, column permutation and transpose, there are exactly 130 cases. This was determined about 1976 by I.A.Faradzev using exhaustive enumeration. Brendan McKay. Computer Science Department, Australian National University, GPO Box 4, Canberra, ACT 2601, Australia. 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 ]
bdm@anucsd.UUCP (03/14/86)
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 ]
eklhad@ihnet.UUCP (K. A. Dahlke) (03/20/86)
> 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
bdm@anucsd.UUCP (03/26/86)
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 ]