Catalan Numbers

Posted by Beetle B. on Mon 20 March 2023

Suppose we want to populate \(2n\) positions with exactly \(n\) 1’s and \(n\) -1’s. But we have a constraint. For any given \(k\) where \(1\le k\le 2n\), the partial sum \(\sum_{i=1}^{k}a_{i}\ge0\). In words, this means there cannot be more \(-1\) entries than \(1\) entries up to that point.

The question is: For a given \(n\), how many such sequences exist?

We know the total number of sequences one can get by placing \(1\) and \(-1\) is:

\begin{equation*} T_{n}=\dbinom{2n}{n} \end{equation*}

Let \(A_{n}\) denote the number of acceptable sequences (i.e. the answer we are looking for).

Let \(U_{n}\) denote the number of unacceptable sequences. Then \(T_{n}=U_{n}+A_{n}\).

We will try to find \(U_{n}\).

For any unacceptable sequence, there is a first index \(k\) such that prior to \(a_{k}\) the sequence is acceptable, and at \(k\) it becomes unacceptable. This means the sum of terms up to \(k-1\) is 0 (equal number of positive and negative \(1\)). Therefore, \(k\) must be odd.

Let us construct another sequence via the following rule:

Up to and including the index \(k\), flip the signs of all the values (convert 1 to -1 and vice versa). Beyond \(k\), keep the values as is.

Note that we now have a sequence with \(n+1\) 1’s and \(n-1\) -1’s.

Note also that this transformation is a bijection.

To see the forward injection, assume you have two distinct unacceptable sequences \(s_{1},s_{2}\), with \(k_{1},k_{2}\). We assume without loss of generality that \(k_{1}\le k_{2}\). Let \(j\) be the index of the first difference between the two.

If \(j<k_{1}\), then \(s_{1j}\ne s_{2j}\). Both will have their signs flipped and will differ in the new sequence.

If \(j>k_{2}\), then \(s_{1j}\ne s_{2j}\). Both will not be modified, and will differ in the new sequence.

Let \(j=k_{1}\). This means it is still valid in \(s_{2}\) and \(k_{1}<k_{2}\). This means \(s_{1j}=-1\) and \(s_{2j}=1\). In either case, both will have their signs flipped and will differ in the new sequence.

Finally, let \(j>k_{1}\) and \(j\le k_{2}\) This is impossible! \(j\) is the index of the first difference. If \(j>k_{1}\), then it means the two sequences match up to \(k_{1}\), which means that both sequences are unacceptable by that point!

For the reverse injection, assume \(t_{1}\ne t_{2}\). To transform back, we find the first index where the partial sum is positive, and apply the same procedure. The logic above applies here as well.

Finally, note that for any sequence of \(n+1\) 1’s and \(n-1\) -1’s, we can always transform “back” using this reverse transformation: We are guaranteed to find one index where the partial sum is positive because we have more 1’s than -1’s.

Therefore, \(U_{n}\) is the count of the number of ways to arrange \(n+1\) 1’s and \(n-1\) -1’s. That’s simply:

\begin{equation*} U_{n}=\dbinom{2n}{n+1} \end{equation*}

To get \(A_{n}\), subtract from \(T_{n}\). The result is:

\begin{equation*} A_{n}=\frac{1}{n+1}\dbinom{2n}{n} \end{equation*}