Sequences of length $4n$ with $2n$ ones and $2n$ zeroes with one constraint. 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 :)
 A: $$\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}$$
A: 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$.
