# Counting strings of $\{ 0,1 \}$'s of length $n$ s.t. last $k$ bits are equal

I'm trying to derive a closed formula for the number of strings of $0$'s and $1$'s of length $n$ such that the last $k \leq n$ bits are all zeros or all ones, and such that there is no other place in the string with $k$ consecutive zeros or ones.

I have tried constructing a recursive formula by "reasoning backward", but the formula is still a mystery.

• When you say no other place in the string, does this include places that overlap the last $k$? In other words, are you excluding strings $b_1\dots b_n$ that end in $k+1$ ones, since $b_{n-k}\dots b_{n-1}$ is a second string of $k$ ones? – Brian M. Scott May 30 '13 at 5:18
• @BrianM.Scott Yes, I am excluding those strings. I do not want $k$ consecutive bits to appear anywhere along the string but at the "end." – Peter May 30 '13 at 5:33
• Okay: then the question is equivalent to asking how many strings of length $n-k$ do not contain any string of $k$ consecutive zeros or ones. Half of them will end in $0$ and require appending $1^k$, and the other half will end in $1$ and require appending $0^k$. – Brian M. Scott May 30 '13 at 5:35

The question is equivalent to asking how many strings of length $n-k$ do not contain any string of $k$ consecutive zeros or ones. Half of these will end in $0$ and require appending $1^k$ to make the desired string of length $n$, and the other half will end in $1$ and require appending $0^k$. Thus, it suffices to find $f(m,k)$, the number of strings of length $m$ that do not contain any string of $k$ consecutive zeros or ones.

Such a string can be thought of as a composition of $m$ into parts of size less than $k$, the parts being the blocks of consecutive zeros or consecutive ones. Each composition is represented twice, however, once with a string starting with a block of zeros and once with a string starting with a block of ones. E.g., the composition $3+1+2$ of $6$ is represented by $000100$ and by $111011$. Thus, $f(m,k)$ is the twice the number of compositions of $m$ into parts of size less than $k$.

If define the $\ell$-nacci numbers $a_i^{(\ell)}$ by $a_0^{(\ell)}=a_1^{(\ell)}=\ldots=a_{\ell-2}^{(\ell)}0$, $a_{\ell-1}^{(\ell)}=1$, and

$$a_i^{(\ell)}=a_{i-1}^{(\ell)}+\ldots+a_{i-\ell}^{(\ell)}\tag{1}$$

for $i\ge\ell$, it turns out that $f(m,k)=2a_{m+k-2}^{(k-1)}$, which is easily computed from the recurrence $(1)$.

When $k=2$, for instance, $a_i^{(1)}=1$ for all $i$, and $f(m,2)=2$: the only acceptable sequences are the two alternating sequences of length $m$. When $k=3$, $a_i^{(2)}=F_i$, the $i$-th Fibonacci number, and $f(m,3)=2F_{m+1}$; in this case Binet’s formula gives a closed form, and OEIS A000073 has a really ugly closed form for the $k=4$ case, but for $k>4$ there’s nothing much better than generating functions.

For more information and references see OEIS A048887 and its references; the specific case $k=5$ is OEIS A000078.

A nice solution to this kind of problems is given by Odlyzko "Enumeration of Strings" (in Apostolico and Galil, "Combinatorial Algorithms on Words", Springer, 1985). He derives simple formulas the generating functions. Except for $k = 2$ the formulas for the coefficients are complex.