Counting Words in the Alphabet {0,1}, That Avoid r consecutive Occurences o\ f the letter 1 According to Their Number of Good Neighbors for r from 2 \ 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 , 2, consecutive occurrences of the letter 1, and having m neig\ hbors (i.e. Hamming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | 2 2 2 \ | \ n m| x y - x y - x y - 1 ) | ) C(m, n) x y | = - ----------------------------- / | / | 3 2 3 2 ----- | ----- | x y - x y - x y - x y + 1 m = 0 \ n = 0 / and in Maple notation -(x^2*y^2-x^2*y-x*y-1)/(x^3*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\ 2 bors of a random word of length n tends to n times, -------------- 2 2 a + 3 a + 1 2 where a is the root of the polynomial, x + x - 1, and in decimals this is, 0.5527864048 -------------------------------------------------------------------------- "Theorem 2" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding , 3, consecutive occurrences of the letter 1, and having m neig\ hbors (i.e. Hamming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | \ | \ n m| ) | ) C(m, n) x y | = / | / | ----- | ----- | m = 0 \ n = 0 / 5 5 5 4 5 3 3 3 3 2 2 2 2 x y - 2 x y + x y + x y - x y - 2 x y + x y - x y - 1 - ------------------------------------------------------------------ 6 5 6 4 6 3 4 3 4 2 3 3 2 x y - 2 x y + x y + x y - x y - x y - x y - x y + 1 and in Maple notation -(x^5*y^5-2*x^5*y^4+x^5*y^3+x^3*y^3-x^3*y^2-2*x^2*y^2+x^2*y-x*y-1)/(x^6*y^5-2*x ^6*y^4+x^6*y^3+x^4*y^3-x^4*y^2-x^3*y^3-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, 2 (2 a + 1) ----------------------------- 2 2 (3 a + 2 a + 1) (a + a + 1) 3 2 where a is the root of the polynomial, x + x + x - 1, and in decimals this is, 0.7631601556 -------------------------------------------------------------------------- "Theorem 3" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding , 4, consecutive occurrences of the letter 1, and having m neig\ hbors (i.e. Hamming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | \ | \ n m| 9 9 9 8 9 7 9 6 ) | ) C(m, n) x y | = - (x y - 3 x y + 3 x y - x y / | / | ----- | ----- | m = 0 \ n = 0 / 7 7 7 6 7 5 5 5 5 4 5 3 4 4 4 3 - x y + 2 x y - x y - 2 x y + 3 x y - x y - 2 x y + 2 x y 3 3 3 2 2 2 / 10 9 10 8 10 7 + 2 x y - x y + x y + x y + 1) / (x y - 3 x y + 3 x y / 10 6 8 7 8 6 8 5 6 6 6 5 5 4 5 3 - x y - x y + 2 x y - x y - x y + x y - 2 x y + 2 x y 4 4 3 2 2 2 + x y + x y + x y + x y - 1) and in Maple notation -(x^9*y^9-3*x^9*y^8+3*x^9*y^7-x^9*y^6-x^7*y^7+2*x^7*y^6-x^7*y^5-2*x^5*y^5+3*x^5 *y^4-x^5*y^3-2*x^4*y^4+2*x^4*y^3+2*x^3*y^3-x^3*y^2+x^2*y^2+x*y+1)/(x^10*y^9-3*x ^10*y^8+3*x^10*y^7-x^10*y^6-x^8*y^7+2*x^8*y^6-x^8*y^5-x^6*y^6+x^6*y^5-2*x^5*y^4 +2*x^5*y^3+x^4*y^4+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, 2 2 (3 a + 2 a + 1) ------------------------------------------- 6 5 4 3 2 4 a + 7 a + 9 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.8673142246 -------------------------------------------------------------------------- "Theorem 4" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding , 5, consecutive occurrences of the letter 1, and having m neig\ hbors (i.e. Hamming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | \ | \ n m| 14 14 14 13 14 12 ) | ) C(m, n) x y | = - (x y - 4 x y + 6 x y / | / | ----- | ----- | m = 0 \ n = 0 / 14 11 14 10 11 11 11 10 11 9 11 8 9 9 - 4 x y + x y + x y - 3 x y + 3 x y - x y - 3 x y 9 8 9 7 8 8 9 6 8 7 8 6 6 6 + 7 x y - 5 x y - 2 x y + x y + 4 x y - 2 x y - 2 x y 6 5 6 4 5 5 5 4 4 4 4 3 3 3 + 3 x y - x y - 2 x y + 2 x y + 3 x y - 2 x y + 2 x y 3 2 2 2 / 15 14 15 13 15 12 - x y + x y + x y + 1) / (x y - 4 x y + 6 x y / 15 11 15 10 12 11 12 10 12 9 12 8 10 10 - 4 x y + x y + x y - 3 x y + 3 x y - x y - x y 10 9 10 8 10 7 9 8 9 7 9 6 7 7 7 6 + x y + x y - x y - 2 x y + 4 x y - 2 x y - x y + x y 6 5 6 4 5 5 5 4 4 4 3 2 2 2 - 2 x y + 2 x y + 2 x y - x y + x y + x y + x y + x y - 1) and in Maple notation -(x^14*y^14-4*x^14*y^13+6*x^14*y^12-4*x^14*y^11+x^14*y^10+x^11*y^11-3*x^11*y^10 +3*x^11*y^9-x^11*y^8-3*x^9*y^9+7*x^9*y^8-5*x^9*y^7-2*x^8*y^8+x^9*y^6+4*x^8*y^7-\ 2*x^8*y^6-2*x^6*y^6+3*x^6*y^5-x^6*y^4-2*x^5*y^5+2*x^5*y^4+3*x^4*y^4-2*x^4*y^3+2 *x^3*y^3-x^3*y^2+x^2*y^2+x*y+1)/(x^15*y^14-4*x^15*y^13+6*x^15*y^12-4*x^15*y^11+ x^15*y^10+x^12*y^11-3*x^12*y^10+3*x^12*y^9-x^12*y^8-x^10*y^10+x^10*y^9+x^10*y^8 -x^10*y^7-2*x^9*y^8+4*x^9*y^7-2*x^9*y^6-x^7*y^7+x^7*y^6-2*x^6*y^5+2*x^6*y^4+2*x ^5*y^5-x^5*y^4+x^4*y^4+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, 3 2 2 (4 a + 3 a + 2 a + 1) ----------------------------------------------------- 4 3 2 4 3 2 (5 a + 4 a + 3 a + 2 a + 1) (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.9241477666 -------------------------------------------------------------------------- "Theorem 5" Let C(m,n) be the number of words of length n in the alphabet, {0, 1}, avoiding , 6, consecutive occurrences of the letter 1, and having m neig\ hbors (i.e. Hamming distance 1) that also obey this property, then infinity /infinity \ ----- | ----- | \ | \ n m| 20 20 20 19 20 18 ) | ) C(m, n) x y | = - (x y - 5 x y + 10 x y / | / | ----- | ----- | m = 0 \ n = 0 / 20 17 20 16 20 15 17 17 17 16 17 15 - 10 x y + 5 x y - x y - x y + 4 x y - 6 x y 17 14 17 13 14 14 14 13 14 12 13 13 + 4 x y - x y - 3 x y + 10 x y - 12 x y - 3 x y 14 11 13 12 14 10 13 11 13 10 11 11 + 6 x y + 9 x y - x y - 9 x y + 3 x y + 3 x y 11 10 11 9 10 10 11 8 10 9 10 8 - 7 x y + 5 x y + 2 x y - x y - 4 x y + 2 x y 8 8 8 7 8 6 7 7 7 6 7 5 6 6 + 3 x y - 5 x y + 2 x y + 4 x y - 6 x y + 2 x y + 3 x y 6 5 5 5 5 4 4 4 4 3 3 3 2 2 - 3 x y - 3 x y + 2 x y - 2 x y + x y - x y - x y - x y - 1) / 21 20 21 19 21 18 21 17 21 16 21 15 / (x y - 5 x y + 10 x y - 10 x y + 5 x y - x y / 18 17 18 16 18 15 18 14 18 13 15 15 - x y + 4 x y - 6 x y + 4 x y - x y - x y 15 14 15 12 14 13 15 11 14 12 14 11 + 2 x y - 2 x y - 3 x y + x y + 9 x y - 9 x y 14 10 12 12 12 11 12 10 12 9 11 10 11 9 + 3 x y + x y - x y - x y + x y + 2 x y - 4 x y 11 8 9 9 9 8 9 7 8 8 8 7 7 6 + 2 x y + 2 x y - 3 x y + x y + 2 x y - 2 x y + 3 x y 7 5 6 6 6 5 5 5 4 3 3 3 2 2 - 3 x y - 2 x y + x y - x y - x y - x y - x y - x y + 1) and in Maple notation -(x^20*y^20-5*x^20*y^19+10*x^20*y^18-10*x^20*y^17+5*x^20*y^16-x^20*y^15-x^17*y^ 17+4*x^17*y^16-6*x^17*y^15+4*x^17*y^14-x^17*y^13-3*x^14*y^14+10*x^14*y^13-12*x^ 14*y^12-3*x^13*y^13+6*x^14*y^11+9*x^13*y^12-x^14*y^10-9*x^13*y^11+3*x^13*y^10+3 *x^11*y^11-7*x^11*y^10+5*x^11*y^9+2*x^10*y^10-x^11*y^8-4*x^10*y^9+2*x^10*y^8+3* x^8*y^8-5*x^8*y^7+2*x^8*y^6+4*x^7*y^7-6*x^7*y^6+2*x^7*y^5+3*x^6*y^6-3*x^6*y^5-3 *x^5*y^5+2*x^5*y^4-2*x^4*y^4+x^4*y^3-x^3*y^3-x^2*y^2-x*y-1)/(x^21*y^20-5*x^21*y ^19+10*x^21*y^18-10*x^21*y^17+5*x^21*y^16-x^21*y^15-x^18*y^17+4*x^18*y^16-6*x^ 18*y^15+4*x^18*y^14-x^18*y^13-x^15*y^15+2*x^15*y^14-2*x^15*y^12-3*x^14*y^13+x^ 15*y^11+9*x^14*y^12-9*x^14*y^11+3*x^14*y^10+x^12*y^12-x^12*y^11-x^12*y^10+x^12* y^9+2*x^11*y^10-4*x^11*y^9+2*x^11*y^8+2*x^9*y^9-3*x^9*y^8+x^9*y^7+2*x^8*y^8-2*x ^8*y^7+3*x^7*y^6-3*x^7*y^5-2*x^6*y^6+x^6*y^5-x^5*y^5-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, 4 3 2 2 (5 a + 4 a + 3 a + 2 a + 1) ----------------------------------------------------------------- 5 4 3 2 5 4 3 2 (6 a + 5 a + 4 a + 3 a + 2 a + 1) (a + a + a + a + a + 1) 6 5 4 3 2 where a is the root of the polynomial, x + x + x + x + x + x - 1, and in decimals this is, 0.9564550110 ---------------------------------- This ends this paper that took, 12.065, seconds to produce