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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 27 '16 at 17:50
  • $\begingroup$ @GregMartin Nice observation, thanks! $\endgroup$ – 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


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



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.