Investigating Maximal words in {0,1} avoiding , 2, consecutive ones By Shalosh B. Ekhad Theorem: Let , A(c)(x), be the weight-enumerator of MAXIMAL words in {0,1} of length c, avoiding, 2, consecutive ones according to the weight x^NumberOfOnes (or equivalently, x^SumOfEntries) Then infinity ----- 2 \ c t x + t x + 1 ) A(c)(x) t = - --------------- / 3 2 ----- t x + t x - 1 c = 0 and in Maple notation -(t^2*x+t*x+1)/(t^3*x+t^2*x-1) It follows that the generating function for the total number is infinity ----- 2 \ c t + t + 1 ) A(c)(1) t = - ----------- / 3 2 ----- t + t - 1 c = 0 For the sake of the OEIS, the first, 30, terms are [1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410] ------------------------------------------------- First let us note that the EXACT limiting average density as the length of t\ he word goes to infinity is, 0.4114955887 Now let's specialize and look at the statistical distribution of words of le\ ngth, 200, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.4128755536, 0.01734112270, 0.035456590777305438004, 2.9775311089698181181, 0.34961955190620705149, 14.677058216523154126] Here is a plot of the distribution + HHH 0.2 H H + H H + H H + H H + H H 0.15 H H + H H + H H + H H 0.1 H H + H H + H H + H H + H H 0.05 H H + H H + H HH + H H + HH HH +************************+-++-+-+-+-++-+-+-++-+-****************************- 0 0.34 0.36 0.38 0.4 0.42 0.44 0.46 0.48 0.5 Now let's compare it to RSA simulation with, 10000, random permutations of, 200 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.4339030000, 0.01821431820, -0.011550048556103846153, 2.9473955240028196900, -0.16148841306488667799, 14.048134080834395631] and a plot of the densitiy distribution is + HHH 0.2 HHHH HH + H HH + H H + HH HH 0.15 H H + H H + H H + H H + HH HH 0.1 H H + H H + H H + H H + HH HH 0.05 HH H + H HH + HH HH + HHH HH + HHHHH HHHHH +*********+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-*******+ 0 0.4 0.41 0.42 0.43 0.44 0.45 0.46 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.050929260 and The ratio of the exact s.d (under the uniform distribution) and the s.d \ of RSA simulations is 1.050354035 ------------------------------------- This ends this article that took, 219.238, seconds to generate most of the time was spent by the RSA simulation -------------------------------------------------- Investigating Maximal words in {0,1} avoiding , 3, consecutive ones By Shalosh B. Ekhad Theorem: Let , A(c)(x), be the weight-enumerator of MAXIMAL words in {0,1} of length c, avoiding, 3, consecutive ones according to the weight x^NumberOfOnes (or equivalently, x^SumOfEntries) Then infinity ----- 5 3 3 2 2 2 2 \ c t x - t x - t x + t x - t x - 1 ) A(c)(x) t = - -------------------------------------- / 6 3 4 2 3 2 2 ----- t x - t x - t x - t x + 1 c = 0 and in Maple notation -(t^5*x^3-t^3*x^2-t^2*x^2+t^2*x-t*x-1)/(t^6*x^3-t^4*x^2-t^3*x^2-t^2*x+1) It follows that the generating function for the total number is infinity ----- 5 3 \ c t - t - t - 1 ) A(c)(1) t = - --------------------- / 6 4 3 2 ----- t - t - t - t + 1 c = 0 For the sake of the OEIS, the first, 30, terms are [1, 1, 3, 3, 4, 6, 9, 12, 16, 24, 33, 46, 64, 91, 127, 177, 249, 349, 489, 684, 960, 1345, 1884, 2640, 3700, 5185, 7264, 10180, 14265, 19989] ------------------------------------------------- First let us note that the EXACT limiting average density as the length of t\ he word goes to infinity is, 0.5772029462 Now let's specialize and look at the statistical distribution of words of le\ ngth, 200, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.5791614170, 0.01505366345, 0.041926374082080306069, 2.9799263521836189472, 0.41352639444533695476, 14.717435752555791195] Here is a plot of the distribution + H + HHH 0.2 H H + H H + H H + HH H + H H 0.15 H H + H H + H H + H H 0.1 HH H + H H + H H + H HH + H H 0.05 HH H + H H + H HH + HH HHH +*************************++-+-++-+-+-++-+-++-******************************- 0 0.5 0.52 0.54 0.56 0.58 0.6 0.62 0.64 0.66 Now let's compare it to RSA simulation with, 10000, random permutations of, 200 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.6025025000, 0.01622599875, -0.055001766519818147982, 2.9900082781419688782, -0.37164476793425396845, 14.456764007521673631] and a plot of the densitiy distribution is + HHHH + HHHH H 0.2 H HH + HH H + H H + H H 0.15 H H + HH H + H H + H H + H H 0.1 H H + HH H + H H + H H + H H 0.05 HH HH + HH H + HH HH + HHHHH HHHHHH +*********+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+-**********+ 0 0.58 0.59 0.6 0.61 0.62 0.63 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.040301516 and The ratio of the exact s.d (under the uniform distribution) and the s.d \ of RSA simulations is 1.077877076 ------------------------------------- This ends this article that took, 270.329, seconds to generate most of the time was spent by the RSA simulation -------------------------------------------------- Investigating Maximal words in {0,1} avoiding , 4, consecutive ones By Shalosh B. Ekhad Theorem: Let , A(c)(x), be the weight-enumerator of MAXIMAL words in {0,1} of length c, avoiding, 4, consecutive ones according to the weight x^NumberOfOnes (or equivalently, x^SumOfEntries) Then infinity ----- \ c ) A(c)(x) t = / ----- c = 0 9 6 7 5 5 4 5 3 4 3 3 3 3 2 2 2 t x + t x - t x + t x - 2 t x - t x + t x - t x - t x - 1 - ------------------------------------------------------------------------- 10 6 8 5 6 4 5 3 4 3 3 2 t x + t x - t x - 2 t x - t x - t x + 1 and in Maple notation -(t^9*x^6+t^7*x^5-t^5*x^4+t^5*x^3-2*t^4*x^3-t^3*x^3+t^3*x^2-t^2*x^2-t*x-1)/(t^ 10*x^6+t^8*x^5-t^6*x^4-2*t^5*x^3-t^4*x^3-t^3*x^2+1) It follows that the generating function for the total number is infinity ----- 9 7 4 2 \ c t + t - 2 t - t - t - 1 ) A(c)(1) t = - ---------------------------------- / 10 8 6 5 4 3 ----- t + t - t - 2 t - t - t + 1 c = 0 For the sake of the OEIS, the first, 30, terms are [1, 1, 1, 4, 4, 5, 7, 10, 16, 22, 29, 40, 60, 84, 118, 165, 230, 330, 466, 653, 919, 1297, 1831, 2585, 3640, 5124, 7233, 10201, 14380, 20272] ------------------------------------------------- First let us note that the EXACT limiting average density as the length of t\ he word goes to infinity is, 0.6686427921 Now let's specialize and look at the statistical distribution of words of le\ ngth, 200, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.6709173205, 0.01243557232, 0.050619375216441751295, 2.9794670821194173032, 0.49867612850197456674, 14.718246752785808366] Here is a plot of the distribution 0.25 H + HHH + H H + H H 0.2 H H + H H + H H + H H 0.15 H H + H H + H H + H H 0.1 H H + H H + H H + H H 0.05 H H + HH HH + HH H + H HHH +**************************+-+-+-+-+-++-+-+-+-+*****************************- 0 0.6 0.62 0.64 0.66 0.68 0.7 0.72 0.74 Now let's compare it to RSA simulation with, 10000, random permutations of, 200 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.6935190000, 0.01352932780, -0.019811406727605798427, 2.9851284746248391415, -0.12456903206806453882, 14.777897267126674114] and a plot of the densitiy distribution is + HHHH + HHHH H + H HH 0.2 H H + H H + H H + HH H 0.15 H H + H H + H HH + H H + H H 0.1 H H + H H + H H + HH H 0.05 H H + HH HH + HH HH + HHHH HHHH +*************-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+--+-+-+-+***********+ 0 0.67 0.68 0.69 0.7 0.71 0.72 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.033687727 and The ratio of the exact s.d (under the uniform distribution) and the s.d \ of RSA simulations is 1.087953771 ------------------------------------- This ends this article that took, 324.636, seconds to generate most of the time was spent by the RSA simulation -------------------------------------------------- Investigating Maximal words in {0,1} avoiding , 5, consecutive ones By Shalosh B. Ekhad Theorem: Let , A(c)(x), be the weight-enumerator of MAXIMAL words in {0,1} of length c, avoiding, 5, consecutive ones according to the weight x^NumberOfOnes (or equivalently, x^SumOfEntries) Then infinity ----- \ c 14 10 11 8 9 7 9 6 8 6 6 5 ) A(c)(x) t = - (t x - t x - 2 t x + t x - 2 t x + t x / ----- c = 0 6 4 5 4 4 4 4 3 3 3 3 2 2 2 - t x + 2 t x + t x - 2 t x + t x - t x + t x + t x + 1) / 15 10 12 8 10 7 9 6 7 5 6 4 5 4 / (t x - t x - 2 t x - 2 t x + t x + 2 t x + t x / 4 3 3 2 + t x + t x - 1) and in Maple notation -(t^14*x^10-t^11*x^8-2*t^9*x^7+t^9*x^6-2*t^8*x^6+t^6*x^5-t^6*x^4+2*t^5*x^4+t^4* x^4-2*t^4*x^3+t^3*x^3-t^3*x^2+t^2*x^2+t*x+1)/(t^15*x^10-t^12*x^8-2*t^10*x^7-2*t ^9*x^6+t^7*x^5+2*t^6*x^4+t^5*x^4+t^4*x^3+t^3*x^2-1) It follows that the generating function for the total number is infinity ----- 14 11 9 8 5 4 2 \ c t - t - t - 2 t + 2 t - t + t + t + 1 ) A(c)(1) t = - ------------------------------------------------------- / 15 12 10 9 7 6 5 4 3 ----- t - t - 2 t - 2 t + t + 2 t + t + t + t - 1 c = 0 For the sake of the OEIS, the first, 30, terms are [1, 1, 1, 1, 5, 5, 6, 8, 11, 15, 25, 35, 46, 61, 85, 125, 175, 245, 341, 470, 650, 925, 1300, 1810, 2521, 3520, 4915, 6880, 9640, 13476] ------------------------------------------------- First let us note that the EXACT limiting average density as the length of t\ he word goes to infinity is, 0.7269949175 Now let's specialize and look at the statistical distribution of words of le\ ngth, 200, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.7294654055, 0.01042349831, 0.059557053662145118440, 2.9785409727711029151, 0.58589393434487994462, 14.713734597721045268] Here is a plot of the distribution + H + H H 0.25 HH H + H H + H H 0.2 H H + H H + H H + H H 0.15 H H + H H + H H + H H 0.1 H H + H H + H H 0.05 H HH + H H + HH H + H H +************************+-+--+-+-+-+--+-+-+-+******************************- 0 0.68 0.7 0.72 0.74 0.76 0.78 0.8 Now let's compare it to RSA simulation with, 10000, random permutations of, 200 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7508205000, 0.01154885595, -0.010260835552940522940, 2.8908523818044917877, 0.026169464695242540974, 13.525093056970210843] and a plot of the densitiy distribution is 0.25 HH + HH HHH + HH HH + HH H 0.2 H H + H H + H H + H H 0.15 H H + H H + H H + H HH 0.1 H H + H H + H H + HH H 0.05 H HH + H H + HHHH HHH + HHH HHHH +********--+-+--+--+-+--+--+-+--+--+-+--+--+-+--+--+-+--+--+-+--************- 0 0.73 0.74 0.75 0.76 0.77 0.78 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.029274993 and The ratio of the exact s.d (under the uniform distribution) and the s.d \ of RSA simulations is 1.107963527 ------------------------------------- This ends this article that took, 362.589, seconds to generate most of the time was spent by the RSA simulation -------------------------------------------------- Investigating Maximal words in {0,1} avoiding , 6, consecutive ones By Shalosh B. Ekhad Theorem: Let , A(c)(x), be the weight-enumerator of MAXIMAL words in {0,1} of length c, avoiding, 6, consecutive ones according to the weight x^NumberOfOnes (or equivalently, x^SumOfEntries) Then infinity ----- \ c 20 15 17 13 14 11 14 10 13 10 ) A(c)(x) t = - (t x + t x - 2 t x + t x - 3 t x / ----- c = 0 11 9 11 8 10 8 8 7 8 6 7 6 7 5 - 2 t x + t x - 2 t x + t x - 2 t x + 2 t x - 2 t x 6 5 5 5 5 4 4 4 4 3 3 3 2 2 + 3 t x + t x - 2 t x + t x - t x + t x + t x + t x + 1) / 21 15 18 13 15 11 14 10 12 9 11 8 / (t x + t x - 2 t x - 3 t x - 2 t x - 2 t x / 9 7 8 6 7 5 6 5 5 4 4 3 + t x + 2 t x + 3 t x + t x + t x + t x - 1) and in Maple notation -(t^20*x^15+t^17*x^13-2*t^14*x^11+t^14*x^10-3*t^13*x^10-2*t^11*x^9+t^11*x^8-2*t ^10*x^8+t^8*x^7-2*t^8*x^6+2*t^7*x^6-2*t^7*x^5+3*t^6*x^5+t^5*x^5-2*t^5*x^4+t^4*x ^4-t^4*x^3+t^3*x^3+t^2*x^2+t*x+1)/(t^21*x^15+t^18*x^13-2*t^15*x^11-3*t^14*x^10-\ 2*t^12*x^9-2*t^11*x^8+t^9*x^7+2*t^8*x^6+3*t^7*x^5+t^6*x^5+t^5*x^4+t^4*x^3-1) It follows that the generating function for the total number is infinity ----- \ c ) A(c)(1) t = - ( / ----- c = 0 20 17 14 13 11 10 8 6 5 3 2 t + t - t - 3 t - t - 2 t - t + 3 t - t + t + t + t + 1) / 21 18 15 14 12 11 9 8 7 6 / (t + t - 2 t - 3 t - 2 t - 2 t + t + 2 t + 3 t + t / 5 4 + t + t - 1) For the sake of the OEIS, the first, 30, terms are [1, 1, 1, 1, 1, 6, 6, 7, 9, 12, 16, 21, 36, 51, 67, 87, 116, 161, 231, 321, 446, 616, 841, 1141, 1561, 2191, 3046, 4196, 5770, 7945] ------------------------------------------------- First let us note that the EXACT limiting average density as the length of t\ he word goes to infinity is, 0.7675902978 Now let's specialize and look at the statistical distribution of words of le\ ngth, 200, and look at the staistics of the densitiy The average, standard-deviation, and third through the, 6, scaled momenets are [0.7701918825, 0.008912901830, 0.068312212748513046191, 2.9775834478609307568, 0.67105201051906439166, 14.709914348993674527] Here is a plot of the distribution 0.3 H + HH + HH H 0.25 H H + H H + H H + H H 0.2 H H + H H + H H 0.15 H H + H H + H H 0.1 H H + HH H + H H + H H 0.05 H HH + H H + HHH HH +************************-+--+-+--+-+--+-+-+--+*****************************- 0 0.72 0.74 0.76 0.78 0.8 0.82 Now let's compare it to RSA simulation with, 10000, random permutations of, 200 The average, s.d., and first few scaled moments up to the, 6, are, for this particular simulation [0.7900625000, 0.01012171875, -0.021809007009705885769, 2.9356363974514871712, -0.38355206648798827554, 13.898055450093396803] and a plot of the densitiy distribution is + H + HH HH 0.25 HH HH + H H + HH HH + H H 0.2 H H + H HH + HH H + H H 0.15 H H + H H + H HH 0.1 HH H + H HH + HH H + H HH 0.05 HH H + HHH HHH + HHHH HHHH +*********--+--+--+-+--+--+--+--+--+--+--+--+--+--+--+--+-+--+--+--*********+ 0 0.77 0.78 0.79 0.8 0.81 The ratio of the exact average (under the uniform distribution) and the aver\ age of the RSA simulations is 1.025799568 and The ratio of the exact s.d (under the uniform distribution) and the s.d \ of RSA simulations is 1.135625517 ------------------------------------- This ends this article that took, 390.675, seconds to generate most of the time was spent by the RSA simulation --------------------------------------------------