Sequences of length $4n$ with $2n$ ones and $2n$ zeroes with one constraint.

Question

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 :)

Answer 1

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

Answer 2

$$\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}$$

Answer 3

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*}