msp@warwick.UUCP (Mike Paterson) (03/11/86)
Distribution: Xpath: ukc eagle I am afraid I have lost the original reference but Lambert Meertens writes: >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) A lower bound of the form (2m;m)^(2m-a.sqrt(m)) may be derived as follows. Let c = a.sqrt(m) and consider taking for the first 2m-c rows independent random choices from the (2m;m) possibilities. If the resulting column sums are all in the range [m-c,m] then the pattern can be completed by successively assigning 0's to m of the columns with the largest current sums (and 1's elsewhere) for each remaining row. The expected number of column sums which are outside the required range after choosing the first 2m-c rows can be made less than 1/2 say, by an appropriate choice of the constant a. For this value the majority of the (2m;m)^(2m-c) ways of picking the first 2m-c rows can be completed. Mike Paterson