# Number of distinct binary strings made by inserting m characters into a given string

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?

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.

• Ah, I see. Thanks! – Dan LaPointe May 1 at 3:48
• 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? – antkam May 2 at 0:15

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 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 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$$.

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.