Combinatorics

Counting Combinations

Cnk=Ankk!=n!k!⋅(n−k)!=(n−k+1)⋅(n−k+2)⋯nk!C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k! \cdot (n - k)!} = \frac{(n-k+1)\cdot(n-k+2)\cdots n}{k!}

When n is small -- Iteration

We can use the following equation:

Cnk=(n−k+1)⋅(n−k+2)⋯nk!=n−k+11⋅n−k+22⋯nkC_n^k = \frac{(n-k+1)\cdot(n-k+2)\cdots n}{k!} = \frac{n-k+1}{1}\cdot\frac{n-k+2}{2}\cdots\frac{n}{k}

We compute from the smaller side $\frac{n-k+1}{1}$ to avoid the potential non-divisible error caused by $\frac{n}{k}$.

// Author: github.com/lzl124631x
// Time: O(min(K, N - K))
// Space: O(1)
int combination(int n, int k) {
    k = min(k, n - k); // Since we loop in range [1, k], we make sure `k` is smaller than `n - k`
    long ans = 1;
    for (int i = 1; i <= k; ++i) {
        ans = ans * (n - k + i) / i; // compute from the smaller side
    }
    return ans;
}

Try this in 62. Unique Paths (Medium)

When n is large -- Dynamic Programming

To avoid overflow, we will be asked to return the answer modulo some prime number (1e9+7 on LeetCode).

We can't change the above solution to ans = ans * (n - k + i) / i % mod because after a previous modulo operation, ans * (n - k + i) might not be divisible by i.

We need to use this equation:

Cnk=Cn−1k−1+Cn−1kC_n^k = C_{n-1}^{k-1} + C_{n-1}^k

Memo: Picking k elements from n elements is the same as the sum of the following:

  1. Pick the first element, and pick k - 1 elements from the rest n - 1 elements, i.e. $C_{n-1}^{k-1}$

  2. Skip the first element, and pick k elements from the rest n - 1 elements, i.e. $C_{n-1}^k$

This can be computed using Pascal Triangle and Dynamic Programming.

  k  0  1  2  3  4
n  _______________
0 |  1  0  0  0  0
1 |  1  1  0  0  0
2 |  1  2  1  0  0
3 |  1  3  3  1  0
4 |  1  4  6  4  1
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
dp[i][0] = 1

And the answer is dp[n][k].

// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(K * (N - K))
int combination(int n, int k, int mod) {
    k = min(k, n - k);
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
        }
    }
    return dp[n][k];
}

Since dp[i][j] only depends on dp[i-1][j-1] and dp[i-1][j], we can use 1D array to store the DP values. The answer is dp[k].

// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(min(K, N - K))
int combination(int n, int k, int mod) {
    k = min(k, n - k);
    vector<int> dp(k + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = min(i, k); j > 0; --j) {
            dp[j] = (dp[j] + dp[j - 1]) % mod;
        }
    }
    return dp[k];
}

Try this in 1569. Number of Ways to Reorder Array to Get Same BST (Hard)

Sum of combinations

We can use the following equation to get some useful conclusions:

(a+b)n=Cn0⋅a0⋅bn+Cn1⋅a1⋅bn−1+⋯+Cnn⋅an⋅b0(a + b)^n = C_n^0\cdot a^0\cdot b^n + C_n^1\cdot a^1\cdot b^{n-1} + \dots + C_n^n\cdot a^n\cdot b^0

Let a = 1, b = 1, we have

Cn0+Cn1+Cn2+⋯+Cnn−1+Cnn=2nC_n^0 + C_n^1 + C_n^2 + \dots + C_n^{n-1} + C_n^n = 2^n

Let a = 1, b = -1, we have

Cn0−Cn1+Cn2−Cn3+Cn4−Cn5+⋯=0C_n^0 - C_n^1 + C_n^2 - C_n^3 + C_n^4 - C_n^5 + \dots = 0

So

∑pCnp=∑qCnq=2n−1\sum_{p}C_n^p = \sum_{q}C_n^q = 2^{n-1}

where p and q represent all the even and odd numbers in [0, n], respectively.

We can use this trick in 1863. Sum of All Subset XOR Totals (Easy)

Problems

Generating Combinations

Problems

PreviousCatalan NumberNextFactorial

Last updated