Advanced Counting DP

// 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;
}