Sequences (2): Catalan numbers

The following problems belong to the Catalan sequence:

1. Yes $2n$ Individuals line up to enter the theater. Admission is $5. Among them only $n$ The individual has a 5 dollar bill and another $n$ People only have 10 yuan bills, and there are no other bills in the theater. How many ways are there so that as long as 10 yuan people buy tickets, there will be 5 yuan bills in change at the box office?
2. A big-city lawyer lives just north of her home $n$ blocks and east of $n$ Work in blocks. Every day she goes $2n$ blocks to work. If he never crosses (but can hit) the diagonal from home to office, how many possible paths are there?
3. Select on circle $2n$ points, connect these points in pairs so that the obtained $n$ How many ways can line segments not intersect?
4. How many ways are there to divide a convex polygon area into triangular areas when the diagonals do not intersect?
5. The push sequence of a stack (infinity) is $1,2,3, \cdots ,n$ How many different pop sequences are there?
6. $n$ How many different binary trees can be constructed from each node?
7. $n$ a $+1$ and $n$ a $-1$ constitute $2n$ item $a_1,a_2, \cdots ,a_{2n}$, its parts and satisfies $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ Correspondence $n$ What is the number?

The corresponding sequence is:

(Catalan sequence)

# Recursive

The solution to this recurrence relation is:

$$H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})$$

Common formulas for Catalan numbers:

$$H_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}$$

$$H_n = \frac{H_{n-1} (4n-2)}{n+1}$$

$$H_n = \binom{2n}{n} - \binom{2n}{n-1}$$

The main idea of ​​the question: The order of pushing onto the stack is $1,2,\ldots,n$, find the total number of all possible popping orders.

// C++ Version
#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); // Common formula 2 is used here cout << f[n] << endl; return 0;
}

# path counting problem

A non-descending path is a path that can only go up or to the right.

1. from $(0,0)$ Arrive $(m,n)$ The number of non-descending paths is equal to $m$ a $x$ and $n$ a $y$ The number of permutations, that is $\dbinom{n + m}{m}$。

2. from $(0,0)$ Arrive $(n,n)$ does not touch the straight line except for the endpoints $y=x$ The number of non-descending paths:

   Consider first $y=x$ The paths below all start from $(0, 0)$ set off, pass $(1, 0)$ and $(n, n-1)$ Arrive $(n,n)$, can be seen as $(1,0)$ Arrive $(n,n-1)$ no contact $y=x$ The number of non-descending paths.

   All non-descending paths have $\dbinom{2n-2}{n-1}$ article. Have any contact with any of these? $y=x$ path, you can take its last point leaving this line to $(1,0)$ between the parts about $y=x$ Symmetric transformation, we get from $(0,1)$ Arrive $(n,n-1)$ a non-descending path. The reverse is also true. Thus $y=x$ The number of non-descending paths below is $\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}$. According to the symmetry, the answer is $2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}$。

3. from $(0,0)$ Arrive $(n,n)$ does not pass through a straight line except for the endpoints $y=x$ The number of non-descending paths:

   You can get it in a similar way:$\dfrac{2}{n+1}\dbinom{2n}{n}$