Investigating Maximal T-avoiding configurations of 0-1 matrices with, 4, columns and a general number of rows By Shalosh B. Ekhad Theorem: Let , A[4](r)(z), be the weight-enumerator of MAXIMAL r by , 4, 0-1 matrices avoiding a T pattern [1 1 1] [ ] [* 1 *] according to the weight z^NumberOfOnes (or equivalently, z^SumOfEntries) Then infinity ----- 2 4 \ r (3 x z + 1) x z ) A[4](r)(z) x = - ------------------------------------- / 2 6 2 5 3 2 ----- 3 x z - 2 x z + 2 x z + x z - 1 r = 0 and in Maple notation -(3*x*z^2+1)*x*z^4/(3*x^2*z^6-2*x^2*z^5+2*x*z^3+x*z^2-1) It follows that the generating function for the total number is infinity ----- \ r (3 x + 1) x ) A[4](r)(1) x = - ------------ / 2 ----- x + 3 x - 1 r = 0 For the sake of the OEIS, the first, 30, terms are [1, 6, 19, 63, 208, 687, 2269, 7494, 24751, 81747, 269992, 891723, 2945161, 9727206, 32126779, 106107543, 350449408, 1157455767, 3822816709, 12625905894, 41700534391, 137727509067, 454883061592, 1502376693843, 4962013143121, 16388416123206, 54127261512739, 178770200661423, 590437863497008, 1950083791152447] This seems to be OEIS sequence A189735 The first, 30, terms of the efficient matrices (those with a maximal number of ones) are [1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762, 44287, 132860, 398581, 1195742, 3587227, 10761680, 32285041, 96855122, 290565367, 871696100, 2615088301, 7845264902, 23535794707, 70607384120, 211822152361, 635466457082, 1906399371247, 5719198113740, 17157594341221, 51472783023662] This seems to be OEIS sequence A15518 ------------------------------------------------- First let us note that the EXACT limiting average density as the number or r\ ows goes to infinity is, / / 1/2\3 / 1/2\2 1/2\ | | 13 | | 13 | 7 13 | 1/2 |3 |- 3/2 + -----| - 13 |- 3/2 + -----| - 17/2 + -------| 13 \ \ 2 / \ 2 / 2 / ----------------------------------------------------------------- / 1/2\ / 1/2\ | 13 | | 3 13 | 26 |- 3/2 + -----| |- 7/2 + -------| \ 2 / \ 2 / and in Maple notation 1/26/(-3/2+1/2*13^(1/2))*(3*(-3/2+1/2*13^(1/2))^3-13*(-3/2+1/2*13^(1/2))^2-17/2 +7/2*13^(1/2))/(-7/2+3/2*13^(1/2))*13^(1/2) and in floating-point .7226499000 Now let's specialize and look at the statistical distribution of, 100, by , 4, such matrices, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.7238978235, 0.03440950530, -0.36305565569653410657, 3.1433082685619028373, -3.6827975011610464569, 18.473275821240793744] Here is a plot of the distribution + HH 0.1 HH + H H + H H + H H 0.08 H H + H H + H H + H H 0.06 H H + H HH + H H + HH H 0.04 H H + H H + HH H 0.02 H H + HH H + H H + HH HH +**********************************************************+--+--+--+--+-***- 0 0.55 0.6 0.65 0.7 0.75 Now let's compare it to RSA simulation with, 1000, random permutations of, 400 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7421400000, 0.01095816000, -0.50860739465641796988, 3.1937627439560935451, -4.7176035223905853588, 18.590535043939409150] and a plot of the densitiy distribution is 0.2 HHHHH + HHH H + H H + H H + HH H 0.15 HH HH + H H + H H + H H + HH H 0.1 HH HH + H H + HH H + HH HH + HHH H 0.05 HH H + HH HH + HH H + HH HH + HHHHHHHHHHHH +*********+-+--+-+--+-+--+-+-+--+-+--+-+--+-+--+-+-+--+-+--+-+--+-+-+--+-+--+ 0 0.725 0.73 0.735 0.74 0.745 0.75 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.025199933 ------------------------------------- This ends this atricle that took, 7.613, seconds to generate most of the time was spent by the RSA simulation