Investigating Maximal, {{[0, 0], [0, 1], [1, 0], [1, 1]}}, avoiding configurations of 0-1 matrices with, 4, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[4](r)(z), be the weight-enumerator of MAXIMAL r by , 4, 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 8 20 6 16 6 15 6 14 ) A[4](r)(z) x = - (18 x z - 2 x z - 33 x z - 21 x z / ----- r = 0 5 13 5 12 4 11 4 10 4 9 3 8 3 7 + 4 x z - 63 x z + 5 x z - 8 x z - 7 x z + x z - 11 x z 2 6 2 5 2 4 3 2 4 / 9 24 - x z - 3 x z + 15 x z - x z + 12 x z + 1) x z / (18 x z / 8 22 7 19 7 18 6 17 6 16 5 14 - 6 x z - 33 x z - 21 x z + 15 x z - 58 x z + 12 x z 5 13 4 12 4 11 4 10 3 9 3 8 2 6 - 7 x z - 3 x z - 5 x z + 3 x z - 3 x z + 20 x z + 4 x z 2 5 3 + x z + x z - 1) and in Maple notation -(18*x^8*z^20-2*x^6*z^16-33*x^6*z^15-21*x^6*z^14+4*x^5*z^13-63*x^5*z^12+5*x^4*z ^11-8*x^4*z^10-7*x^4*z^9+x^3*z^8-11*x^3*z^7-x^2*z^6-3*x^2*z^5+15*x^2*z^4-x*z^3+ 12*x*z^2+1)*x*z^4/(18*x^9*z^24-6*x^8*z^22-33*x^7*z^19-21*x^7*z^18+15*x^6*z^17-\ 58*x^6*z^16+12*x^5*z^14-7*x^5*z^13-3*x^4*z^12-5*x^4*z^11+3*x^4*z^10-3*x^3*z^9+ 20*x^3*z^8+4*x^2*z^6+x^2*z^5+x*z^3-1) It follows that the generating function for the total number is infinity ----- \ r ) A[4](r)(1) x = / ----- r = 0 8 6 5 4 3 2 (18 x - 56 x - 59 x - 10 x - 10 x + 11 x + 11 x + 1) x - ----------------------------------------------------------------- 9 8 7 6 5 4 3 2 18 x - 6 x - 54 x - 43 x + 5 x - 5 x + 17 x + 5 x + x - 1 For the sake of the OEIS, the first, 30, terms are [1, 12, 28, 95, 424, 1261, 4817, 17425, 59462, 218640, 771081, 2734910, 9820951, 34798661, 124130661, 442630676, 1574424848, 5613429887, 19992938620, 71203606617, 253711193493, 903645968313, 3219044971566, 11467493903436, 40847861516729, 145512706974362, 518348923928883, 1846459330095113, 6577561711929125, 23430680101268220] First let us note that the EXACT (In floating point) limiting average densit\ y as the number or rows goes to infinity is, 0.6910574228 Now let's specialize and look at the statistical distribution of, 100, by , 4, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.6923449450, 0.01246409294, -0.0077536387499490756723, 2.9912478897566161308, -0.078033015763709576213, 14.869326129073708356] Here is a plot of the distribution 0.18 H + HHH 0.16 H H + H H 0.14 H HH + H H + H H 0.12 H H + H H 0.1 H H + H H 0.08 H H + H H 0.06 H H + H H + H H 0.04 H H + H H 0.02 H H + H H +******************************-+-+--+-+-+--+-+-****************************- 0 0.64 0.66 0.68 0.7 0.72 0.74 Now let's compare it to RSA simulation with, 1000, random permutations of, 400 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7109200000, 0.01334644000, 0.020784488024670114982, 3.4255122184517478083, 0.076493381589209919590, 21.167496699416452303] and a plot of the densitiy distribution is 0.18 HHHHHH + H H 0.16 H H + H H + HH H 0.14 H H + H H 0.12 H H + H HH 0.1 H H + H H 0.08 H H + H HH 0.06 HH H + H H + H H 0.04 HH HHHH + HH HHH 0.02 HH HHH + HHHHH HHHH +************---+---+--+---+---+--+---+---+--+---+---+--+---+---+--+********- 0 0.7 0.71 0.72 0.73 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.026829191 ------------------------------------- This ends this atricle that took, 419.867, seconds to generate most of the time was spent by the RSA simulation