Why this matters when you build with AI
Many counting statements in contests are not new. They are a known family of numbers in a new costume: "balanced brackets", "split the students into teams", "how many ways to put items in boxes". If you recognise the family, you know the recurrence, the first values, and a brute force to test against. If you do not, you start from zero.
AI tools are good at naming these families when asked, and bad at checking that the name fits. A common failure looks like this. You ask for the number of ways to split 5 people into 2 non-empty groups, and the tool answers with the binomial C(5, 2) = 10. The answer looks plausible, and it is wrong. The true answer is S(5, 2) = 15, because the two groups are not labelled and the split (1 2 3 4 | 5) is the same as (5 | 1 2 3 4) in a different order. The only way to catch this is a brute force on n = 5. Run it, and the mismatch shows up in one minute.
This lesson covers three families: Catalan numbers, Stirling numbers, and Bell numbers. For each one you will see the statement that gives it, a recurrence (a rule that builds each value from smaller ones), a closed form (a formula that gives the value directly), and a brute force. The code is C++17. We compiled it with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2.0. The output blocks below are from our runs. The arithmetic does not depend on the machine, so your output should match them exactly.
Definitions
A recurrence is a rule that computes a value from earlier values. The Fibonacci rule F(n) = F(n-1) + F(n-2) is one.
A closed form is a formula that computes a value directly from n, without a table. For example, 1 + 2 + ... + n = n(n+1)/2 is a closed form for a running sum.
A DP (dynamic programming table) is a table filled row by row from a recurrence.
A brute force enumerates every object the statement describes and counts them. It is slow, but it is simple enough to be correct, so it is the reference you test against.
A set partition of n items is a way to split the items into groups (called blocks) so that every item is in exactly one block and no block is empty. The blocks are not labelled. The partition {1, 2}, {3} is the same as {3}, {1, 2}.
A permutation of n items is an ordering of them. Every permutation can be split into cycles. Start at item 1, follow the arrow to the position it points to, and keep going until you return. That loop is one cycle. For the permutation that sends 1 to 2, 2 to 1, and 3 to 3, the cycles are (1 2) and (3), so there are 2 cycles.
Catalan numbers
The statement that gives them
Catalan numbers count balanced bracket sequences. Take n opening brackets and n closing brackets. A sequence is balanced when every prefix has at least as many opening brackets as closing ones, and the whole sequence has equal numbers of each.
For n = 2 there are two sequences: (()) and ()(). The string )( is not allowed because its first prefix already has more closing brackets. For n = 3 there are five: ((())), (()()), (())(), ()(()), and ()()().
The same count shows up in many other statements. Triangulations of a convex polygon with n + 2 corners are counted by C(n). A walk of 2n steps, each +1 or -1, that starts at 0, ends at 0, and never goes below 0 is also counted by C(n). The idea is the same in all of them: a rule that a running total must not cross a line.
The formula and the recurrence
The Catalan number C(n) has two standard forms.
The first recurrence is C(0) = 1 and C(n+1) = the sum of C(i) times C(n-i) over i from 0 to n. To see why, split a balanced sequence by its first return to balance. It has the form ( A ) B, where A and B are balanced sequences. The sizes of A and B add up to n - 1 pairs, which gives the sum.
The closed form is C(n) = binomial(2n, n) / (n + 1). We write binomial(2n, n) for the number of ways to choose n positions out of 2n. Check n = 3: binomial(6, 3) = 20, and 20 / 4 = 5. Division by n + 1 is exact for every n.
The reflection argument
Why does the closed form work? Start with every sequence of n opening and n closing brackets, with no rule. There are binomial(2n, n) of them. Some are not balanced. Among those, look at the first position where the running total goes to -1. Swap every bracket before that position: the opening ones become closing, and the closing ones become opening. The prefix now ends at +1 instead of -1, and the sequence has n + 1 opening brackets and n - 1 closing brackets.
This swap is reversible. Every sequence with n + 1 openings and n - 1 closings has a first point where the total reaches +1, and swapping the prefix up to that point gives a sequence that goes to -1. So the bad sequences are in one-to-one match with the sequences of n + 1 openings and n - 1 closings. There are binomial(2n, n - 1) of those. So the number of balanced sequences is:
C(n) = binomial(2n, n) - binomial(2n, n - 1)
The two forms agree, because binomial(2n, n - 1) = binomial(2n, n) times n / (n + 1). Subtracting leaves binomial(2n, n) / (n + 1).
The reflection trick is the main tool in this family. You will use it again in the lattice path lesson, where a path that touches a forbidden line is swapped for a path with a different end point.
Recognising Catalan from a statement
Look for three signs. The objects are sequences built from two kinds of step, or trees with two children per node, or polygons cut by diagonals. There is a rule that a running total or a height must not cross a line. And the count is for the whole length, with both ends fixed (the sequence starts at 0 and ends at 0). If the statement lets the running total go anywhere, or lets the sequence end at any height, it is not Catalan. Then it is a binomial sum or a different count.
Stirling numbers of the second kind
The statement that gives them
S(n, k) is the number of ways to split n distinct items into exactly k non-empty blocks, where the blocks are not labelled. This is the number of set partitions into k blocks. The statement usually says "split into k non-empty groups" or "put n distinct balls into k identical boxes, no box empty".
For n = 4 the row is S(4, 1) = 1, S(4, 2) = 7, S(4, 3) = 6, S(4, 4) = 1. Check S(4, 2) by hand. The partitions of {1, 2, 3, 4} into two blocks are: one block of size 1 and one of size 3 (4 ways), and two blocks of size 2 (3 ways). That is 4 + 3 = 7.
The DP
The recurrence is S(n, k) = k times S(n-1, k) + S(n-1, k-1), with S(0, 0) = 1 and S(n, 0) = 0 for n >= 1. Look at item n. Either it joins one of the k existing blocks of a partition of the first n - 1 items, which gives k times S(n-1, k) choices, or it forms a block by itself, which gives S(n-1, k-1) choices.
Here is the table from our run, rows 0 to 6:
1
0 1
0 1 1
0 1 3 1
0 1 7 6 1
0 1 15 25 10 1
0 1 31 90 65 15 1Row 5 adds up to 52, which is the Bell number B(5). Section on Bell numbers explains why.
The closed form
The closed form is:
S(n, k) = (1 / k!) times the sum over j from 0 to k of (-1)^(k-j) times binomial(k, j) times j^n
The idea is inclusion-exclusion. Assign each item one of j labelled boxes, for any j. That gives j^n assignments, and with the sign and binomial it counts the ways that use every one of k labelled boxes. Dividing by k! removes the labels from the boxes. The formula is exact, and it is safe to compute modulo a prime p when k < p, because k! has an inverse.
Check S(4, 2): the sum is binomial(2,0) times 0^4 with sign +, minus binomial(2,1) times 1^4, plus binomial(2,2) times 2^4. That is 0 - 2 + 16 = 14. Divide by 2! = 2 to get 7.
Forgetting the sign is a common error. Without the sign the same sum is 0 + 2 + 16 = 18, and 18 / 2 = 9. Nothing crashes and the number looks reasonable, so only a brute force finds it.
Recognising Stirling second kind
Look for "distinct items", "non-empty", and "groups that are not labelled or ordered". If the statement names the groups (team A and team B), the count is not S(n, k), it is k! times S(n, k). If the statement wants at most k groups, sum S(n, j) over j from 0 to k.
Stirling numbers of the first kind (unsigned)
The statement that gives them
c(n, k) is the number of permutations of n items that have exactly k cycles. We use the unsigned version, which is the count without any sign. The statement usually says "arrange n people in a circle, forming k circles" or "count permutations by number of cycles".
The recurrence is c(n, k) = (n - 1) times c(n-1, k) + c(n-1, k-1), with c(0, 0) = 1. Item n either goes into an existing cycle, in one of n - 1 places after another item, or forms a cycle by itself.
From our run, rows 0 to 5:
1
0 1
0 1 1
0 2 3 1
0 6 11 6 1
0 24 50 35 10 1Each row adds up to n!. Row 4 gives 6 + 11 + 6 + 1 = 24, which is 4!. That is a useful check: a wrong table rarely has the right row sum.
The closed form is not needed in contests for this family. Its generating function is a product of linear factors, which the generating functions lesson covers. For this lesson, the DP and the brute force over permutations are enough.
Recognising Stirling first kind
Look for permutations, cycles, or circular arrangements. If the statement asks for permutations sorted by how many cycles they have, it is c(n, k).
Bell numbers
The statement that gives them
The Bell number B(n) is the number of set partitions of n items with any number of blocks. It is the sum of S(n, k) over all k:
B(n) = the sum of S(n, k) for k from 0 to n
The values start 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 for n = 0 to 10. The values grow faster than exponentially, so a contest that asks for B(n) gives a small n or a modulus.
A Bell triangle computes B(n) without Stirling numbers at all. Start with the row [1]. Each new row starts with the last number of the row above. Each further number is the sum of the number on its left and the number above that position. The first number of row n is B(n).
Output from our run:
row 4 of S(n, k): [0, 1, 7, 6, 1]
row 5 of S(n, k): [0, 1, 15, 25, 10, 1]
Bell numbers B(0..10): [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]
sum of row 5 equals B(5): TrueClosed forms for Bell numbers
Dobinski's formula gives B(n) as an infinite sum, B(n) = (1/e) times the sum over j of j^n / j!, where e is the number 2.71828... This is a true identity, but it uses real numbers and an infinite sum, so it is not usable in a contest. The practical closed form is the sum of the Stirling closed form over k, which is exact and works modulo a prime. The cross-check in the next section does exactly this.
Recognising Bell numbers
Look for "partition", "group the items in any way", or "any number of teams". If the statement fixes the number of groups, use S(n, k) instead. If it fixes the group sizes, use a multinomial coefficient instead.
How to recognise each family
Read the statement and ask three questions.
- Are the groups labelled or ordered? Labelled groups multiply by k!. Groups with no names are the unlabelled case.
- Is the object a split of items into blocks, a permutation with cycles, or a sequence with a running total that must not cross a line?
- Is the number of blocks or cycles fixed, or is it summed?
A table of the answers:
- Balanced sequences, paths that stay above a line, polygon triangulations, full binary trees: Catalan C(n).
- Split n distinct items into exactly k unlabelled, non-empty groups: S(n, k).
- Permutations with exactly k cycles, or circular arrangements in k circles: c(n, k).
- Split n distinct items into any number of groups: B(n).
Standard technique
The standard approach for each family is the same: a DP table for small n, a closed form for large n, and a brute force for the tests. The code below holds the parts you use in a contest. Put them in one file, and the cross-check at the end runs all three methods on the same values.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll pow_mod(ll a, ll e, ll m) {
ll r = 1 % m;
a %= m;
if (a < 0) a += m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}
// Factorials and inverse factorials modulo MOD, for 0 <= n <= N, with N < MOD.
struct Fact {
vector<ll> f, fi;
explicit Fact(int N) : f(N + 1), fi(N + 1) {
f[0] = 1;
for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
fi[N] = pow_mod(f[N], MOD - 2, MOD);
for (int i = N; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
}
ll C(int n, int k) const {
if (k < 0 || k > n) return 0;
return f[n] * fi[k] % MOD * fi[n - k] % MOD;
}
};
// Catalan: DP by C(n+1) = sum of C(i) * C(n-i), modulo MOD. O(N^2).
vector<ll> catalan_dp_mod(int N) {
vector<ll> C(N + 1, 0);
C[0] = 1;
for (int n = 0; n < N; n++)
for (int i = 0; i <= n; i++) C[n + 1] = (C[n + 1] + C[i] * C[n - i]) % MOD;
return C;
}
// Catalan: closed form C(2n, n) / (n + 1), modulo MOD.
ll catalan_closed_mod(const Fact& F, int n) {
return F.C(2 * n, n) * pow_mod(n + 1, MOD - 2, MOD) % MOD;
}
// Stirling second kind: DP by S(n, k) = k * S(n-1, k) + S(n-1, k-1), modulo MOD.
vector<vector<ll>> stirling2_dp(int N) {
vector<vector<ll>> S(N + 1, vector<ll>(N + 1, 0));
S[0][0] = 1;
for (int n = 1; n <= N; n++)
for (int k = 1; k <= n; k++) S[n][k] = (k * S[n - 1][k] + S[n - 1][k - 1]) % MOD;
return S;
}
// Stirling second kind: closed form (1 / k!) * sum of (-1)^(k-j) * C(k, j) * j^n.
ll stirling2_closed(const Fact& F, int n, int k) {
ll s = 0;
for (int j = 0; j <= k; j++) {
ll term = F.C(k, j) * pow_mod(j, n, MOD) % MOD;
if ((k - j) & 1) s = (s - term + MOD) % MOD;
else s = (s + term) % MOD;
}
return s * F.fi[k] % MOD;
}
// Bell numbers: Bell triangle, modulo MOD. Row n starts with B(n).
vector<ll> bell_triangle_mod(int N) {
vector<ll> B(N + 1);
vector<ll> row = {1};
B[0] = 1;
for (int n = 1; n <= N; n++) {
vector<ll> nr;
nr.push_back(row.back());
for (ll x : row) nr.push_back((nr.back() + x) % MOD);
row = nr;
B[n] = row[0];
}
return B;
}
int main() {
const int N = 200;
Fact F(2 * N);
auto cat = catalan_dp_mod(N);
auto S2 = stirling2_dp(N);
auto B = bell_triangle_mod(N);
int mismatches = 0;
for (int n = 0; n <= N; n++) {
if (catalan_closed_mod(F, n) != cat[n]) mismatches++;
ll row_sum = 0;
for (int k = 0; k <= n; k++) {
ll closed = stirling2_closed(F, n, k);
if (closed != S2[n][k]) mismatches++;
row_sum = (row_sum + closed) % MOD;
}
if (row_sum != B[n]) mismatches++; // Bell = sum of Stirling over k
}
cout << "Cross-check for n <= " << N << ", mismatches: " << mismatches << "\n";
cout << "Catalan(200) mod p = " << cat[200] << "\n";
cout << "S(200, 100) mod p = " << S2[200][100] << "\n";
cout << "B(200) mod p = " << B[200] << "\n";
return 0;
}The full file we ran also has the brute force checks. It printed:
Cross-check for n <= 200, mismatches: 0
Catalan(200) mod p = 577800661
S(200, 100) mod p = 651805877
B(200) mod p = 325069421The Catalan DP and closed form are checked exactly against 64-bit values for n up to 30. The 64-bit check uses Pascal's triangle for the binomials, so it does not depend on the modular inverse. Our brute force runs covered:
- Catalan, by stepping through all 2^(2n) sequences of +1 and -1, for n up to 9. Matches the DP.
- Stirling second kind, by listing all restricted growth strings for n up to 8, where a restricted growth string gives each item a block number no larger than one more than the largest used so far. Each string is one set partition. Matches the DP for every n and k.
- Stirling first kind, by listing all permutations of n up to 8 and counting cycles. Matches the DP.
Worked problem: team split
Statement (our own wording). There are n students, numbered 1 to n. Split them into exactly k non-empty teams. The teams have no names, and the order of the students inside a team does not matter. Print the number of ways modulo 998244353. Input is two integers n and k with 1 <= k <= n <= 2000.
Recognition. Distinct items, non-empty, unlabelled groups, fixed number of groups. This is S(n, k).
Solution. Use the recurrence with one row. The table is n by k, which is 2000 by 2000 at most, and the answer needs only one entry. Keep one array S of size k + 1 that holds the row for the current i. Going from row i - 1 to row i, update j from high to low, so that S[j - 1] still holds the old value when S[j] reads it. That is the same trick as a 0/1 knapsack.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
int main() {
int n, k;
cin >> n >> k;
// S[j] holds S(i, j) for the current i. Going from i - 1 to i in place,
// j runs downward so S[j - 1] still holds the old value when it is read.
vector<ll> S(k + 1, 0);
S[0] = 1; // S(0, 0) = 1
for (int i = 1; i <= n; i++) {
for (int j = min(i, k); j >= 1; j--) S[j] = (j * S[j] + S[j - 1]) % MOD;
S[0] = 0; // S(i, 0) = 0 for i >= 1
}
cout << S[k] << "\n";
return 0;
}Compiled and run on the sample inputs:
input [5 2] -> 15
input [5 3] -> 25
input [4 4] -> 1
input [6 3] -> 90
input [2000 1000] -> 272019032
input [2000 2000] -> 1
input [1 1] -> 1
input [3 5] -> 0The input "3 5" has k larger than n, so the answer is 0. The statement forbids that case, but the program handles it anyway because j never goes past i.
Test. We wrote a Python brute force that lists all restricted growth strings for n up to 8 and all k, plus 30 random cases with n up to 9. It runs the C++ program on each case and compares. Result: 66 cases checked, 0 mismatches.
Complexity. Time O(n k), which is about 4 million steps at the limits. Memory O(k).
Common mistakes
Mixing up labelled and unlabelled groups. The answer for named teams is k! times S(n, k). Symptom: your answer is exactly k! times the expected value. For 5 students in 2 teams, the sample answer is 15, and the labelled answer would be 30.
Forgetting the sign in the closed form. Symptom: S(4, 2) prints 9 instead of 7. The formula with no sign gives this number, and it looks plausible, so the only catch is a brute force.
Using the binomial for a set partition count. Symptom: "5 people in 2 teams" gives 10 instead of 15. The binomial counts choices of one team, not splits.
Dividing by k! when k is at least p. The inverse of k! does not exist modulo p when k >= p. For p = 998244353 and k up to 2000 this does not happen, but a statement with k up to 10^9 needs another method.
Off-by-one in the Catalan closed form. Symptom: C(3) prints 20. The number 20 is binomial(6, 3), and you forgot to divide by n + 1 = 4.
Row order in the in-place DP. If you update j upward, S[j - 1] has already changed for this row, and the table gives wrong values. The fix is the downward loop.
Confusing the recurrence with the row sum. The row sum of S(n, k) over k is B(n), not C(n). Symptom: a Bell check that compares against Catalan values.
Checklist
- Write the statement's small cases by hand, for n = 2 and 3, before you pick a family.
- Ask whether the groups are labelled or ordered. Labelled groups add a factor of k!.
- Ask whether the number of groups is fixed (S(n, k)), summed (B(n)), or whether it is cycles (c(n, k)).
- For a Catalan count, check that the running total is fixed at both ends and must not cross a line.
- Compare the DP with the closed form on n up to 200 before you trust either.
- Check the row sum: the sum of S(n, k) over k is B(n), and the sum of c(n, k) over k is n!.
- Write a brute force for n up to 8 or 9, and run it against the solution on random inputs.
- Keep the modulus prime and larger than every factorial you invert.
Exercise
Write a program that prints, for n from 1 to 200, the three values Catalan(n) mod 998244353, S(n, n // 2) mod 998244353, and B(n) mod 998244353. Compute each one twice: once by the DP and once by the closed form. Print the number of mismatches. Then write the brute force for n up to 8 and check the first 9 lines of your output against it.
Prompt to use with an AI tool, if you want help:
Write C++17 code that computes Catalan numbers C(n) modulo 998244353 for n up to 200,
both by the recurrence C(n+1) = sum of C(i) * C(n-i) and by the closed form
binomial(2n, n) / (n + 1). Also compute Stirling numbers of the second kind S(n, k)
modulo the same prime by the DP S(n,k) = k*S(n-1,k) + S(n-1,k-1), and by the closed
form (1/k!) * sum over j of (-1)^(k-j) * binomial(k, j) * j^n. Print the number of
mismatches. Do not use any library beyond the standard library. Show the brute force
for n up to 8 as a separate function. Explain any step that depends on the modulus
being prime.A good answer uses the same modulus everywhere, computes factorials up to 2n, and handles k = 0 and j = 0 with 0^0 = 1. Check that the tool's Stirling closed form gives 7 for S(4, 2), and that its Catalan closed form gives 5 for n = 3. If the tool's answer does not match the brute force on n up to 8, do not use it.
Your own run is the answer key here. The values in this lesson cover only the first rows.
Practice problems
Problem 1. How many balanced bracket sequences with 4 pairs exist, and how many ways are there to split 6 distinct people into exactly 3 non-empty unlabelled teams?
Hint: C(4) is in the Catalan list, and S(6, 3) is in the row we printed for n = 6.
Show the answer
C(4) = 14 and S(6, 3) = 90. The Catalan value is 14, from the list 1, 1, 2, 5, 14. The Stirling value is the entry at k = 3 in row 6 of the table.
Problem 2. Count the permutations of 5 items with exactly 2 cycles. Then count the set partitions of 10 items into exactly 4 blocks.
Hint: The first is c(5, 2), in row 5 of the first kind table. The second is S(10, 4). Check the second with the DP or the Python sample.
Show the answer
c(5, 2) = 50, from row 5 of the unsigned table: 0, 24, 50, 35, 10, 1. S(10, 4) = 34105, checked by a separate DP in our run.
Problem 3. How many ways are there to triangulate a convex hexagon? Then count the lattice paths from (0, 0) to (n, n) with steps right and up that never go above the line y = x + 1, for n = 5.
Hint: A hexagon has 6 corners, so use C(4), because a polygon with n + 2 corners gives C(n). For the paths, the reflection argument across the line y = x + 2 gives binomial(2n, n) minus binomial(2n, n - 2).
Show the answer
Triangulations of a hexagon: 14, which is C(4). Paths for n = 5: binomial(10, 5) - binomial(10, 3) = 252 - 120 = 132. A brute force over all paths for n = 1 to 8 matched the formula in our run.
Problem 4. Find B(12), and check it against the sum of the Stirling numbers in row 12.
Hint: Use the Bell triangle for B(12), then check that the row 12 entries of the Stirling table add up to the same number.
Show the answer
B(12) = 4213597. The row sum of S(12, k) over k from 0 to 12 is 4213597 too. Our run gave S(12, 4) = 611501 as one entry of that row.
Summary
Catalan numbers count balanced sequences and polygon triangulations, and they follow the recurrence C(n+1) = sum of C(i) C(n-i), with the closed form binomial(2n, n) / (n + 1), which the reflection argument proves. Stirling numbers of the second kind count splits of distinct items into k unlabelled, non-empty groups, and they follow S(n, k) = k S(n-1, k) + S(n-1, k-1), with a closed form that uses an alternating sum. Stirling numbers of the first kind count permutations by cycles, and Bell numbers add the second kind over all k. Each family has a DP and a closed form, and a brute force for small n. When two methods disagree, the disagreement is the sign that one of them has a bug.