Investigating Maximal T-avoiding configurations of 0-1 matrices with, 6, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[6](r)(z), be the weight-enumerator of MAXIMAL r by , 6, 0-1 matrices avoiding a T pattern [1 1 1] [ ] [* 1 *] according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- \ r 5 19 5 18 4 17 4 16 ) A[6](r)(z) x = - (8 x z + 8 x z + 2 x z - 6 x z / ----- r = 0 4 15 4 14 3 13 3 12 3 11 3 10 + 8 x z - 12 x z + 4 x z - 21 x z + 8 x z - 28 x z 2 9 2 8 2 7 2 6 4 3 2 + 2 x z - 19 x z + 8 x z - 4 x z - 3 x z - 4 x z - 4 x z - 1) x 6 / 6 25 6 24 5 21 5 20 4 17 z / (10 x z + 14 x z + 12 x z - 17 x z - 12 x z / 4 16 3 13 3 12 2 9 2 8 4 - 35 x z - 20 x z + 8 x z - 6 x z - 6 x z - 5 x z + 1) and in Maple notation -(8*x^5*z^19+8*x^5*z^18+2*x^4*z^17-6*x^4*z^16+8*x^4*z^15-12*x^4*z^14+4*x^3*z^13 -21*x^3*z^12+8*x^3*z^11-28*x^3*z^10+2*x^2*z^9-19*x^2*z^8+8*x^2*z^7-4*x^2*z^6-3* x*z^4-4*x*z^3-4*x*z^2-1)*x*z^6/(10*x^6*z^25+14*x^6*z^24+12*x^5*z^21-17*x^5*z^20 -12*x^4*z^17-35*x^4*z^16-20*x^3*z^13+8*x^3*z^12-6*x^2*z^9-6*x^2*z^8-5*x*z^4+1) It follows that the generating function for the total number is infinity ----- 5 4 3 2 \ r (16 x - 8 x - 37 x - 13 x - 11 x - 1) x ) A[6](r)(1) x = - ---------------------------------------------- / 6 5 4 3 2 ----- 24 x - 5 x - 47 x - 12 x - 12 x - 5 x + 1 r = 0 For the sake of the OEIS, the first, 30, terms are [1, 16, 105, 766, 5337, 37878, 267617, 1892808, 13382129, 94624312, 669060105, 4730768806, 33450058329, 236517064494, 1672353023489, 11824791042240, 83610145409969, 591186469710112, 4180131962003625, 29556669726013966, 208987834127550681, 1477700810712375846, 10448453590877536673, 73878407354126433528, 522375777975247982705, 3693588738416982638920, 26116444030843151075913, 184662856945063755877942, 1305704968671866610442329, 9232313922889191325195998] The first, 30, terms of the efficient matrices (those with a maximal number of ones) are [1, 8, 4, 84, 24, 704, 144, 5424, 864, 39744, 5184, 281664, 31104, 1949184, 186624, 13250304, 1119744, 88833024, 6718464, 588985344, 40310784, 3869835264, 241864704, 25234550784, 1451188224, 163500539904, 8707129344, 1053562650624, 52242776064, 6756732370944] ------------------------------------------------- First let us note that the EXACT limiting average density as the number or r\ 11 10 9 8 ows goes to infinity is, -1/3 (16 %1 + 172 %1 + 416 %1 + 1173 %1 7 6 5 4 3 2 / + 976 %1 - 384 %1 + 394 %1 + 948 %1 - 6 %1 + 30 %1 - 44 %1 - 3) / / 5 4 3 2 (%1 (144 %1 - 25 %1 - 188 %1 - 36 %1 - 24 %1 - 5) 5 4 3 2 (16 %1 - 8 %1 - 37 %1 - 13 %1 - 11 %1 - 1)) 6 5 4 3 2 %1 := RootOf(24 _Z - 5 _Z - 47 _Z - 12 _Z - 12 _Z - 5 _Z + 1, index = 1) and in Maple notation -1/3/RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)*(16*RootOf (24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^11+172*RootOf(24*_Z^6 -5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^10+416*RootOf(24*_Z^6-5*_Z^5-\ 47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^9+1173*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-\ 12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^8+976*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-\ 12*_Z^2-5*_Z+1,index = 1)^7-384*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5 *_Z+1,index = 1)^6+394*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1, index = 1)^5+948*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1 )^4-6*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^3+30* RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^2-44*RootOf(24* _Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)-3)/(144*RootOf(24*_Z^6-5* _Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^5-25*RootOf(24*_Z^6-5*_Z^5-47*_Z ^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^4-188*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^ 3-12*_Z^2-5*_Z+1,index = 1)^3-36*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-\ 5*_Z+1,index = 1)^2-24*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1, index = 1)-5)/(16*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^5-8*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^4-37* RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^3-13*RootOf(24* _Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^2-11*RootOf(24*_Z^6-5*_Z^ 5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)-1) and in floating-point .6887296366 Now let's specialize and look at the statistical distribution of, 100, by , 6, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.6904319348, 0.01416765943, 0.056864510488648945873, 2.9589102969899539365, 0.57387966698261782929, 14.422562646901199165] Here is a plot of the distribution + HH + HH H 0.12 H HH + HH H + H H 0.1 H H + H HH + H H 0.08 H H + H H + H H 0.06 HH H + H H + H H 0.04 H H + H H + H H 0.02 HH H + HH H + HH HH +**********--+--+---+--+---+--+---******************************************- 0 0.68 0.7 0.72 0.74 Now let's compare it to RSA simulation with, 1000, random permutations of, 600 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7105983333, 0.01426019833, -0.20082846600586281691, 3.4315448874240924069, -2.1716758091333781879, 21.066487640162164627] and a plot of the densitiy distribution is + HHH 0.14 HH H + HH HH + H H 0.12 HH H + H H 0.1 H H + HH H + H H 0.08 H HH + HH H + H H 0.06 H H + H H + H HH 0.04 HHH H + HHH HH 0.02 H H + HHHH HHHHHH + HHHHH HHH +************+-+-+-+-+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+-+--+-+-+-+-+********- 0 0.695 0.7 0.705 0.71 0.715 0.72 0.725 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.029208380 ------------------------------------- This ends this atricle that took, 16.340, seconds to generate most of the time was spent by the RSA simulation