2
$\begingroup$

Let $s$ be a length $n$ binary string. It is natural to ask how many distinct length $n+m$ binary strings can be made by inserting $m$ binary characters into $s$.

As an example, we can consider the distinct strings made by inserting two characters into the string $001$. Since we are inserting two characters, we are either inserting two $0$'s, one $1$ and one $0$, or two $1$'s. Inserting two $0$'s may be done in the three following distinct ways: $$00001, 00010, 00100~.$$ Inserting one $1$ and one $0$ may be done in the seven following distinct ways: $$10001, 01001, 00101, 00011, 10010, 01010, 00110~.$$ Finally, inserting two $1$'s may be done in the six following distinct ways: $$11001, 10101, 10011, 01101, 01011, 00111~.$$ Therefore we have 16 distinct strings made by inserting two characters into $001$.

Using a similar process, we can show that there are $16$ distinct strings made by inserting two characters into $000$. Similarly, there are $16$ distinct strings made by inserting two characters into $010$. In fact, for any length $3$ binary string $s$ there are $16$ distinct strings made by inserting two characters into $s$.

After discovering this, I wrote some Python code to see if this sort of thing holds more generally. As it turns out, the number of distinct strings made by inserting $m$ characters into a binary string $s$ is the same for all $s$ of length $n$. Furthermore, we get the following formula for the number of distinct strings $S$ as a function of $n$ and $m$:

$$S(n,m) = {n+m \choose 0} + {n+m \choose 1} + {n+m \choose 2} + ... + {n+m \choose m}~.$$

If we assume that $S(n,m)$ is well-defined for all $n$ and $m$ (that is, if different base strings of length $n$ give the same answer), then proving this formula is relatively straightforward. In the case of the base string $00 \ldots 0$ of length $n$, the strings of length $n+m$ formed by inserting $m$ characters are precisely the binary strings of length $n+m$ containing at least $n$ zeros. These can be counted by ignoring the strings of length $n+m$ with fewer than $n$ zeros.

$$\begin{align}S(n,m) &= 2^{n+m} - {n+m \choose 0} - {n+m \choose 1} - ... - {n+m \choose n-1} \\ &= {n+m \choose n} + {n+m \choose n+1} + ... + {n+m \choose n+m} \\ &= {n+m \choose 0} + {n+m \choose 1} + ... + {n+m \choose m}.\end{align}$$

This proof of the formula only works, however, if we are willing to grant that the number of distinct strings depends only on $m$ and on the length $n$ of the base string. I was unable to prove this fact. Can someone provide a deeper explanation of what's going on here?

$\endgroup$
1
$\begingroup$

Think of it in a different way. Given binary strings $T$ and $S$ of lengths $n+m$ and $n$ respectively, $T$ can be obtained from $S$ by inserting $m$ characters if and only if $S$ is a subsequence of $T$. Now, when is that true?

If it is, the subsequence can be obtained as follows. Starting at the left, let $i_1$ be the first position $i$ where $T_i = S_1$, let $i_2$ be the first $i > i_1$ where $T_i = S_2$, ..., $i_n$ the first $i > i_{n-1}$ where $T_i = S_n$. If you can define $i_1, \ldots, i_n$ in this way, i.e. you never get to a point where there are no $i > i_{k-1}$ such that $T_i = S_k$, then $S$ is the subsequence $T_{i_1},\ldots, T_{i_n}$.

Now, given two binary strings $S$ and $S'$ of length $n$, I will define a map $f$ from $\{0,1\}^{n+m}$ to itself such that $S$ is a subsequence of $T$ if and only if $S'$ is a subsequence of $f(T)$. Consider the construction above for $T$ and $S$, obtaining $i_1, \ldots, i_k$ (where either $k=n$, in which case $S$ is a subsequence of $T$, or $k < n$ and $i_{k+1}$ does not exist). For convenience, take $i_0 = 0$, and $i_{k+1} = n+m+1$. If $i_{j-1} < i \le i_{j}$, let $f(T)_i = T_i$ if $S_j = S'_j$ (or $j = n+1$), $1-T_i$ if $S_j \ne S'_j$. It is easy to see that $f$ is a one-to-one correspondence and has the desired property. This shows that the number of $T$ with $S$ as a subsequence is equal to the number with $S'$ as a subsequence.

$\endgroup$
  • $\begingroup$ Ah, I see. Thanks! $\endgroup$ – Dan LaPointe May 1 at 3:48
  • $\begingroup$ Can you confirm my understanding? $f$ kinda cuts $T$ into segments based on $(i_j)$ and then flips those where $S_j \neq S'_j$. This ensures that $f(T)$ would be cut by $S'$ using the same indices $(i_j)$. And since the process is reversible (starting from $S'$ instead) this implies $f$ is bijective, right? I am still trying to fully grasp this, but IMHO this is a very clever proof! And of a very non-obvious fact too! How did you come up with this mapping? $\endgroup$ – antkam May 2 at 0:15
1
$\begingroup$

A direct proof of the formula for $S(n,m)$ inspired by Robert's approach. Taking after Robert, we can reformulate this question as "how many length $n+m$ binary strings have a given length $n$ string as a subsequence?" Also taking from Robert, we know that if a length $n$ sub-sequence $S$ appears in a length $n+m$ binary string $T$, then it must appear a "first time" in the sense that there exist indices $i_1<i_2<...<i_n$ such that $i_1$ is the smallest index such that $T_{i_1} = S_1$, and such that each of the $i_k$'s is the smallest $i$ such that $i_k > i_{k-1}$ and such that $T_{i_k} = S_k$.

To count the number of length $n+m$ binary strings containing $S$ as a sub-sequence, we add together the number of strings such that $i_n = n$, the number such that $i_n = n+1$, the number such that $i_n = n+2$, etc. out to the number of strings such that $i_n = n+m$.

How many length $n+m$ strings are there such that $i_n = n$? Such strings must have the string $S$ as the first $n$ characters, but are allowed to vary freely in their last $m$ characters. Hence we have $2^m$ such strings.

How many length $n+m$ strings are there such that $i_n = n+1$? Such strings must be such that $T_{n+1} = S_n$, and they must contain exactly one index $i < n+1$ such that $i \not\in i_1,i_2,...,i_n$. There are ${n \choose 1}$ ways this $i$ can be placed. Since the placement of this $i$ determines the value ($1$ or $0$) that $T_i$ takes (in order to be consistent with the fact that $i \not\in i_1,i_2,...,i_n$), and since the $m-1$ characters after $T_{n+1}$ can vary freely, we deduce that there are ${n \choose 1} \cdot 2^{m-1}$ strings such that $i_n = n + 1$.

How many length $n+m$ strings are there such that $i_n = n+2$? Such strings must be such that $T_{n+2} = S_n$, and they must contain indices $i_a<i_b < n+2$ such that $i_a,i_b \not\in i_1,i_2,...,i_n$. There are ${n+1 \choose 2}$ ways $i_a$ and $i_b$ can be placed. Since the placement of these indices determines the values ($1$ or $0$) that $T_{i_a}$ and $T_{i_b}$ take (in order to be consistent with the fact that $i_a,i_b \not\in i_1,i_2,...,i_n$), and since the $m-2$ characters after $T_{n+2}$ can vary freely, we deduce that there are ${n+1 \choose 2} \cdot 2^{m-2}$ strings such that $i_n = n + 2$.

Continuing this pattern, we deduce that

$$S(n,m) = \sum_{i = 0}^{m}2^{m-i}{n-1+i \choose i}.$$

The goal, however, was to prove that

$$S(n,m) = \sum_{i=0}^{m}{n+m \choose i}.$$

The equivalence of these two sums can be seen using Pascal's Triangle. This approach, which I won't give in full detail, relies on repeated applications of Pascal's Rule, and is similar in spirit to the proof by induction that the sum of the terms in the $n$th row of Pascal's Triangle is $2^n$.

$\endgroup$
1
$\begingroup$

For each length $n$ string $A$ contained in a length $m+n$ string $B$, there is a unique first occurrence of $A$ in $B$. To find it, just start looking for the first character of $A$ (either a 0 or a 1) at the left side of $B$ and move right until you find one. Then move right until you find the second character of $A$, and so on until you've found all the characters of $A$.

For how many strings $B$ will the first occurrence of $A$ be found in the leftmost $n+k$ characters of $B$ (and in no fewer)? Well, there must be $k$ instances where you moved right without finding the next character of $A$. So between the successive characters of $A$ in $B$, there had to have been $k$ instances of the "wrong" character. There are $n$ bins to put these "wrong" characters into (before the first character of $A$, between the first and second, between the second and third, etc.), so using the formula for number of ways to put $k$ balls in $n$ boxes, there are $\binom{n+k-1}{k}$ choices for the first $n+k$ characters of $B$. Then the remaining $m-k$ characters of $B$ are totally unconstrained, so there are $2^{m-k}$ choices for these. Summing over $k$, the total number of strings $B$ containing $A$ is $$\sum_{k=0}^m \binom{n+k-1}{k}2^{m-k}$$ This formula is independent of the string $A$, which proves your point. It also establishes a combinatorial proof of equality between this sum and the one you discovered.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.