Pattern Guide
Advanced Counting DP
"Partition numbers, Bell numbers, Stirling numbers. DP on combinatorial structures."
Advanced counting DP computes partition numbers (ways to write n as sum of positive integers), Bell numbers (ways to partition a set), and Stirling numbers (partitions into k non-empty subsets). Also covers: counting sequences with forbidden patterns, DP on generating functions, and transfer matrix method. Essential for combinatorics competition problems.
Problems you can solve with this pattern
4 problems · click any to start solving
// Integer partition: ways to write n as sum of positive integers, largest part ≤ k
function partition(n, k = n) {
// dp[i][j] = ways to partition i using parts ≤ j
const dp = Array.from({length: n+1}, () => new Array(n+1).fill(0));
for (let j = 0; j <= n; j++) dp[0][j] = 1;
for (let i = 1; i <= n; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = dp[i][j-1] + (i >= j ? dp[i-j][j] : 0);
return dp[n][k];
}
// Stirling numbers of the second kind: S(n,k) = ways to partition n elements into k subsets
function stirling2(maxN) {
const S = Array.from({length: maxN+1}, () => new Array(maxN+1).fill(0));
S[0][0] = 1;
for (let n = 1; n <= maxN; n++)
for (let k = 1; k <= n; k++)
S[n][k] = k * S[n-1][k] + S[n-1][k-1];
return S;
}
// Bell numbers: B(n) = Σ S(n,k) for k=0..n = total set partitions
function bell(maxN) {
const S = stirling2(maxN);
return Array.from({length: maxN+1}, (_, n) =>
S[n].reduce((a, b) => a + b, 0));
}
// Bell triangle: efficient O(n²) Bell number computation
function bellTriangle(n) {
const row = [1];
const bells = [1];
for (let i = 1; i <= n; i++) {
const next = [row[row.length - 1]];
for (let j = 1; j <= i; j++)
next.push(next[j-1] + row[j-1]);
bells.push(next[i]);
row.length = 0; row.push(...next);
}
return bells;
}Partition numbers p(n): ways to write n as an ordered sum (compositions) or unordered sum (partitions). Compositions of n: 2^(n-1). Integer partitions: recurrence p(n,k) = p(n-k,k) + p(n,k-1) (use k or don't use k). Bell numbers B(n) = total ways to partition a set of n elements = Σ S(n,k) for all k. Stirling numbers S(n,k) = ways to partition n-set into exactly k non-empty subsets. Recurrence: S(n,k) = k×S(n-1,k) + S(n-1,k-1).
// Integer partition: ways to write n as sum of positive integers, largest part ≤ k
function partition(n, k = n) {
// dp[i][j] = ways to partition i using parts ≤ j
const dp = Array.from({length: n+1}, () => new Array(n+1).fill(0));
for (let j = 0; j <= n; j++) dp[0][j] = 1;
for (let i = 1; i <= n; i++)
for (let j = 1; j <= n; j++)
dp[i][j] = dp[i][j-1] + (i >= j ? dp[i-j][j] : 0);
return dp[n][k];
}
// Stirling numbers of the second kind: S(n,k) = ways to partition n elements into k subsets
function stirling2(maxN) {
const S = Array.from({length: maxN+1}, () => new Array(maxN+1).fill(0));
S[0][0] = 1;
for (let n = 1; n <= maxN; n++)
for (let k = 1; k <= n; k++)
S[n][k] = k * S[n-1][k] + S[n-1][k-1];
return S;
}
// Bell numbers: B(n) = Σ S(n,k) for k=0..n = total set partitions
function bell(maxN) {
const S = stirling2(maxN);
return Array.from({length: maxN+1}, (_, n) =>
S[n].reduce((a, b) => a + b, 0));
}
// Bell triangle: efficient O(n²) Bell number computation
function bellTriangle(n) {
const row = [1];
const bells = [1];
for (let i = 1; i <= n; i++) {
const next = [row[row.length - 1]];
for (let j = 1; j <= i; j++)
next.push(next[j-1] + row[j-1]);
bells.push(next[i]);
row.length = 0; row.push(...next);
}
return bells;
}- Integer compositions of n: 2^(n-1)
- Integer partitions: recurrence dp[n][k] = dp[n-k][k] + dp[n][k-1]
- Distribute n identical balls into k distinct boxes (≥0 each): C(n+k-1,k-1) — stars and bars
- Distribute n into k boxes (≥1 each): C(n-1,k-1)
- Stirling second kind: S(n,k) = k×S(n-1,k) + S(n-1,k-1)
- Bell number: B(n) = Σₖ S(n,k) = total set partitions