Core Logic and Mathematical Principles
1. Catalan Number
The Catalan number is one of the most frequently encountered special counting sequences in combinatorial mathematics. Let the $n$-th term be denoted as $H_n$, with the standard formula given by:
$$H_n = \frac{C_{2n}^n}{n + 1} = C_{2n}^n - C_{2n}^{n-1}$$
The general term satisfies the following efficient algebraic recurrence relation:
$$H_n = \frac{4n - 2}{n + 1} H_{n-1} \, (H_0 = 1)$$
Proof via Lattice Path Model
In the Cartesian coordinate system, starting from $(0,0)$, if one can only move right or up by 1 unit at a time, we seek the number of non-decreasing paths to $(n,n)$ such that for any point $(x,y)$ on the path, $x \geq y$ (i.e., not crossing the line $y=x$).
- Total unrestricted paths: This is equivalent to choosing $n$ right moves from $2n$ total steps, giving a total of $C_{2n}^n$.
- Illegal paths: Any path that crosses $y=x$ must touch or exceed the line $y=x+1$. Let the first point where an illegal path touches $y=x+1$ be $P$. Reflect the path after point $P$ across the line $y=x+1$.
- After reflection, the endpoint $(n,n)$ will be symmetrically mapped to $(n-1, n+1)$. Since each illegal path that touches $y=x+1$ to reach $(n,n)$ corresponds uniquely to a path reaching $(n-1, n+1)$, the total number of illegal paths is $C_{2n}^{n-1}$. Subtracting the illegal paths from the total paths gives the standard term $C_{2n}^n - C_{2n}^{n-1}$.
2. Stirling Number of the First Kind
The signed Stirling number of the first kind $\begin{bmatrix} n \\ k \end{bmatrix}$ (denoted as $s(n,k)$) represents the number of ways to arrange $n$ distinct elements into $k$ mutually disjoint circular arrangements (cycles). Its state combination recurrence relation is given by:
$$\begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + (n-1) \cdot \begin{bmatrix} n-1 \\ k \end{bmatrix}$$
- Base Case: $\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1$, and if $n > 0$, then $\begin{bmatrix} n \\ 0 \end{bmatrix} = 0$.
3. Stirling Number of the Second Kind
The second kind Stirling number $\begin{Bmatrix} n \\ k \end{Bmatrix}$ (denoted as $S(n,k)$) represents the number of ways to partition $n$ distinct elements into $k$ non-empty indistinguishable subsets (sets). Its state merging recurrence relation is given by:
$$\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix} + k \cdot \begin{Bmatrix} n-1 \\ k \end{Bmatrix}$$
- Base Case: $\begin{Bmatrix} 0 \\ 0 \end{Bmatrix} = 1$, and if $n > 0$, then $\begin{Bmatrix} n \\ 0 \end{Bmatrix} = 0$.
State Design and Algorithm Derivation
In NOIP practical contests, for counting problems like Stirling numbers that exhibit obvious two-dimensional dependency characteristics, a dynamic programming two-dimensional table filling method is typically employed.
1. State Derivation Logic Analysis for Second Kind Stirling Numbers
Consider the direction of the $n$-th element (the newly added element):
- Independently forming a set: This element occupies a new set by itself. In this case, the previous $n-1$ elements must form $k-1$ sets, giving a count of $\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$.
- Integrating into an old set: The new element is forcibly inserted into one of the existing $k$ sets. Since the sets are distinguishable (because the internal elements are different), there are $k$ strategies to insert it. The number of ways is $k \cdot \begin{Bmatrix} n-1 \\ k \end{Bmatrix}$. Using the addition principle, the two counts are summed to complete the state transition.
2. State Derivation Logic Analysis for First Kind Stirling Numbers
Consider the direction of the $n$-th element in the circular arrangement:
- Independently forming a cycle: It forms a single-element cycle by itself. The number of ways is $\begin{bmatrix} n-1 \\ k-1 \end{bmatrix}$.
- Inserting into an old cycle: The new element is inserted into one of the existing $k$ circular arrangements. It can be inserted to the left (or right) of any existing element, and since there are $n-1$ predecessors, there are $n-1$ insertion positions. The number of ways is $(n-1) \cdot \begin{bmatrix} n-1 \\ k \end{bmatrix}$.
C++ Standard Source Code
#include <iostream>
#include <vector>
const int MOD = 1000000007;
const int MAXN = 2000;
long long catalan[MAXN + 5];
long long S2[MAXN + 5][MAXN + 5];
long long S1[MAXN + 5][MAXN + 5];
// Preprocess Catalan numbers using linear recurrence
void init_catalan(int n) {
catalan[0] = 1;
catalan[1] = 1;
// Use Fermat's little theorem to find the inverse of the denominator for single-point linear derivation
auto quick_power = [](long long base, long long exp) {
long long res = 1;
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
};
for (int i = 2; i <= n; ++i) {
long long inv = quick_power(i + 1, MOD - 2);
catalan[i] = (4 * i - 2) * catalan[i - 1] % MOD * inv % MOD;
}
}
// Preprocess the matrices of the two kinds of Stirling numbers
void init_stirling(int n) {
S1[0][0] = 1;
S2[0][0] = 1;
for (int i = 1; i <= n; ++i) {
S1[i][0] = 0;
S2[i][0] = 0;
for (int j = 1; j <= i; ++j) {
// State transition for the first kind Stirling number
S1[i][j] = (S1[i - 1][j - 1] + (i - 1) * S1[i - 1][j]) % MOD;
// State transition for the second kind Stirling number
S2[i][j] = (S2[i - 1][j - 1] + j * S2[i - 1][j]) % MOD; // Critical point: the multiplier here is j, not i-1
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
init_catalan(MAXN);
init_stirling(MAXN);
int n, k;
if (std::cin >> n >> k) {
if (n <= MAXN && k <= n) {
std::cout << "Catalan(" << n << ") = " << catalan[n] << "\n";
std::cout << "S1(" << n << "," << k << ") = " << S1[n][k] << "\n";
std::cout << "S2(" << n << "," << k << ") = " << S2[n][k] << "\n";
}
}
return 0;
}
NOIP Practical Contest Pitfall Guide
- Confusing the transition multipliers of the first and second kind Stirling numbers Contestants often misremember the multipliers under pressure. The first kind multiplies by the total number of predecessors $(i - 1)$ (representing the number of insertion positions), while the second kind multiplies by the current target set count $j$ (representing the number of chosen subsets). If these two numbers are swapped, the data characteristics of the recurrence table will undergo fundamental changes.
- Forgetting to compute the inverse in the linear recurrence of Catalan numbers leading to integer division truncation
In the formula $H_n = \frac{4n-2}{n+1} H_{n-1}$, the numerator is divided by $n+1$. In modular arithmetic, directly using the C++
/operator effectively truncates the intermediate result, rather than performing modular division. One must correctly compute the inverse of $(n + 1)$ under modulo $MOD$ using fast exponentiation before executing multiplication.
Classic NOIP/Luogu Problems
1. Luogu P3941 Entering the Formation / Variant Luogu P5386 [CERC2018] Game on Tree (involving second kind Stirling numbers)
- Problem Description: Determine the number of ways to place $n$ distinct balls into $m$ indistinguishable boxes, ensuring no box is empty.
- Essence of the Problem: The pure definition of the second kind Stirling numbers is applied.
- Core Solution Idea: Since the balls are distinct and the boxes indistinguishable, and the constraint is that no box can be empty, this perfectly aligns with the basic model of the second kind Stirling number $\begin{Bmatrix} n \\ m \end{Bmatrix}$. If the problem were modified to “boxes are distinguishable,” simply multiply the computed Stirling number by the factorial of the number of boxes $m!$.
2. Luogu P1655 The Child's Balls
- Problem Description: $N$ distinct balls are placed into $M$ indistinguishable boxes. Find the number of arrangements. There are no empty box restrictions, but the data range requires high-precision handling.
- Essence of the Problem: High-precision filling of second kind Stirling numbers under non-prime modulus constraints.
- Core Solution Idea: If the problem explicitly allows empty boxes, we only need to enumerate the actual effective number of boxes $k$ (looping from $1$ to $M$), and the total number of arrangements will be $\sum_{k=1}^M \begin{Bmatrix} N \\ k \end{Bmatrix}$. If no modulus is given and the range is large, the transition equations in the above source code need to be modified for high-precision addition and high-precision multiplication during recurrence.