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

  • $\begingroup$ 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)$? $\endgroup$ – Brian M. Scott Nov 30 '16 at 0:02
  • $\begingroup$ Indeed both of those would count for $k=1$. $\endgroup$ – Tyler Durden Nov 30 '16 at 0:15
  • $\begingroup$ But then in this case $|P|=2$, and $n=k=1$, while $\binom10\binom00=1$. $\endgroup$ – Brian M. Scott Nov 30 '16 at 0:16
  • $\begingroup$ 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$. $\endgroup$ – Tyler Durden Nov 30 '16 at 0:19
  • $\begingroup$ 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$. $\endgroup$ – 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)$.


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.