Number of ways to break up consecutive series of $1$s in binary number

Question

There is a binary number of length $N$ which consists of a consecutive series of 1s. For example, if $N=5$ the number is $11111$. How many ways are there to intervene on this number (i.e., replacing $1$s with $0$s) such that the series of $1$s is interrupted?

For clarity, the numbers $11101$, $11010$ and $10101$ are valid interventions but $11110$ and $01110$ are not, since the series of $1$s are not interrupted in the latter cases.

It is quite easy for the cases where the endpoint numbers are 1 (i.e. the first and the last bit of the binary number is $1$, such as $1XXX1$). These cases, I believe, sum up to $2^{N-2} - 1$, where the subtraction accounts for the case when all the numbers are $1$s.

However, I am unsure how to solve this for the cases where the endpoint numbers need not both be $1$s, such as $10110$.

Answer 1

Degenerate sequences consisting of a single 1 are also allowed.

All of the analysis below assumes that such degenerate sequences have been disallowed. Given the stipulation above, the adjustment is simply to add $(n)$ to the computation below.

This is because there are clearly $n$ such degenerate sequences that I originally disallowed.

---

Given any set $E$ with a finite number of elements, let $|E|$ denote the number of elements in the set $E$.

Let $S$ denote the set of all $n$ binary digit strings that are not all 0's.

Under the assumption that the string of $n$ 1's, when converted, can not be all 0's, after the conversion, then the set $S$ represents the possible results of this conversion.

Let $T$ denote the subset of $S$ where all of the 1's are in a single clump.

Then, the desired computation is

$$|S| - |T|,$$

where $~\displaystyle |S| = \left(2^n\right) - 1.$
This computation accommodates that you are not allowed to have the converted number be all 0's.

---

Any element in the subset $T$ will have the following characteristics:

• It will contain a single clump of 1's that will have a length of between $1$ and $n$ digits. Here, I am assuming that if the converted number is all 1's, that that number is considered unsatisfactory (i.e. that the number belongs in the set $T$).

• If the clump of numbers has length $k$,
  where $k \in \{1,2,\cdots,n\}$,
  then the starting position for this clump will be
  some element in $\{1,2,\cdots (n+1-k)\}.$

• For the element in $T$, besides the clump of 1's,
  every other digit is a 0.

---

So, each element in $T$ is uniquely identified by two characteristics:

• $A = $ the length of the clump
• $B = $ the starting position of the clump.

For $A \in \{1,2,\cdots,n\}$,

$B$ will range from $\{1,2,\cdots,(n+1-A)\}.$

Therefore

$$|T| = \sum_{A = 1}^n (n+1 - A) = \left[(n+1)\sum_{A=1}^n (1) \right] - \left[\sum_{A=1}^n A\right]. \tag1 $$

In computing the two terms in (1) above,
the first term is $(n+1)\times n$,
while the second term is $~\displaystyle \frac{n(n+1)}{2}.$

So,

$$|T| = n(n+1) - \left[\frac{n(n+1)}{2}\right] = \frac{n(n+1)}{2}.$$

Therefore,

$$|S| - |T| = \left(2^n\right) - 1 - \frac{n(n+1)}{2}.$$

Answer 2

Easier to count cases that we are not interested in. (I.e., sequences with at most $1$ uninterrupted block of $1$s.)

There is one sequence of all $0$s.

There are $n$ sequences with a single $1$ in the uninterrupted block.

There are ${n}\choose{2}$ sequences with a single uninterrupted block of length two or more (choose starting and ending positions for that block).

So the total number of ways to choose a sequence with a single uninterrupted block of $1$s is $1+n+{{n}\choose{2}}$. (This also could be written as ${{n}\choose{0}}+{{n}\choose{1}}+{{n}\choose{2}}$.)

So the number of ways to choose so that there are at least two (nonadjacent) blocks of $1$s is given by $2^n-1-n-{{n}\choose{2}}$.

This gives the same result as derived by user2661923, but perhaps a bit simpler.