Investigating Maximal Dimer-avoiding configurations of 0-1 matrices with, 5, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[5](r)(z), be the weight-enumerator of MAXIMAL r by , 5, 0-\ 1 matrices avoiding Dimers, i.e. two consecutive horizontal 1s and also \ avoiding two consecutive vertical ones according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- \ r 13 17 13 16 12 17 12 16 ) A[5](r)(z) x = - (3 x z - x z - 4 x z + 10 x z / ----- r = 0 11 17 11 16 11 15 11 14 10 15 11 13 + 2 x z - 9 x z - 9 x z + 17 x z + 18 x z + x z 10 14 9 15 10 13 9 14 10 12 9 13 - 18 x z - 4 x z - 22 x z - 8 x z + 4 x z + 47 x z 8 14 9 12 9 11 8 12 8 11 7 12 + 2 x z + 4 x z - x z - 43 x z - 12 x z + 9 x z 8 10 7 11 7 10 6 11 7 9 6 10 + 3 x z + 2 x z + 40 x z - 10 x z - 30 x z + 36 x z 7 8 6 9 5 10 6 8 5 9 6 7 5 8 - x z - 74 x z + 2 x z + 33 x z - 19 x z - 5 x z + 45 x z 5 7 4 8 5 6 4 7 4 6 3 7 4 5 - 25 x z + 13 x z - x z - 33 x z + 11 x z - 2 x z - 9 x z 3 6 3 5 3 4 2 5 2 4 2 3 2 2 + 7 x z - 26 x z + 11 x z - 5 x z + 7 x z + 9 x z + x z 3 2 2 / 13 17 12 17 12 16 + x z + 3 x z + 2 x z + z + 3) x z / (x z - 2 x z + 2 x z / 11 17 11 16 11 15 10 16 11 14 10 15 + x z + 2 x z - 5 x z - 4 x z + 2 x z + 10 x z 9 16 10 14 9 15 10 13 9 14 9 13 + x z - 6 x z - 3 x z + 4 x z + 5 x z - 14 x z 8 14 9 12 8 13 9 11 8 12 7 13 - 2 x z - 4 x z + 10 x z - x z + 3 x z - 3 x z 8 11 7 12 8 10 7 11 6 12 7 10 - 7 x z + 10 x z - 2 x z - 26 x z + x z + 19 x z 6 11 7 9 6 10 6 9 5 10 6 8 5 9 - 2 x z - 2 x z + 12 x z - 4 x z + 3 x z - 6 x z - 3 x z 5 8 4 9 5 7 5 6 4 7 4 6 3 7 4 5 - 22 x z - x z + x z + x z - 8 x z + 10 x z - x z + 3 x z 3 5 2 5 2 4 2 3 2 + 11 x z + x z + x z + 2 x z + x z - 1) and in Maple notation -(3*x^13*z^17-x^13*z^16-4*x^12*z^17+10*x^12*z^16+2*x^11*z^17-9*x^11*z^16-9*x^11 *z^15+17*x^11*z^14+18*x^10*z^15+x^11*z^13-18*x^10*z^14-4*x^9*z^15-22*x^10*z^13-\ 8*x^9*z^14+4*x^10*z^12+47*x^9*z^13+2*x^8*z^14+4*x^9*z^12-x^9*z^11-43*x^8*z^12-\ 12*x^8*z^11+9*x^7*z^12+3*x^8*z^10+2*x^7*z^11+40*x^7*z^10-10*x^6*z^11-30*x^7*z^9 +36*x^6*z^10-x^7*z^8-74*x^6*z^9+2*x^5*z^10+33*x^6*z^8-19*x^5*z^9-5*x^6*z^7+45*x ^5*z^8-25*x^5*z^7+13*x^4*z^8-x^5*z^6-33*x^4*z^7+11*x^4*z^6-2*x^3*z^7-9*x^4*z^5+ 7*x^3*z^6-26*x^3*z^5+11*x^3*z^4-5*x^2*z^5+7*x^2*z^4+9*x^2*z^3+x^2*z^2+x*z^3+3*x *z^2+2*x*z+z+3)*x*z^2/(x^13*z^17-2*x^12*z^17+2*x^12*z^16+x^11*z^17+2*x^11*z^16-\ 5*x^11*z^15-4*x^10*z^16+2*x^11*z^14+10*x^10*z^15+x^9*z^16-6*x^10*z^14-3*x^9*z^ 15+4*x^10*z^13+5*x^9*z^14-14*x^9*z^13-2*x^8*z^14-4*x^9*z^12+10*x^8*z^13-x^9*z^ 11+3*x^8*z^12-3*x^7*z^13-7*x^8*z^11+10*x^7*z^12-2*x^8*z^10-26*x^7*z^11+x^6*z^12 +19*x^7*z^10-2*x^6*z^11-2*x^7*z^9+12*x^6*z^10-4*x^6*z^9+3*x^5*z^10-6*x^6*z^8-3* x^5*z^9-22*x^5*z^8-x^4*z^9+x^5*z^7+x^5*z^6-8*x^4*z^7+10*x^4*z^6-x^3*z^7+3*x^4*z ^5+11*x^3*z^5+x^2*z^5+x^2*z^4+2*x^2*z^3+x*z^2-1) It follows that the generating function for the total number is infinity ----- \ r 13 12 11 10 9 8 ) A[5](r)(1) x = - (2 x + 6 x + 2 x - 18 x + 38 x - 50 x / ----- r = 0 7 6 5 4 3 2 / 13 + 20 x - 20 x + 2 x - 18 x - 10 x + 12 x + 6 x + 4) x / (x / 10 9 8 7 6 5 4 3 2 + 4 x - 16 x + 2 x - 2 x + x - 20 x + 4 x + 10 x + 4 x + x - 1) For the sake of the OEIS, the first, 30, terms are [4, 10, 38, 108, 358, 1132, 3580, 11382, 36270, 114992, 365628, 1162290, 3692624, 11733828, 37293892, 118504546, 376583590, 1196750110, 3803034578, 12085297922, 38405269512, 122045123484, 387837623386, 1232482503260, 3916616317912, 12446322770862, 39552271908226, 125690284637502, 399421938977022, 1269293892301040] ------------------------------------------------- First let us note that the EXACT limiting average density as the number or r\ ows goes to infinity is, 0.3417823740 Now let's specialize and look at the statistical distribution of, 100, by , 5, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.3428648678, 0.03689521376, 0.086272087584751936032, 3.0098559292000324922, 0.86476360594853533000, 15.226703953591493014] Here is a plot of the distribution + HH + H H + H H 0.08 HH H + H HH + H H + H H 0.06 H H + H H + H H + H H 0.04 H H + H H + HH H + H H + H H 0.02 H H + H H + H H + H HH +************************-+--+--+--+-***************************************- 0 0.25 0.3 0.35 0.4 0.45 0.5 Now let's compare it to RSA simulation with, 1000, random permutations of, 500 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.3816700000, 0.05700355000, 0.19004587663493799109, 2.9378849354061084178, 1.8026761914624135170, 14.076800225778698196] and a plot of the densitiy distribution is + HHH + HH HHHH 0.07 HHH H H + HH H HHH 0.06 H HH + H HH + H H 0.05 HH H + H H 0.04 H H + HH HHH + H H 0.03 H H HH + HH H H + H HHH H 0.02 H HH + H H 0.01 H HH H + H H H HHH HH + HHHH HH HH H +****-+-+-+--+-+-+-+-+--+-+-+-+-+--+-+-+-+--+-+-+-+-+--+-+-+-+-+--**********- 0 0.36 0.37 0.38 0.39 0.4 0.41 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.113179086 ------------------------------------- This ends this atricle that took, 638.812, seconds to generate most of the time was spent by the RSA simulation