Counting Words in the Alphabet {0,1}, That Avoid r consecutive Occurences o\ f the same letter, According to Their Number of Good Neighbors for r fro\ m 3 to, 6 By Shalosh B. Ekhad "Theorem 1" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding strings of, 3, consecutive occurrences of the same letter (i.e. you are not allowed to have consecutive substrings in the set, {[0, 0, 0], [1, 1, 1]}, and having\ m neighbors (i.e. Hamming distance 1) that also obey this property, the\ n infinity /infinity \ ----- | ----- | \ | \ n m| 5 4 5 3 5 2 4 3 ) | ) C(m, n) x y | = (2 x y - 4 x y + 2 x y - 2 x y / | / | ----- | ----- | m = 0 \ n = 0 / 4 2 4 3 2 3 2 2 3 2 2 + 4 x y - 2 x y - x y + 2 x y - 4 x y - x + 2 x y + x - 2 x y / 3 2 3 2 + x - 1) / (x y - x + x + x - 1) / and in Maple notation (2*x^5*y^4-4*x^5*y^3+2*x^5*y^2-2*x^4*y^3+4*x^4*y^2-2*x^4*y-x^3*y^2+2*x^3*y-4*x^ 2*y^2-x^3+2*x^2*y+x^2-2*x*y+x-1)/(x^3*y^2-x^3+x^2+x-1) As the length of the word goes to infinity, the average number of good neigh\ bors of a random word of length n tends to n times, 4 3 2 2 (a - 2 a - 3 a + 2 a + 1) ------------------------------ 3 2 2 a + 3 a + 3 a + 1 2 where a is the root of the polynomial, x + x - 1, and in decimals this is, 0.3416407884 "Theorem 2" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding strings of, 4, consecutive occurrences of the same letter (i.e. you are not allowed to have consecutive substrings in the set, {[0, 0, 0, 0], [1, 1, 1, 1]}, and \ having m neighbors (i.e. Hamming distance 1) that also obey this propert\ y, then infinity /infinity \ ----- | ----- | \ | \ n m| 7 6 7 5 7 4 6 5 ) | ) C(m, n) x y | = - (2 x y - 4 x y + 2 x y - 2 x y / | / | ----- | ----- | m = 0 \ n = 0 / 6 4 6 3 5 4 5 3 4 4 5 2 4 3 4 2 + 4 x y - 2 x y - x y + 2 x y + 2 x y - x y - 3 x y + x y 3 3 3 2 3 2 2 2 / - 4 x y + 2 x y + x y - 2 x y + x y - x y - 1) / ( / 5 4 5 3 5 2 4 3 4 2 3 2 x y - 2 x y + x y - x y + x y - x y - x y - x y + 1) and in Maple notation -(2*x^7*y^6-4*x^7*y^5+2*x^7*y^4-2*x^6*y^5+4*x^6*y^4-2*x^6*y^3-x^5*y^4+2*x^5*y^3 +2*x^4*y^4-x^5*y^2-3*x^4*y^3+x^4*y^2-4*x^3*y^3+2*x^3*y^2+x^3*y-2*x^2*y^2+x^2*y- x*y-1)/(x^5*y^4-2*x^5*y^3+x^5*y^2-x^4*y^3+x^4*y^2-x^3*y-x^2*y-x*y+1) As the length of the word goes to infinity, the average number of good neigh\ bors of a random word of length n tends to n times, 6 5 4 3 2 2 (a - 2 a - 3 a - 4 a + 3 a + 2 a + 1) -------------------------------------------- 5 4 3 2 3 a + 5 a + 6 a + 6 a + 3 a + 1 3 2 where a is the root of the polynomial, x + x + x - 1, and in decimals this is, 0.6724562346 "Theorem 3" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding strings of, 5, consecutive occurrences of the same letter (i.e. you are not allowed to have consecutive substrings in the set, {[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]}, and having m neighbors (i.e. Hamming distance 1) that also obey this pro\ perty, then infinity /infinity \ ----- | ----- | \ | \ n m| 14 13 14 12 14 11 ) | ) C(m, n) x y | = - (2 x y - 8 x y + 12 x y / | / | ----- | ----- | m = 0 \ n = 0 / 13 12 14 10 13 11 14 9 13 10 12 11 - 2 x y - 8 x y + 8 x y + 2 x y - 12 x y - x y 13 9 12 10 11 11 13 8 12 9 11 10 + 8 x y + 4 x y + 2 x y - 2 x y - 6 x y - 6 x y 12 8 11 9 12 7 11 8 10 9 10 8 9 9 + 4 x y + 6 x y - x y - 2 x y - 2 x y + 6 x y - 2 x y 10 7 9 8 10 6 9 7 8 8 9 6 8 7 - 6 x y + 2 x y + 2 x y + 3 x y - 2 x y - 4 x y + 7 x y 9 5 8 6 7 7 8 5 7 6 7 5 6 6 7 4 + x y - 8 x y - x y + 3 x y + 3 x y - 3 x y - 4 x y + x y 6 5 6 4 5 5 5 4 5 3 4 4 4 3 + 7 x y - 3 x y - 4 x y + 6 x y - 2 x y + 4 x y - 2 x y 4 2 3 3 3 2 2 2 / 12 11 12 10 - x y + 2 x y - x y + x y + x y + 1) / (x y - 4 x y / 12 9 12 8 12 7 9 7 9 6 8 7 9 5 8 6 + 6 x y - 4 x y + x y - x y + 2 x y - x y - x y + 2 x y 7 7 8 5 7 6 7 5 7 4 6 5 6 4 4 2 3 2 - x y - x y + x y + x y - x y - x y + x y + x y + x y 2 2 + x y + x y - 1) and in Maple notation -(2*x^14*y^13-8*x^14*y^12+12*x^14*y^11-2*x^13*y^12-8*x^14*y^10+8*x^13*y^11+2*x^ 14*y^9-12*x^13*y^10-x^12*y^11+8*x^13*y^9+4*x^12*y^10+2*x^11*y^11-2*x^13*y^8-6*x ^12*y^9-6*x^11*y^10+4*x^12*y^8+6*x^11*y^9-x^12*y^7-2*x^11*y^8-2*x^10*y^9+6*x^10 *y^8-2*x^9*y^9-6*x^10*y^7+2*x^9*y^8+2*x^10*y^6+3*x^9*y^7-2*x^8*y^8-4*x^9*y^6+7* x^8*y^7+x^9*y^5-8*x^8*y^6-x^7*y^7+3*x^8*y^5+3*x^7*y^6-3*x^7*y^5-4*x^6*y^6+x^7*y ^4+7*x^6*y^5-3*x^6*y^4-4*x^5*y^5+6*x^5*y^4-2*x^5*y^3+4*x^4*y^4-2*x^4*y^3-x^4*y^ 2+2*x^3*y^3-x^3*y^2+x^2*y^2+x*y+1)/(x^12*y^11-4*x^12*y^10+6*x^12*y^9-4*x^12*y^8 +x^12*y^7-x^9*y^7+2*x^9*y^6-x^8*y^7-x^9*y^5+2*x^8*y^6-x^7*y^7-x^8*y^5+x^7*y^6+x ^7*y^5-x^7*y^4-x^6*y^5+x^6*y^4+x^4*y^2+x^3*y^2+x^2*y^2+x*y-1) As the length of the word goes to infinity, the average number of good neigh\ bors of a random word of length n tends to n times, 8 7 6 5 4 3 2 2 (a - 2 a - 3 a - 4 a - 5 a + 4 a + 3 a + 2 a + 1) ---------------------------------------------------------- 7 6 5 4 3 2 4 a + 7 a + 9 a + 10 a + 10 a + 6 a + 3 a + 1 4 3 2 where a is the root of the polynomial, x + x + x + x - 1, and in decimals this is, 0.8278311802 "Theorem 4" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding strings of, 6, consecutive occurrences of the same letter (i.e. you are not allowed to have consecutive substrings in the set, {[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]}, and having m neighbors (i.e. Ha\ mming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | \ | \ n m| 20 19 20 18 20 17 ) | ) C(m, n) x y | = - (2 x y - 10 x y + 20 x y / | / | ----- | ----- | m = 0 \ n = 0 / 19 18 20 16 19 17 20 15 19 16 18 17 - 2 x y - 20 x y + 10 x y + 10 x y - 20 x y - x y 20 14 19 15 18 16 17 17 19 14 18 15 - 2 x y + 20 x y + 5 x y + 2 x y - 10 x y - 10 x y 17 16 19 13 18 14 17 15 18 13 - 12 x y + 2 x y + 10 x y + 28 x y - 5 x y 17 14 16 15 18 12 17 13 16 14 17 12 - 32 x y + 2 x y + x y + 18 x y - 8 x y - 4 x y 16 13 15 14 16 12 15 13 14 14 16 11 + 12 x y + x y - 8 x y - 4 x y - 4 x y + 2 x y 15 12 14 13 15 11 14 12 13 13 15 10 + 6 x y + 13 x y - 4 x y - 15 x y - 4 x y + x y 14 11 13 12 14 10 13 11 12 12 13 10 + 7 x y + 15 x y - x y - 21 x y - x y + 13 x y 12 11 13 9 12 10 12 9 11 10 12 8 + 6 x y - 3 x y - 12 x y + 10 x y + 4 x y - 3 x y 11 9 10 10 11 8 10 9 11 7 10 8 9 9 - 9 x y + 2 x y + 6 x y - 7 x y - x y + 8 x y + x y 10 7 9 8 9 7 8 8 9 6 8 7 8 6 - 3 x y - 3 x y + 3 x y + 5 x y - x y - 9 x y + 4 x y 7 7 7 6 7 5 6 6 6 5 6 4 5 5 + 6 x y - 10 x y + 4 x y + 5 x y - 7 x y + 2 x y - 4 x y 5 4 5 3 4 4 4 3 3 3 2 2 / + 2 x y + x y - 2 x y + x y - x y - x y - x y - 1) / ( / 18 17 18 16 18 15 18 14 18 13 18 12 x y - 5 x y + 10 x y - 10 x y + 5 x y - x y 15 14 15 13 15 12 14 13 15 11 14 12 - x y + 4 x y - 6 x y - x y + 4 x y + 3 x y 15 10 14 11 13 12 14 10 13 11 12 12 - x y - 3 x y - x y + x y + 3 x y - x y 13 10 12 11 13 9 12 9 12 8 11 9 11 8 - 3 x y + 2 x y + x y - 2 x y + x y + x y - 2 x y 10 9 11 7 10 8 9 9 10 7 9 8 9 7 8 8 + x y + x y - 2 x y + x y + x y - x y - x y + x y 9 6 8 7 7 6 7 5 6 6 6 5 5 3 4 3 + x y - x y + 2 x y - 2 x y + x y - x y - x y - x y 3 3 2 2 - x y - x y - x y + 1) and in Maple notation -(2*x^20*y^19-10*x^20*y^18+20*x^20*y^17-2*x^19*y^18-20*x^20*y^16+10*x^19*y^17+ 10*x^20*y^15-20*x^19*y^16-x^18*y^17-2*x^20*y^14+20*x^19*y^15+5*x^18*y^16+2*x^17 *y^17-10*x^19*y^14-10*x^18*y^15-12*x^17*y^16+2*x^19*y^13+10*x^18*y^14+28*x^17*y ^15-5*x^18*y^13-32*x^17*y^14+2*x^16*y^15+x^18*y^12+18*x^17*y^13-8*x^16*y^14-4*x ^17*y^12+12*x^16*y^13+x^15*y^14-8*x^16*y^12-4*x^15*y^13-4*x^14*y^14+2*x^16*y^11 +6*x^15*y^12+13*x^14*y^13-4*x^15*y^11-15*x^14*y^12-4*x^13*y^13+x^15*y^10+7*x^14 *y^11+15*x^13*y^12-x^14*y^10-21*x^13*y^11-x^12*y^12+13*x^13*y^10+6*x^12*y^11-3* x^13*y^9-12*x^12*y^10+10*x^12*y^9+4*x^11*y^10-3*x^12*y^8-9*x^11*y^9+2*x^10*y^10 +6*x^11*y^8-7*x^10*y^9-x^11*y^7+8*x^10*y^8+x^9*y^9-3*x^10*y^7-3*x^9*y^8+3*x^9*y ^7+5*x^8*y^8-x^9*y^6-9*x^8*y^7+4*x^8*y^6+6*x^7*y^7-10*x^7*y^6+4*x^7*y^5+5*x^6*y ^6-7*x^6*y^5+2*x^6*y^4-4*x^5*y^5+2*x^5*y^4+x^5*y^3-2*x^4*y^4+x^4*y^3-x^3*y^3-x^ 2*y^2-x*y-1)/(x^18*y^17-5*x^18*y^16+10*x^18*y^15-10*x^18*y^14+5*x^18*y^13-x^18* y^12-x^15*y^14+4*x^15*y^13-6*x^15*y^12-x^14*y^13+4*x^15*y^11+3*x^14*y^12-x^15*y ^10-3*x^14*y^11-x^13*y^12+x^14*y^10+3*x^13*y^11-x^12*y^12-3*x^13*y^10+2*x^12*y^ 11+x^13*y^9-2*x^12*y^9+x^12*y^8+x^11*y^9-2*x^11*y^8+x^10*y^9+x^11*y^7-2*x^10*y^ 8+x^9*y^9+x^10*y^7-x^9*y^8-x^9*y^7+x^8*y^8+x^9*y^6-x^8*y^7+2*x^7*y^6-2*x^7*y^5+ x^6*y^6-x^6*y^5-x^5*y^3-x^4*y^3-x^3*y^3-x^2*y^2-x*y+1) As the length of the word goes to infinity, the average number of good neigh\ bors of a random word of length n tends to n times, 10 9 8 7 6 5 4 3 2 2 (a - 2 a - 3 a - 4 a - 5 a - 6 a + 5 a + 4 a + 3 a + 2 a + 1) ------------------------------------------------------------------------- 4 3 2 5 4 3 2 (5 a + 4 a + 3 a + 2 a + 1) (a + a + a + a + a + 1) 5 4 3 2 where a is the root of the polynomial, x + x + x + x + x - 1, and in decimals this is, 0.9061477040 ---------------------------------- This ends this paper that took, 12.823, seconds to produce