# Number of sequences with $k$ pairs of consecutive (+1)(-1)

I'm working on a combinatorics problem related to Dyck paths/Ballot sequences/Catalan numbers and the Narayana numbers (defined by $N(n,k) = \frac{1}{n} \binom{n}{k}\binom{n}{k-1}$).

My question is this: Let $P$ be the set of sequences of $\{1^{n+1},(-1)^n\}$, i.e. consisting of $(n+1)$ positive ones and $n$ negative ones, which start with $1$ and contain exactly $k$ pairs of consecutive $(+1)(-1)$s. Prove that $|P| = \binom{n}{k-1} \binom{n-1}{k-1}$.

So I essentially have a binary word, beginning with a $1$, of length $2n+1$ with $k$ pairs of $+1$ followed by $-1$. I've tried to enumerate this by choosing where to put the pairs, but I am having trouble since the second position is special (it comes after a $1$, so if the second position is a $-1$, this adds a pair).

• Do $(+1)(-1)(+1)$ and $(+1)(+1)(-1)$ both count for $k=1$? Or are you counting only $(+1)(-1)$ pairs that don’t involve the initial $(+1)$? – Brian M. Scott Nov 30 '16 at 0:02
• Indeed both of those would count for $k=1$. – Tyler Durden Nov 30 '16 at 0:15
• But then in this case $|P|=2$, and $n=k=1$, while $\binom10\binom00=1$. – Brian M. Scott Nov 30 '16 at 0:16
• The sequence has length $2n+1$, as it has $n+1$ positive ones and $n$ negative ones. So in that case, $n=1$, not $2$. – Tyler Durden Nov 30 '16 at 0:19
• Yes, I just corrected that in my comment; but in this case it makes no difference in the final value of the product of the two binomials, which is still $1$, not $2$. – Brian M. Scott Nov 30 '16 at 0:20

For convenience of notation let me replace $-1$ with $0$. Any string consists of alternating blocks of $1$s and $0$s, beginning with a block of $1$s, and it’s not hard to see that a string has $k$ $10$ pairs if and only if it has exactly $k$ blocks of $0$s. Ignore the leading $1$. A standard stars and bars calculation shows that there are $\binom{n+1}k$ ways to distribute $n$ $1$s amongst the $k+1$ slots before the first block of $0$, between adjacent blocks of $0$s, and after the last block of $0$s under the requirement that the middle $k-1$ slots be non-empty. Similarly, there are $\binom{n-1}{k-1}$ ways to distribute the $n$ $0$s amongst the $k$ blocks of $0$s. Thus, there should be $\binom{n+1}k\binom{n-1}{k-1}$ sequences with $k$ $10$ pairs. Note that
\begin{align*}\binom{n+1}k\binom{n-1}{k-1}&=\frac{n+1}{n+1-k}\binom{n}k\binom{n-1}{k-1}\\ &=\frac{n+1}{n+1-k}\binom{n}k\binom{n}{k-1}\frac{n-k+1}{n}\\ &=(n+1)N(n,k)\;. \end{align*}

This is not provable because it is not true. The question was supposed to also have the constraint of ending on $(-1)$.