3
$\begingroup$

I found old exam task.

How many sequences of length $4n$ are there if every sequence needs to contain exactly $2n$ zeroes and $2n$ ones and number of zeroes before $n$-th occurence of one must be not greater than $n$.

So i came up with straightforward solution: $n$-th occurence of one can appear on places from $n$ to $2n$. So we fix $n$-th one at place $n+k$ where $k \in \{ 0\dots n \}$ and first arrange numbers on the left of fixed one and then on the right. This approach gives us the sum: $$\sum_{k=0}^n \binom{n+k-1}{n-1} \binom{3n-k}{n}$$

I was searching for some magical identities in Concrete Mathetmatics book, but none of them seemed to fit (not suitable summation upper limit is in my sum). How can i approach this problem? I'd appreciate some help on this :)

$\endgroup$
  • $\begingroup$ One way to attack it: compute the first half dozen terms or so and ask OEIS. If the sum has a convenient closed form or if the sequence has an alternative definition, it's likely OEIS will recognize it. $\endgroup$ – lulu Aug 16 '16 at 12:20
  • $\begingroup$ @lulu thanks for this good idea. Oeis gave me alternative sequence and a result for this ( oeis.org/A036910 ), but i don't see transformation from my sum to sum in the "formula" section $\endgroup$ – Krzysztof Lewko Aug 16 '16 at 13:02
  • $\begingroup$ That's often the case. Sometimes it's possible to prove the two formulas match inductively, but even in that case there's no guarantee that it will bring enlightenment. In your case...well, I'm a bit skeptical because I don't see a straight forward recursion. Your method looks optimal to me, but that's not the sort of approach that tends to lead to elegant closed forms. And OEIS doesn't seem to have one. Mind you, none of that proves anything...it's perfectly possible that there's another, more intuitive, way to see it. $\endgroup$ – lulu Aug 16 '16 at 13:08
  • $\begingroup$ @lulu you are right, although i think it should be doable, because it's task from exam and students had like 3h to do that and other tasks too. But to be honest, result doesn't seem to be easy to guess. $\endgroup$ – Krzysztof Lewko Aug 16 '16 at 13:32
1
$\begingroup$

A closed for is given by the expression $$\frac12 \left( \binom{4n}{2n} + \binom{2n}{n}^2 \right).$$

Not only do I have a proof, it even matches the first $5$ terms in the OEIS sequence, so it must be right!

To see where this formula comes from, observe that the sequences come in complementary pairs, where the complement of a sequence is the sequence obtained by exchanging $0$s and $1$s. For example, when $n = 1$, the $\binom{4}{2} = 6$ sequences are paired up as follows: $$ \{ 0011, 1100\}, \{ 0101, 1010 \}, \{0110, 1001\}. $$

Now suppose a sequence is not good. That means there are more than $n$ $0$s before the $n$th $1$. This means that there are fewer than $n$ $1$s before the $n$th $0$, so the complement of this sequence will be good. In other words, every complementary pair has at least one good sequence. This is where the $\frac12 \binom{4n}{2n}$ in the formula comes from.

However, there are some pairs where both sequences are good. In order for this to happen, there must be at most $n$ $0$s before the $n$th $1$, and at most $n$ $1$s before the $n$th $0$. This means that the first $2n$ elements must contain exactly $n$ $0$s and $n$ $1$s. There are $\binom{2n}{n}$ ways of choosing these first $2n$ elements. Since the last $2n$ elements must also have $n$ $0$s and $n$ $1$s, there are $\binom{2n}{n}$ ways of choosing the last $2n$ elements. Hence there are $\binom{2n}{n}^2$ sequences where both the sequence and its complement are good. We have already counted one from each such pair above, so we add half this to account for the second sequence in the pair, giving the $\frac12 \binom{2n}{n}^2$ term in the formula.

As a side remark, the formula in the OEIS entry is $\sum_{k=0}^n \binom{2n}{k}^2$. This comes from letting $k$ be the number of $0$s in the first $2n$ entries. This can be anything between $0$ and $n$, but it cannot be bigger than $n$ as otherwise there would be more than $n$ $0$s before the $n$th $1$. There are then $\binom{2n}{k}$ ways of choosing the first $2n$ entries. The last $2n$ elements must have exactly $k$ $1$s, and there are a further $\binom{2n}{k}$ ways of choosing those elements. This leads to the formula $\sum_{k=0}^n \binom{2n}{k}^2$.

$\endgroup$
  • $\begingroup$ And now that I look at the OEIS entry more closely, I see, with deflating effect, that the closed form was there in the title all along. $\endgroup$ – Shagnik Aug 16 '16 at 14:16
  • 1
    $\begingroup$ This is great way to look at this problem! Thank you very much for such detailed answer. $\endgroup$ – Krzysztof Lewko Aug 16 '16 at 14:40
  • $\begingroup$ You're welcome, happy to help! $\endgroup$ – Shagnik Aug 17 '16 at 10:57
2
$\begingroup$

$$\begin{align} \sum_{k=0}^n\binom {n+k-1}{n-1}\binom {3n-k}n &=\sum_{k=0}^n\binom {n+k-1}{k}\binom {3n-k}{2n-k}\\ &=\sum_{k=0}^n(-1)^k\binom {-n}k (-1)^{2n-k}\binom {-n-1}{2n-k}&&\text{(upper negation)}\\ &=\sum_{k=0}^{n}\binom {-n}k\binom {-n-1}{2n-k}\\ \text{Note that}\sum_{k=0}^{2n}\binom {-n}k\binom {-n-1}{2n-k} &=\binom{-2n-1}{2n}&&\text{(Vandermonde)}\\ &=(-1)^{2n}\binom{4n}{2n}&&\text{(upper negation)}\\ &=\binom{4n}{2n}\\ \text{and that} \sum_{k=0}^{n-1}\binom {-n}k\binom {-n-1}{2n-k} &=\sum_{k=n}^{2n}\binom {-n}k\binom {-n-1}{2n-k}=\frac 12 \binom {4n}{2n}\\ \text{Hence} \sum_{k=0}^{n}\binom {-n}k\binom {-n-1}{2n-k} &=\left[\sum_{k=0}^{n-1}\binom {-n}k\binom {-n-1}{2n-k}\right]+\binom {-n}n\binom {-n-1}n\\ &=\frac 12 \binom {4n}{2n}+(-1)^n\binom {2n-1}n(-1)^n\binom{2n}n\\ &=\frac 12 \binom {4n}{2n}+\binom {2n-1}n\binom{2n}n\\ &=\frac 12 \binom {4n}{2n}+\frac 12\binom {2n}n\binom{2n}n &&\text{as }\binom {2n}n=\frac {2n}n\binom {2n-1}n\\ &=\color{red}{\frac 12 \left[\binom {4n}{2n}+\binom {2n}n^2\right] \qquad\blacksquare} \end{align}$$

$\endgroup$
  • $\begingroup$ @MarkusScheuer - Thanks for your comment. Edited accordingly. $\endgroup$ – hypergeometric Aug 18 '16 at 17:07
  • $\begingroup$ Nicely done! (+1) But, the real challenge is proving the middle part. Namely the line with: ...and that... :-) Could you also show this rather difficult part? $\endgroup$ – Markus Scheuer Aug 18 '16 at 17:16
  • $\begingroup$ I've added an answer with a proof for the middle part. Regards, $\endgroup$ – Markus Scheuer Aug 19 '16 at 22:42
  • $\begingroup$ @MarkusScheuer - Thanks for your proof! $\endgroup$ – hypergeometric Aug 20 '16 at 9:33
2
$\begingroup$

Here is an algebraic solution which is a supplement of the nice answer of @hypergeometric. Note that his answer contains a middle part which needs a proof and which is quite tricky to solve.

We use following approach \begin{align*} \sum_{k=0}^n\binom{n+k-1}{n-1}\binom{3n-k}{n} &=\sum_{k=0}^{2n}\binom{n+k-1}{n-1}\binom{3n-k}{n}\\ &\qquad-\sum_{k=n+1}^{2n}\binom{n+k-1}{n-1}\binom{3n-k}{n} \end{align*}

In the right-hand side we extend the range of the first sum to $2n$ which is easy to calculate and then we focus on the other sum, the surplus which is the somewhat more challenging part.

First sum: $0\leq k\leq 2n$

\begin{align*} \sum_{k=0}^{2n}\binom{n+k-1}{n-1}\binom{3n-k}{n} &=\sum_{k=0}^{2n}\binom{n+k-1}{k}\binom{3n-k}{2n-k}\\ &=\sum_{k=0}^{2n}\binom{-n}{k}\binom{-n-1}{2n-k}\\ &=\binom{-2n-1}{2n}\\ &=\binom{4n}{2n} \end{align*}

These steps use upper negation and Vandermonde's identity as we can see in the first half of the answer of @hypergeometric.

In order to calculate the second sum it is convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

Second sum: $n+1\leq k \leq 2n$

We obtain \begin{align*} \sum_{k=n+1}^{2n}&\binom{n+k-1}{n-1}\binom{3n-k}{n}\\ &=\sum_{k=0}^{n-1}\binom{2n+k}{n-1}\binom{2n-k-1}{n-k-1}\tag{1}\\ &=\sum_{k=0}^\infty [z^{n-1}](1+z)^{2n+k}[u^{n-k-1}](1+u)^{2n-k-1}\tag{2}\\ &=[z^{n-1}](1+z)^{2n}[u^{n-1}](1+u)^{2n-1}\sum_{k=0}^\infty\left(\frac{u(1+z)}{1+u}\right)^k\tag{3}\\ &=[z^{n-1}](1+z)^{2n}[u^{n-1}](1+u)^{2n-1}\frac{1}{1-\frac{u(1+z)}{1+u}}\tag{4}\\ &=[z^{n-1}](1+z)^{2n}[u^{n-1}](1+u)^{2n}\frac{1}{1-uz}\tag{5}\\ &=[z^{n-1}](1+z)^{2n}[u^{n-1}]\sum_{k=0}^\infty \left(uz\right)^k(1+u)^{2n}\tag{6}\\ &=[z^{n-1}](1+z)^{2n}\sum_{k=0}^{n-1}z^k[u^{n-1-k}](1+u)^{2n}\tag{7}\\ &=[z^{n-1}](1+z)^{2n}\sum_{k=0}^{n-1}z^k\binom{2n}{n-1-k}\tag{8}\\ &=\sum_{k=0}^{n-1}[z^{n-1-k}](1+z)^{2n}\binom{2n}{n-1-k}\tag{9}\\ &=\sum_{k=0}^{n-1}\binom{2n}{n-1-k}^2\tag{10}\\ &=\sum_{k=0}^{n-1}\binom{2n}{k}^2\tag{11}\\ \end{align*}

Comment:

  • In (1) we shift the index range from $k\in[n+1,2n]$ to $k\in[0,n-1]$ and we use the symmetry $\binom{p}{q}=\binom{p}{p-q}$ in the second factor as preparation for the next step.

  • In (2) we apply the coefficient of operator twice and we extend the upper range of the series to $\infty$ without changing anything since thanks to the second factor we add only zeros.

  • In (3) we do some rearrangements, use the linearity of the coefficient of operator and use the rule $[z^{p+q}]A(z)=[z^p]z^{-q}A(z)$.

  • In (4) and (5) we use the geometric series expansion and do some simplifications.

  • In (6) and (7) we expand $\frac{1}{1-zu}$ and apply the same rule as in (3). Since the exponent of $z^{n-k-1}$ is non-negative, we restrict the upper range of the sum with $n-1$.

  • In (8) we select the coefficient of $z^{n-k-1}$.

  • In (9) and (10) we do the same steps with $z$ as we did with $u$ in (7) and (8).

  • In (11) we use the symmetry $\binom{p}{q}=\binom{p}{p-q}$.

Putting all together:

The sum (11) is due to its symmetry easily to manage. We observe on the one hand with the help of Vandermonde's identity \begin{align*} \sum_{k=0}^{2n}\binom{2n}{k}^2=\sum_{k=0}^{2n}\binom{2n}{k}\binom{2n}{n-k}=\binom{4n}{2n}\tag{12} \end{align*} On the other hand we have \begin{align*} \sum_{k=0}^{2n}\binom{2n}{k}^2 =\sum_{k=0}^{n-1}\binom{2n}{k}^2+\binom{2n}{n}^2+\sum_{k=n+1}^{2n}\binom{2n}{k}^2 \end{align*} and since \begin{align*} \sum_{k=n+1}^{2n}\binom{2n}{k}^2&=\sum_{k=0}^{n-1}\binom{2n}{k+n+1}^2\\ &=\sum_{k=0}^{n-1}\binom{2n}{2n-k}^2\qquad\qquad\qquad k\longrightarrow n-1-k\\ &=\sum_{k=0}^{n-1}\binom{2n}{k}^2 \end{align*} we obtain \begin{align*} \sum_{k=0}^{2n}\binom{2n}{k}^2=2\sum_{k=0}^{n-1}\binom{2n}{k}^2+\binom{2n}{n}^2\tag{13} \end{align*}

We obtain from (12) and (13) \begin{align*} \sum_{k=0}^{n-1}\binom{2n}{k}^2&=\frac{1}{2}\sum_{k=0}^{2n}\binom{2n}{k}^2-\frac{1}{2}\binom{2n}{n}^2\\ &=\frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}\right) \end{align*}

and can finally conclude \begin{align*} \sum_{k=0}^n\binom{n+k-1}{n-1}\binom{3n-k}{n} &=\sum_{k=0}^{n-1}\binom{2n}{k}^2\\ &=\frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}\right)\qquad\qquad n\geq 1\\ \end{align*}

$\endgroup$
  • $\begingroup$ Very nice proof! (+1) Thanks! $\endgroup$ – hypergeometric Aug 20 '16 at 9:34
  • $\begingroup$ @hypergeometric: My pleasure. Thanks for your nice comment! :-) $\endgroup$ – Markus Scheuer Aug 20 '16 at 10:52

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.