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 6 25 6 24 5 23 5 22 5 21 ) A[6](r)(z) x = (2 x z + 6 x z - 2 x z + 6 x z + 4 x z / ----- r = 0 5 20 4 19 4 18 4 17 4 16 3 15 - 5 x z - 4 x z + 21 x z - 20 x z - 7 x z - 2 x z 3 14 3 13 3 12 2 10 2 9 2 8 6 + 19 x z - 28 x z + 12 x z + 3 x z - 2 x z - 2 x z + x z 4 / 6 25 6 24 5 21 5 20 - 5 x z + 1) / (10 x z + 14 x z + 12 x z - 17 x z / 4 17 4 16 3 13 3 12 2 9 2 8 - 12 x z - 35 x z - 20 x z + 8 x z - 6 x z - 6 x z 4 - 5 x z + 1) and in Maple notation (2*x^6*z^25+6*x^6*z^24-2*x^5*z^23+6*x^5*z^22+4*x^5*z^21-5*x^5*z^20-4*x^4*z^19+ 21*x^4*z^18-20*x^4*z^17-7*x^4*z^16-2*x^3*z^15+19*x^3*z^14-28*x^3*z^13+12*x^3*z^ 12+3*x^2*z^10-2*x^2*z^9-2*x^2*z^8+x*z^6-5*x*z^4+1)/(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 ----- 6 5 4 3 2 \ r 8 x + 3 x - 10 x + x - x - 4 x + 1 ) 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 ((144 %1 - 25 %1 - 188 %1 - 36 %1 - 24 %1 - 5) 6 5 4 3 2 (8 %1 + 3 %1 - 10 %1 + %1 - %1 - 4 %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*(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)/(8*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1, index = 1)^6+3*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^ 5-10*RootOf(24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^4+RootOf( 24*_Z^6-5*_Z^5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^3-RootOf(24*_Z^6-5*_Z^ 5-47*_Z^4-12*_Z^3-12*_Z^2-5*_Z+1,index = 1)^2-4*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 .6887296373 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, 10000, random permutations of, 600 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7106760000, 0.01463648107, -0.037323638726263685850, 3.0810122465471450477, -0.57868665526464319223, 15.891092761377056632] and a plot of the densitiy distribution is + HHHHH + H H 0.12 HH HH + HH H + H H 0.1 H HH + H H + H H 0.08 HH H + H H + H H 0.06 H H + H HH + H H 0.04 H HH + HH H + H H 0.02 HH HH + HH HH + HHHH HHHH +***************-+-+-++-+-+-+-+-+-+-+-+-++-+-+-+-+-+-+-+-+-+-++-+-+*********+ 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.029320870 ------------------------------------- This ends this atricle that took, 175.613, seconds to generate most of the time was spent by the RSA simulation