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 5 3 2 \ r x z + x z - 2 x z + 1 ) 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^2*z^5+x*z^3-2*x*z^2+1)/(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 - x + 1 ) 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 4 3 2 4 (172 + 36 29 ) 80 2 %1 - 6 %1 - 3 %1 + --------------------- - --------------------- + 1/3 3 1/2 1/3 3 (172 + 36 29 ) \ / / 1/2 1/3 \ | / | | 2 (172 + 36 29 ) 20 | | / |3 |3 %1 + ------------------- - --------------------- + 4/3| | / | | 3 1/2 1/3 | / \ \ 3 (172 + 36 29 ) / / 1/2 1/3 \\ | 2 (172 + 36 29 ) 10 || |-%1 + ------------------- - --------------------- - 4/3|| | 6 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*(2*(1/6*(172+36*29^(1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)^4-6*(1/6 *(172+36*29^(1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)^3-3*(1/6*(172+36*29^ (1/2))^(1/3)-10/3/(172+36*29^(1/2))^(1/3)-1/3)^2+4/3*(172+36*29^(1/2))^(1/3)-80 /3/(172+36*29^(1/2))^(1/3)+1/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)/(-(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)-4/3) and in floating-point .7227884439 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.018, seconds to generate most of the time was spent by the RSA simulation