# How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same.

Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, 010, 011, 100$)

I am trying to get a recurrent formula of this problem but I don't know how to.

• why (000) and (111) aren't in there? – Exodd Sep 28 '14 at 9:18
• Because k consecutive characters must no be the same. In the example, k equal 3. – Xeing Sep 28 '14 at 11:07

## 1 Answer

Let $T(n, k)$ represent the number of strings with k consecutive characters that are the same. We assume that a character can only hold either $0$ or $1$ just by going your example.

$T(n, n) = 2*1$ since there's only one string that has n consecutive characters for each character and we have 2 such characters.

$T(n, n-1)$ includes $T(n,n)$ as the strings counted by the latter already have $n-1$ consecutive identical characters. What remains is for us to find strings that have exactly $n-1$ consecutive characters which is given by $2 * (n - (n-1) + 1)$. Therefore:

$$T(n, n-1) = T(n,n) + 2 * (n- (n-1) + 1)$$

In general, we can count the number of strings with exactly k consecutive identical characters by $2 * (n - k + 1)$ where the $2$ factor comes from the # of characters possible ($0$ or $1$) and the $(n - k + 1)$ factor comes from the possible ways for a character to appear exactly k consecutively.

To find $T(n, k)$, we simply add up the possible strings that has exactly k consecutive identical characters, then the strings that has more than k consecutive exact characters given by $%T(n, k+1)$:

$$T(n, k) = 2 * (n - k + 1) + T(n, k + 1)$$

Therefore, the number of strings that do not have k consecutive identical characters in recurrence form is:

$$2^n - T(n,k) = 2^n - 2*(n-k+1) - T(n, k+1)$$

where $2^n$ is the total number of strings possible of n length and 2 characters.