How to find the amount of binary sequences with at least one "0" in the middle of 2 "1"?

Question

This is a sub problem that I found while trying to solve one question from the programming marathon (please don't give me the direct solution for that. I am having fun solving these sub problems)

If you have a binary sequence with $n$ digits: $\underbrace{1101\ldots}_ n$.

How to find the amount of sequences that have at least a "$0$" in the middle of 2 "$1$". For example for $n=4$:
$0101$
$1010$
$1001$
$1011$
$1101$

5 sequences.

So far my most successful attempt was considering it as a $n$-gon without one of the sides. Getting its non-adjacent links between vertices and then getting the permutations of the blanks vertices between the selected vertices.

It gave me a sequence like this:

for $n \ge 3$

$(n-2)(2^1-1) + (n-3)(2^2-1) + \ldots + (n-(n-1))(2^{n-2}-1)$

for $n = 3$

$(3-2)(2-1) = 1\cdot 1 = 1$

for $n = 4$

$(4-2)(2-1) + (4-3)(4-1) = 2 + 3 = 5$

for $n = 5$

$(5-2)(2-1) + (5-3)(4-1) + (5-4)(8-1) = 3 + 6 + 7 = 16$

It looks correct, but I haven't tested it for $n$ bigger than 5, because that is too much to do by hand. I will try running this on a PC.

Answer 1

The formula $$\sum_{k=2}^{n-1} (n-k)(2^{k-1}-1) = (n-2)(2^1-1) + (n-3)(2^2-1) + \dots + (1)(2^n-1)$$ is correct, but it can be simplified. This is a bit of an adventure, since when we expand out the sum, it has three parts:

• The sum of $n2^{k-1}$ simplifies to $n 2^{n-1} - 2n$; it is the sum of a finite geometric series.
• The sum of $k 2^{k-1}$ simplifies to $n 2^{n-1} - 2^n$, which is easy enough to check by induction. To find this sum, the easiest method I know is to start from $\sum_{k=2}^{n-1} x^k = \frac{x^n-x^2}{x-1}$, take the derivative to get $\sum_{k=2}^{n-1} k x^{k-1}$, and then evaluate at $x=2$.
• The sum of $n-k$ as $k$ goes from $2$ to $n-1$ is equal to the sum of $j =n-k$ as $j$ goes from $1$ to $n-2$, which is $\frac12 (n-1)(n-2)$.

Putting these together with the appropriate signs, we get the expression $2^n - \frac{n(n+1)}{2} - 1$, which seems like it ought to have a simpler explanation.

And it does! The idea is that we start with all $2^n$ binary sequences, and then exclude:

1. The $\binom{n+1}{2}$ sequences consisting of a possibly-empty block of $0$'s, followed by a nonempty block of $1$'s, followed by a possibly-empty block of $0$'s. We can specify such a sequence by a pair $(i,j)$ where $0 \le i < j \le n$: $i$ indicates the last position of the first block of $0$'s (or $0$ if that block is empty), and $j$ indicates the last position of the block of $1$'s. There are $\binom{n+1}{2}$ ways to choose $i$ and $j$ from $\{0,1,\dots,n\}$.
2. The single sequence $000\dots00$.

If we exclude these, then we're left with sequences that contain some $1$'s, and the $1$'s are not all in a consecutive block. This means that some of the $1$'s are separated by $0$'s, which is exactly what we were looking for.