Có bao nhiêu xâu nhị phân độ dài bằng 8 và không chứa 6 số 0 liên tiếp.

Gọi $a_n$ là số xâu nhị phân độ dài $n$ không chứa 6 số 0 liên tiếp. Ta có thể xây dựng xâu nhị phân độ dài $n$ bằng cách thêm một bit (0 hoặc 1) vào xâu nhị phân độ dài $n-1$. Nếu xâu độ dài $n-1$ kết thúc bằng 1, ta có thể thêm 0 hoặc 1 vào cuối. Nếu xâu độ dài $n-1$ kết thúc bằng 0, ta cần xem xét số lượng số 0 liên tiếp ở cuối xâu. Ta gọi $a_{n, k}$ là số xâu nhị phân độ dài $n$ kết thúc bằng $k$ số 0 liên tiếp và không chứa 6 số 0 liên tiếp. Khi đó $a_n = a_{n, 0} + a_{n, 1} + a_{n, 2} + a_{n, 3} + a_{n, 4} + a_{n, 5}$. Ta có công thức truy hồi: $a_{n, 0} = a_{n-1}$ (xâu độ dài $n-1$ cộng thêm 1 vào cuối) $a_{n, 1} = a_{n-1, 0}$ (xâu độ dài $n-1$ kết thúc bằng 0, cộng thêm 0 vào cuối) $a_{n, 2} = a_{n-1, 1}$ (xâu độ dài $n-1$ kết thúc bằng 1 số 0, cộng thêm 0 vào cuối) $a_{n, 3} = a_{n-1, 2}$ (xâu độ dài $n-1$ kết thúc bằng 2 số 0, cộng thêm 0 vào cuối) $a_{n, 4} = a_{n-1, 3}$ (xâu độ dài $n-1$ kết thúc bằng 3 số 0, cộng thêm 0 vào cuối) $a_{n, 5} = a_{n-1, 4}$ (xâu độ dài $n-1$ kết thúc bằng 4 số 0, cộng thêm 0 vào cuối) Tuy nhiên, cách này phức tạp. Ta sẽ tính số xâu nhị phân độ dài 8 chứa 6 số 0 liên tiếp trở lên. Sau đó lấy tổng số xâu nhị phân độ dài 8 trừ đi số xâu vừa tìm được. Tổng số xâu nhị phân độ dài 8 là $2^8 = 256$. Các xâu chứa 6 số 0 liên tiếp: - 000000xx: xx có 4 khả năng (00, 01, 10, 11) - 1000000x: x có 2 khả năng (0, 1) - x1000000: x có 2 khả năng (0, 1) - 00000000: 1 trường hợp - 0000001x: x có 2 khả năng - x0000001: x có 2 khả năng - 11000000 - 01000000 - 00000001 -10000001 Các xâu chứa 7 số 0 liên tiếp: - 0000000x : x có 2 khả năng - x0000000 : x có 2 khả năng - 00000000 : 1 Các xâu chứa 8 số 0 liên tiếp: - 00000000 : 1 Các xâu chứa 6 số 0 liên tiếp: 00000000, 00000001, 10000000, 01000000, 11000000, 00000010, 00000011, 10000001 Các xâu chứa 7 số 0 liên tiếp: 00000000, 10000000, 00000001 Các xâu chứa 8 số 0 liên tiếp: 00000000 Số xâu có ít nhất 6 số 0 liên tiếp là: 4 + 2 + 2 -1 +1 = 8 Các xâu có 6 số 0 liên tiếp: 00000011, 00000010, 10000001, 01000000, 11000000, 00000100, 00000000 Các xâu có 7 số 0 liên tiếp: 10000000, 00000001, Các xâu có 8 số 0 liên tiếp: 00000000 Số các xâu chứa 6 số 0 liên tiếp trở lên là: 3+2+2-1 = 7, 6+7+8 = 8+2+2+4-1 = 15 Số xâu chứa ít nhất 6 số 0 liên tiếp là: 8. Vậy số xâu nhị phân độ dài 8 không chứa 6 số 0 liên tiếp là: 256 - 8 = 248 Tổng số các xâu có ít nhất 6 số 0 liên tiếp: 00000000 00000001 00000010 00000011 10000000 01000000 10000001 11000000 Tổng cộng có 8 xâu. Vậy, có 256 - 8 = 248 xâu không chứa 6 số 0 liên tiếp.