Counting Special Non-Descending Sequences

In this blog post, I will discuss the solution to a very fascinating math problem that I came up with while pondering challenging math problems. The solution to this problem happens to be a really interesting combinatorics identity, and it can be used to describe some very interesting counting problems (including the number of ways to match parentheses).

How many non-descending sequences of integers $ a_1, a_2, \dots, a_n $ are there such that $ 0 \leq a_i < i \: \forall \: i \leq n $?

If \( n = 1 \), the only possible sequence is \( a_1 = 0 \).  Similarly, for \( n = 2 \), the possible sequences are \( \{ [0,0], [0,1] \} \).  For \( n = 3 \), the possible sequences are
\( \{ [0,0,0], [0,0,1], [0,0,2], [0,1,1], [0,1,2] \} \).  Let's let \( f(n) \) denote the number of valid sequences of length \( n \).  From these examples, it is clear that \( f(1) = 1, f(2) = 2, \) and \( f(3) = 5 \).  We would ideally like to get a nice combinatoric expression for \( f(n) \).  Let's define another function, \( g(n, k) \) such that \( g(n, k) \) is the number of valid sequences of length \( n \) under the additional constraint that that all numbers in the sequence are at most \( k \).  This is a useful definition because if we let \( a_i = k \), then \( a_j \leq k \quad \forall j < i \).  Thus, \( f(n) = g(n, n-1) \).  Now that I've setup a good framework, we can try to write down a recurrence relation for \( g(n, k) \) that describes this problem.

You can reduce \( g(n, k) \) recursively by figuring out all the possible values for the last number in the sequence, then solving the sub problem that arises from choosing that number.  For example, if I wanted to compute \( g(5, 3) \), I could let the last element in the sequence be \( 0, 1, 2, \) or \( 3 \).  In each case, I will need to solve \( g(4,0), g(4,1), g(4,2), \) and \( g(4,3) \) respectively.  This gives rise to a nice recurrence relation for \( g(n, k) \).
$$
g(n, k) =
\left\{
    \begin{array}{ll}
        g(n, k-1) \quad &if \quad n = k\\
        \sum_{i=0}^k g(n-1, i) \quad &if \quad n > k
    \end{array}
\right.
$$ Here, we must take \( g(k, k) = g(k, k-1) \) as a definition because \( k \)  is not a valid number for \( a_k \) because \( 0 \leq a_k < k \).  In the general case, however, we have
$$
g(n, k) = g(n-1, 0) + g(n-1, 1) + \dots + g(n-1, k)
$$ Well we can greatly simplify this recurrence relation by noticing that
$$
g(n, k-1) = g(n-1, 0) + g(n-1, 1) + \dots + g(n-1, k-1)
$$ Thus, \( g(n, k) \) can be compactly written in the following form
$$
g(n, k) = g(n, k-1) + g(n-1, k)
$$ From this recursive definition, we can construct a nice triangle for \( g(n, k) \)
$$
\begin{array}{c|cccc}
& k=0 & 1 & 2 & 3 & 4 & 5 & \dots\\
\hline
n=0 & 1\\
1 & 1 & 1\\
2 & 1 & 2 & 2\\
3 & 1 & 3 & 5 & 5\\
4 &  1 & 4 & 9 & 14 & 14\\
5 & 1 & 5 & 14 & 28 & 42 & 42\\
\vdots & & \vdots & & \vdots & & \ddots
\end{array}
$$ The construction for this triangle is pretty similar to Pascal's triangle (where each element is the sum of the two parents).  In fact, this is the exact construction for Catalan's Triangle.  The numbers we are interested in (in terms \( f(n) \)) are those that are along the second diagonal, which is the same as the outer diagonal because \( g(k,k) = g(k, k-1) \).  These are the Catalan Numbers!  They have the general form
$$
f(n) = \frac{1}{n+1} {2 n \choose n}
$$ This is a fascinating result, and when I thought of this problem, I had no idea there was going to be so much cool mathematics behind it!

After reading about the Catalan Numbers for a while, I realized that I could reduce this to a parentheses matching problem.  Consider the following model, where you start at \( (0,0) \) in a lattice and are allowed to move right or up until you reach \( (n, n) \).  Further you may never go above the points \( (k, k) \).

In this example, the corresponding sequence would be \( [0,1,1,3,3,4] \), because those are the minimum y coordinates corresponding to each x coordinate.  The diagonal red line enforces the constraint that \( a_k < k \) and the non-descending constraint is enforced by the fact that you may only move right and up (and not down).  Thus, we can abstract this interpretation by noting that the number of distinct ways to walk from \( (0,0) \) to \( (n, n) \) without going over the red line is given by the number of strings with n R's and n U's such that every substring has at least as many R's as U's.  If there are less R's than U's, then you must be under the red line, so the condition \( a_k < k \) is clearly satisfied.  If we treat R's as open parentheses and U's as closed parentheses, then we can reduce this problem to the number of possible ways to match n pairs of parentheses, which is also given by the Catalan numbers.