Investigating Maximal T-avoiding configurations of 0-1 matrices with, 3, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[3](r)(z), be the weight-enumerator of MAXIMAL r by , 3, 0-1 matrices avoiding a T pattern [1 1 1] [ ] [* 1 *] according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- 2 2 3 \ r (x z + 1) x z ) A[3](r)(z) x = - -------------------------- / 3 7 2 5 2 ----- x z + x z + 2 x z - 1 r = 0 and in Maple notation -(x*z^2+1)^2*x*z^3/(x^3*z^7+x^2*z^5+2*x*z^2-1) It follows that the generating function for the total number is infinity ----- 2 \ r (x + 1) x ) A[3](r)(1) x = - ----------------- / 3 2 ----- x + x + 2 x - 1 r = 0 For the sake of the OEIS, the first, 30, terms are [1, 4, 10, 25, 64, 163, 415, 1057, 2692, 6856, 17461, 44470, 113257, 288445, 734617, 1870936, 4764934, 12135421, 30906712, 78713779, 200469691, 510559873, 1300303216, 3311635996, 8434135081, 21480209374, 54706189825, 139326724105, 354839847409, 903712608748] This seems to be OEIS sequence A347725 The first, 30, terms of the efficient matrices (those with a maximal number of ones) are [1, 4, 1, 7, 1, 10, 1, 13, 1, 16, 1, 19, 1, 22, 1, 25, 1, 28, 1, 31, 1, 34, 1, 37, 1, 40, 1, 43, 1, 46] ------------------------------------------------- First let us note that the EXACT limiting average density as the number or r\ / | ows goes to infinity is, | | \ 1/2 1/3 \ / 3 2 5 (172 + 36 29 ) 50 | / | 2 %1 - 8 %1 + --------------------- - --------------------- + 4/3| / |3 6 1/2 1/3 | / | 3 (172 + 36 29 ) / \ / 1/2 1/3 \ |(172 + 36 29 ) 10 | |------------------- - --------------------- + 2/3| %1 | 6 1/2 1/3 | \ 3 (172 + 36 29 ) / / 1/2 1/3 \\ | 2 (172 + 36 29 ) 20 || |3 %1 + ------------------- - --------------------- + 4/3|| | 3 1/2 1/3 || \ 3 (172 + 36 29 ) // 1/2 1/3 (172 + 36 29 ) 10 %1 := ------------------- - --------------------- - 1/3 6 1/2 1/3 3 (172 + 36 29 ) and in Maple notation 1/3/(1/6*(172+36*29^(1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)+2/3)/(1/6*(172+36 *29^(1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)*(2*(1/6*(172+36*29^(1/2))^(1 /3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)^3-8*(1/6*(172+36*29^(1/2))^(1/3)-10/3/( 172+36*29^(1/2))^(1/3)-1/3)^2+5/6*(172+36*29^(1/2))^(1/3)-50/3/(172+36*29^(1/2) )^(1/3)+4/3)/(3*(1/6*(172+36*29^(1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)^ 2+1/3*(172+36*29^(1/2))^(1/3)-20/3/(172+36*29^(1/2))^(1/3)+4/3) and in floating-point .7227884433 Now let's specialize and look at the statistical distribution of, 100, by , 3, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.7248201893, 0.02697558317, 0.031083750092000815980, 2.9641553955140688229, 0.31237679421653586537, 14.478079431925294912] Here is a plot of the distribution 0.14 HHH + HH HH + H H 0.12 H HH + H H + H H 0.1 H H + H H 0.08 HH H + H H + H H 0.06 H H + H H + H H 0.04 H H + H H + H H 0.02 HH H + H H + HH HH +**************+-++-+-+-+-++-+-+-+-++-**************************************+ 0 0.68 0.7 0.72 0.74 0.76 0.78 0.8 0.82 Now let's compare it to RSA simulation with, 1000, random permutations of, 300 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7635400000, 0.02605385333, 0.042831758879458960850, 3.1343984925357258757, 0.33399807424367187318, 17.483121901278230790] and a plot of the densitiy distribution is + HHHHHHHHH + H H 0.12 H HH + H H + H H 0.1 H H + H H + H H 0.08 H HH + HH H + H H 0.06 HH HH + H H + HH H 0.04 H H + H HH + H H 0.02 HH HH + HH HH + HHHHH HHHHHHHHH +***********+--+-+-+-+-+--+-+-+-+-+--+-+-+-+-+-+--+-+-+-+-+--+-+-+-+-*******+ 0 0.74 0.75 0.76 0.77 0.78 0.79 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.053419884 ------------------------------------- This ends this atricle that took, 6.415, seconds to generate most of the time was spent by the RSA simulation