The Catalan Series

    Mar 2, 2024

    The article discusses Catalan numbers, a sequence used in combinatorial problems. It covers their recurrence relation, closed form, and applications in path counting. It provides insights into problem-solving using Catalan numbers.

    Catalan Numbers

    Catalan numbers HnH_n can be applied to the following problems:

    1. There are 2n2n people queuing up to enter a theater. The entrance fee is 5 yuan. Among them, only nn people have a 5 yuan bill, while the other nn people only have a 10 yuan bill. The theater has no other bills. How many ways are there to ensure that whenever a person with a 10 yuan bill buys a ticket, the ticket office has a 5 yuan bill for change?
    2. There is a grid of size n×nn\times n with the lower left corner at (0,0)(0, 0) and the upper right corner at (n,n)(n, n). Starting from the lower left corner, you can only move one unit to the right or up each time, without going above the diagonal line y=xy=x. How many possible paths are there to reach the upper right corner without crossing the line y=xy=x?
    3. Choose 2n2n points on a circle and connect these points pairwise to obtain nn line segments. How many ways are there to ensure that the nn line segments obtained do not intersect?
    4. Without intersecting diagonals, how many ways are there to divide a convex polygon area into triangular regions?
    5. If the stack (infinite) has a push sequence of 1,2,3,,n1,2,3, \cdots ,n, how many different pop sequences are there?
    6. How many different binary trees can be constructed with nn nodes?
    7. Given 2n2n numbers consisting of nn +1+1s and nn 1-1s, denoted as a1,a2,,a2na_1,a_2, \cdots ,a_{2n}, such that the partial sum satisfies a1+a2++ak0 (k=1,2,3,,2n)a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n), how many sequences satisfy this condition?

    The corresponding sequence is:

    H0H_0H1H_1H2H_2H3H_3H4H_4H5H_5H6H_6...
    11251442132...

    Recurrence Relation

    The solution to this recurrence relation is:

    Hn=(2nn)n+1(n2,nN+)H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})

    Common formulas for Catalan numbers are:

    Hn={i=1nHi1Hnin2,nN+1n=0,1H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases} Hn=Hn1(4n2)n+1H_n = \frac{H_{n-1} (4n-2)}{n+1} Hn=(2nn)(2nn1)H_n = \binom{2n}{n} - \binom{2n}{n-1}

    A common application: for a stack, the push sequence is 1,2,,n1,2, \ldots ,n, find the total number of possible pop sequences.

    #include <iostream>
    using namespace std;
    int n;
    long long f[25];
    
    int main() {
      f[0] = 1;
      cin >> n;
      for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
      // Here, formula 2 is used
      cout << f[n] << endl;
      return 0;
    }
    

    Closed Form

    The recurrence relation of Catalan numbers is

    Hn=i=0n1HiHni1(n2)H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2)

    where H0=1H_0=1 and H1=1H_1=1. Let its ordinary generating function be H(x)H(x).

    We find that the recurrence relation of Catalan numbers is similar to the form of convolution. Therefore, we construct an equation about H(x)H(x) using convolution:

    H(x)=n0Hnxn=1+n1i=0n1HixiHni1xni1x=1+xi0Hixin0Hnxn=1+xH2(x)\begin{aligned} H(x)&=\sum_{n\ge 0}H_nx^n\\ &=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\ &=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\ &=1+xH^2(x) \end{aligned}

    Solving this equation, we get

    H(x)=1±14x2xH(x)=\frac{1\pm \sqrt{1-4x}}{2x}

    Now, we have a question: which root should we take? Rationalizing the numerator, we get

    H(x)=2114xH(x)=\frac{2}{1\mp \sqrt{1-4x}}

    Substituting x=0x=0, we obtain the constant term of H(x)H(x), which is H0H_0. When H(x)=21+14xH(x)=\dfrac{2}{1+\sqrt{1-4x}}, we have H(0)=1H(0)=1, satisfying the requirement. The other root leads to the denominator being 00 (non-convergence), so it is discarded.

    Therefore, we obtain the closed form of the generating function of Catalan numbers:

    H(x)=114x2xH(x)=\frac{1- \sqrt{1-4x}}{2x}

    Next, we need to expand it. But note that its denominator is not in the form of a polynomial like the Fibonacci sequence, so it is not convenient to use the expansion form of geometric sequences. Here we need to use Newton's binomial theorem. Let's first expand 14x\sqrt{1-4x}:

    (14x)12=n0(12n)(4x)n=1+n1(12)nn!(4x)n(1)\begin{aligned} (1-4x)^{\frac{1}{2}} &=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n \end{aligned} \tag{1}

    Note that

    (12)n=121232(2n3)2=(1)n1(2n3)!!2n=(1)n1(2n2)!2n(2n2)!!=(1)n1(2n2)!22n1(n1)!\begin{aligned} \left(\frac{1}{2}\right)^{\underline{n}} &=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3 )!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned}

    Here, we use the simplification technique of double factorials. Then, substitute into (1)(1), we get

    (14x)12=1+n1(1)n1(2n2)!22n1(n1)!n!(4x)n=1n1(2n2)!(n1)!n!2xn=1n1(2n1n)1(2n1)2xn\begin{aligned} (1-4x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n \end{aligned}

    Substitute back into the original expression, we get

    H(x)=114x2x=12xn1(2n1n)1(2n1)2xn=n1(2n1n)1(2n1)xn1=n0(2n+1n+1)1(2n+1)xn=n0(2nn)1n+1xn\begin{aligned} H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\ &=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\ &=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\ \end{aligned}

    Thus, we obtain the general formula for Catalan numbers.

    Path Counting Problem

    Non-decreasing paths refer to paths that can only move upwards or to the right.

    1. The number of non-decreasing paths from (0,0)(0,0) to (m,n)(m,n) is equal to the number of permutations of mm xx and nn yy, i.e., (n+mm)\dbinom{n + m}{m}.

    2. The number of non-decreasing paths from (0,0)(0,0) to (n,n)(n,n) that do not touch the line y=xy=x except at endpoints:

      First, consider the paths below the line y=xy=x, which all start from (0,0)(0, 0), pass through (1,0)(1, 0) and (n,n1)(n, n-1), and reach (n,n)(n,n). This can be seen as the number of non-decreasing paths from (1,0)(1,0) to (n,n1)(n,n-1) without touching y=xy=x.

      All non-decreasing paths total (2n2n1)\dbinom{2n-2}{n-1}. For any path that touches y=xy=x, we can symmetrically transform the part from the point where it leaves this line to (1,0)(1,0), obtaining a non-decreasing path from (0,1)(0,1) to (n,n1)(n,n-1). The reverse is also true. Hence, the number of non-decreasing paths below y=xy=x is (2n2n1)(2n2n)\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}. Due to symmetry, the answer is 2(2n2n1)2(2n2n)2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}.

    3. The number of non-decreasing paths from (0,0)(0,0) to (n,n)(n,n) that do not cross the line y=xy=x: Similarly, we can obtain 2n+1(2nn)\dfrac{2}{n+1}\dbinom{2n}{n} using similar methods.

    NOTE: This article is rewritten by OI WIKI.