# How to prove this formula for counting sub-sequences?

A sequence $(s_i)_0^{N+2m}$ of ones and zeroes has ones on $s_0$ and $s_{N+2m}$ and it's subsequence $(s_i)_1^{N+2m-1}$ that lies in between contains $N+m-1$ ones and $m$ zeroes, where $N\in \mathbb{N}$ and $m\in \mathbb{N}_0$. Such a sequence $(s_i)$ can be split into $N+2m$ subsequences consisting of adjacent elements in $(s_i)$, which together form a set called the decomposition of $(s_i)$. For example, if $N=2$ and $m=1$, we could have

$$(s)=(1,1,0,1,1) \mapsto \{(1,1),(1,0),(0,1),(1,1)\}.$$

There are four different such subsequences, namely $(1,1)$, $(0,0)$, $(1,0)$, and $(0,1)$. Assign a number $a$ to the first two and a number $b$ to the last two. For a given sequence $(s_i)$, define $p_i$ to be the product of the values associated with the elements in the decomposition of $(s_i)$. In the example above, $$p=a\cdot b\cdot b \cdot a=a^2b^2.$$

Given that there are $\binom{N+2m-1}{m}$ different sequences $(s_1),(s_2),\dots,(s_i),\ldots$ what is $$P_{mN}=\sum_{i=1}^{\binom{N+2m-1}{m}}\!p_i\;?$$

Continuing the example from above, we have the three possible sequences

\begin{align} 10111 \rightarrow p_1&=b^2a^2\\ 11011 \rightarrow p_2&=aba \quad \rightarrow \quad P_{12}=3a^2b^2.\\ 11101 \rightarrow p_3&=a^2b^2 \end{align}

I propose that the solution is

$$\boxed{P_{mN}=\sum_{i=1}^m \binom{m-1}{i-1}\binom{N+m}{i} a^{N+2m-2i}b^{2i} \quad \text{for m>0 and that P_{0N}=a^N}}.$$

I've come to this proposal by simply looking at the patterns. How can it be proven?

Here are some calculated examples of $P_{mN}$:

\begin{array}{c|c|c|c} m & N & P_{mN} & P_{mN}\\ \hline 0 & 1 & a \\ & 2 & a^2 \\ & 3 & a^3 \\ \hline 1 & 1 & 2ab^2 & \binom{0}{0}\binom{2}{1}ab^2\\ & 2 & 3a^2b^2 & \binom{0}{0}\binom{3}{1}a^3b^2\\ & 3 & 4a^3b^2 & \binom{0}{0}\binom{4}{1}a^4b^2\\ \hline 2 & 1 & 3a^3b^2+3ab^4 & \binom{1}{0}\binom{3}{1}a^3b^2+\binom{1}{1}\binom{3}{2}ab^4\\ & 2 & 4a^4b^2+6a^2b^4 & \binom{1}{0}\binom{4}{1}a^4b^2+\binom{1}{1}\binom{4}{2}a^2b^4\\ & 3 & 5a^5b^2+10a^3b^4 & \binom{1}{0}\binom{5}{1}a^5b^2+\binom{1}{1}\binom{5}{2}a^3b^4\\ \hline 3 & 1 & 4a^5b^2+12a^3b^4+4ab^6 \\ & 2 & 5a^6b^2+20a^4b^4+10a^2b^6 & \vdots\\ & 3 & 6a^6b^2+30a^5b^4+20a^3b^6 \\ \hline 4 & 1 & 5a^7b^2+30a^5b^4+30a^3b^6+5ab^8 \\ & 2 & 6a^8b^2+45a^6b^4+60a^4b^4+15a^2b^6 & \vdots\\ & 3 & 7a^3b^2+63a^7b^4+105a^5b^6+35a^3b^8 \\ \vdots & \vdots & \vdots \end{array}

I have checked this for higher $m$, but it becomes tedious to write out.

The exponents of $a$ and $b$ must add to $N+2m$, since there are exactly as many elements in a given decomposition. Furthermore, the coefficients must add to $\binom{N+2m-1}{m}$, as this is the number of possible sequences and each sequence contributes with one term.

Any help would be much appreciated!

• It seems that the summand indexed by a particular value of $i$ corresponds to sequences with $i$ runs of zeros in total. For example, $i=1$ corresponds to those sequences where all the zeros are consecutive. This certainly produces the right powers of $a$ and $b$; maybe you can show that the coefficient is correct in this way. – Greg Martin Aug 27 '16 at 17:50
• @GregMartin Nice observation, thanks! – Bobson Dugnutt Aug 27 '16 at 17:54

It’s a pair of stars-and-bars calculations. There are $\binom{m-1}{k-1}$ ways to divide $m$ zeroes into $k$ blocks. The $k$ blocks of zeroes determine $k+1$ gaps, including the two ends gaps, each of which must contain at least $1$ one. The $N+m+1$ ones can be distributed amongst the $k+1$ gaps in $\binom{N+m}k$ ways so that each gap receives at least $1$ one. Thus, there are
$$\binom{m-1}{k-1}\binom{N+m}k$$
ways to distribute the interior ones and zeroes to produce $k$ blocks of zeroes. Each block of zeroes produces a $\langle 1,0\rangle$ pair and a $\langle 0,1\rangle$ pair, so it produces two $b$s. The total degree of the term for any sequence of length $N+2m+1$ is $N+2m$, so the terms $a^{N+2m-2k}b^{2k}$ are precisely those corresponding to sequences with $k$ blocks of zeroes, and the coefficient of $a^{N+2m-2k}b^{2k}$ is therefore
$$\binom{m-1}{k-1}\binom{N+m}k\;.$$