Investigating Maximal T-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 a T pattern [1 1 1] [ ] [* 1 *] according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- \ r 4 15 4 14 3 12 3 11 3 10 ) A[5](r)(z) x = - (2 x z - 2 x z - x z + 2 x z - x z / ----- r = 0 2 9 2 8 2 7 5 4 3 / 5 17 + x z - 5 x z + 4 x z - x z + 2 x z + x z - 1) / (8 x z / 4 14 4 13 3 11 3 10 2 8 2 7 4 - 2 x z + 4 x z + 3 x z - 7 x z + x z - 8 x z - 2 x z 3 - x z + 1) and in Maple notation -(2*x^4*z^15-2*x^4*z^14-x^3*z^12+2*x^3*z^11-x^3*z^10+x^2*z^9-5*x^2*z^8+4*x^2*z^ 7-x*z^5+2*x*z^4+x*z^3-1)/(8*x^5*z^17-2*x^4*z^14+4*x^4*z^13+3*x^3*z^11-7*x^3*z^ 10+x^2*z^8-8*x^2*z^7-2*x*z^4-x*z^3+1) It follows that the generating function for the total number is infinity ----- \ r 2 x - 1 ) A[5](r)(1) x = - ----------------------------------- / 5 4 3 2 ----- 8 x + 2 x - 4 x - 7 x - 3 x + 1 r = 0 For the sake of the OEIS, the first, 30, terms are [1, 10, 41, 195, 902, 4207, 19553, 90998, 423329, 1969555, 9163198, 42631375, 198340089, 922766942, 4293124113, 19973532955, 92925804246, 432332385279, 2011403533617, 9357948455974, 43537359772225, 202555261438435, 942377630395310, 4384362035162991, 20398012256817641, 94900672137120430, 441520352997438641, 2054150067865941035, 9556824442333436102, 44462619771722868127] This is not yet in the OEIS The first, 30, terms of the efficient matrices (those with a maximal number of ones) are [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ------------------------------------------------- First let us note that the EXACT limiting average density as the number or r\ ows goes to infinity is, 1/5 8 7 6 5 4 3 2 16 %1 + 4 %1 - 32 %1 - 244 %1 + 106 %1 + 97 %1 + 26 %1 - 47 %1 - 5 ------------------------------------------------------------------------- 4 3 2 (40 %1 + 8 %1 - 12 %1 - 14 %1 - 3) (-2 %1 + 1) 5 4 3 2 %1 := RootOf(8 _Z + 2 _Z - 4 _Z - 7 _Z - 3 _Z + 1, index = 1) and in Maple notation 1/5*(16*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^8+4*RootOf(8*_Z^5+ 2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^7-32*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-\ 3*_Z+1,index = 1)^6-244*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^5+ 106*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^4+97*RootOf(8*_Z^5+2* _Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^3+26*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3* _Z+1,index = 1)^2-47*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)-5)/( 40*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^4+8*RootOf(8*_Z^5+2*_Z^ 4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)^3-12*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+ 1,index = 1)^2-14*RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)-3)/(-2* RootOf(8*_Z^5+2*_Z^4-4*_Z^3-7*_Z^2-3*_Z+1,index = 1)+1) and in floating-point .7031981290 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.7046288468, 0.01811830215, 0.014557948434501752410, 2.9983670085269842769, 0.14369541214789249481, 14.979589342496894324] Here is a plot of the distribution + H + H H 0.12 H H + H H + H H 0.1 H H + H H + H H 0.08 H H + H H + H H 0.06 H H + H H + H H 0.04 HH H + H H + 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, 10000, random permutations of, 500 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7295268000, 0.02123284088, -0.032835402963931912122, 2.9827178967352417458, -0.27827377180749362040, 15.022164179090202921] and a plot of the densitiy distribution is 0.12 HHH + HH HHHH + H H + H HH 0.1 HH H + H HH + H H 0.08 H H + H H + H HH 0.06 H H + H H + H H + H H 0.04 H H + HH H + HH H 0.02 HH HH + HH HH + HHH HHHH +*****************+-+--+--+--+-+--+--+-+--+--+-+--+--+--+-+--+--+***********- 0 0.7 0.71 0.72 0.73 0.74 0.75 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.035334848 ------------------------------------- This ends this atricle that took, 135.264, seconds to generate most of the time was spent by the RSA simulation