Investigating Maximal, {{[0, 0], [0, 1], [1, 0], [1, 1]}}, avoiding configurations of 0-1 matrices with, 3, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[3](r)(z), be the weight-enumerator of MAXIMAL r by , 3, 0-1 matrices avoiding a pattern in the set {{[0, 0], [0, 1], [1, 0], [1, 1]}} according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- \ r 5 9 5 7 4 7 3 6 3 5 3 4 ) A[3](r)(z) x = - (x z - x z + 2 x z - x z + x z - x z / ----- r = 0 2 4 2 3 2 2 2 3 / 6 12 6 10 - x z + 4 x z + x z + x z + 4 x z + 1) x z / (x z - x z / 5 10 5 9 4 9 4 7 3 6 3 5 2 5 2 4 + x z + x z - x z - x z + 3 x z + 2 x z + x z + x z 2 + x z - 1) and in Maple notation -(x^5*z^9-x^5*z^7+2*x^4*z^7-x^3*z^6+x^3*z^5-x^3*z^4-x^2*z^4+4*x^2*z^3+x^2*z^2+x *z^2+4*x*z+1)*x*z^3/(x^6*z^12-x^6*z^10+x^5*z^10+x^5*z^9-x^4*z^9-x^4*z^7+3*x^3*z ^6+2*x^3*z^5+x^2*z^5+x^2*z^4+x*z^2-1) It follows that the generating function for the total number is infinity ----- 4 3 2 \ r (2 x - x + 4 x + 5 x + 1) x ) A[3](r)(1) x = - --------------------------------- / 5 4 3 2 ----- 2 x - 2 x + 5 x + 2 x + x - 1 r = 0 For the sake of the OEIS, the first, 30, terms are [1, 6, 12, 28, 82, 188, 480, 1234, 3026, 7682, 19320, 48306, 121772, 305672, 767470, 1929702, 4846070, 12175024, 30592078, 76848012, 193074552, 485073058, 1218628114, 3061635122, 7691803560, 19324217362, 48548889980, 121970328488, 306428858382, 769849137654] First let us note that the EXACT (In floating point) limiting average densit\ y as the number or rows goes to infinity is, 0.6720429809 Now let's specialize and look at the statistical distribution of, 100, by , 3, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.6731905163, 0.04131703970, 0.099949566726325481922, 3.0155626245005087769, 0.99623326517593816860, 15.324607569738775023] Here is a plot of the distribution + HH + H H 0.1 H H + H H + H H + H HH 0.08 H H + H H + H H 0.06 H H + H H + H H + H H 0.04 H H + H H + H HH + H H 0.02 H H + H H + HH HH +************************-+--+-+--+--+-+-***********************************- 0 0.6 0.65 0.7 0.75 0.8 Now let's compare it to RSA simulation with, 1000, random permutations of, 300 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7386700000, 0.05938599667, -0.11574688157977356532, 2.9178969884555666292, -1.0019867569866585122, 14.294252080774500757] and a plot of the densitiy distribution is + H + H HH + HHH H HH 0.08 HHH HH HHH + HH HHH + HH HH + H H 0.06 H H + H H + H H + H H + H H 0.04 HH HH + H H + HH HH + H H 0.02 H H + HH H H + HH H H H H + HHH H HHH HH +**********---+--+---+--+--+---+--+--+---+--+---+--+--+---+--+-*+---+*******- 0 0.7 0.72 0.74 0.76 0.78 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.097267389 ------------------------------------- This ends this atricle that took, 273.785, seconds to generate most of the time was spent by the RSA simulation