∑MathIntermediate

Permutations and Combinations

Key Points

  • •
    Permutations count ordered selections, while combinations count unordered selections.
  • •
    The core formulas are P(n,k) = n!/(n-k)! and C(n,k) = n!/(k!(n-k)!).
  • •
    Pascal’s identity C(n,k) = C(n-1,k-1) + C(n-1,k) builds binomial coefficients bottom-up.
  • •
    Symmetry C(n,k) = C(n,n-k) halves the work and reduces overflow risk.
  • •
    In competitive programming, compute C(n,k) modulo a prime using precomputed factorials and inverse factorials for O(1) queries.
  • •
    Use Fermat’s little theorem mod p to compute modular inverses when p is prime.
  • •
    For many queries, precomputation is O(N) time and space; each query is O(1).
  • •
    For one-off queries with small k, use an O(k) multiplicative method to avoid heavy precomputation.

Prerequisites

  • →Modular arithmetic — Combination computations in programming are usually done modulo a prime to avoid overflow.
  • →Exponentiation by squaring — Efficiently computes modular inverses via Fermat’s little theorem in O(log p) time.
  • →Factorials and recursion — Understanding n! and its growth is fundamental to defining P(n,k) and C(n,k).
  • →Time and space complexity — Choosing among precomputation, DP, or multiplicative methods depends on constraints.
  • →Arrays and vectors in C++ — Storing factorials, inverse factorials, and DP tables requires basic container skills.
  • →Integer overflow and data types — Avoids common bugs when dealing with large intermediate values.
  • →Basic combinatorial reasoning — Clarifies when to use permutations vs. combinations and how identities arise.

Detailed Explanation

Tap terms for definitions

01Overview

Permutations and combinations are the fundamental tools for counting how many ways we can choose objects from a set, with and without regard to order. If order matters, we count permutations; if order does not matter, we count combinations. These counts appear everywhere: arranging books on a shelf, picking a team from a class, or determining the number of shortest paths in a grid. Formally, the number of ordered selections of k elements from n distinct elements is P(n,k) = n!/(n−k)!, and the number of unordered selections is C(n,k) = n!/(k!(n−k)!). These formulas encapsulate different constraints (order vs. no order) but are tightly related: P(n,k) = C(n,k)·k!. In algorithms and competitive programming, we often need to compute these values modulo a prime number (like 1,000,000,007) to avoid overflow and keep numbers manageable. Efficient computation relies on identities like Pascal’s identity and symmetry, as well as modular arithmetic techniques. For many queries on large ranges, we precompute factorials and inverse factorials to answer C(n,k) and P(n,k) in O(1) per query after an O(N) setup. For single or small-k queries, multiplicative formulas provide O(k) solutions that avoid big tables. Understanding these concepts bridges discrete math with practical algorithm design, enabling fast solutions to counting problems.

02Intuition & Analogies

Imagine you have a set of colorful badges and you want to pin some on your backpack. If you care about which badge goes on top, second, third, and so on, you are arranging them in order—that’s permutations. If you only care which badges you’ve chosen, not the order they appear, that’s combinations. Think of a pizza shop: choosing toppings is like combinations because mushroom–pepperoni is the same as pepperoni–mushroom—you just care which toppings ended up on the pizza, not the order you listed them. Now think of setting a password by picking k distinct letters from n possible and choosing their positions. Here, order is crucial, so this is permutations. Another analogy: climbing stairs with exact moves. If you want the number of shortest paths in a grid from the top-left to bottom-right, you must take a fixed number of right and down steps. The number of distinct paths is the number of ways to choose which steps will be “down” among the total—this is combinations C(n,k). Finally, for speed: if you will answer many questions like “how many different 5-topping pizzas can I make from 100 toppings?” it’s smart to prepare a chart of factorials and their modular inverses once (like pre-slicing all your toppings). Then every new question is just a quick sandwich-assembly: combine a few prepped ingredients to get the answer instantly.

03Formal Definition

Let n and k be nonnegative integers with 0 ≤ . The number of permutations (ordered k-selections) from an n-element set is P(n,k) = n·(n−1)·...·(n−k+1) = n!/(n−k)!, also known as the falling factorial (n)_k. The number of combinations (unordered k-selections) is C(n,k) = n!/(k!(n−k)!). These quantities satisfy identities such as symmetry C(n,k) = C(n,n−k) and Pascal’s identity C(n,k) = C(n−1,k−1) + C(n−1,k), with base C(n,0) = C(n,n) = 1. In modular arithmetic over a prime modulus p, factorials are defined modulo p, and modular inverses exist for all nonzero residues. Using Fermat’s little theorem, ≡ 1 (mod p) for a not divisible by p, so ≡ (mod p). This enables computing C(n,k) mod p via precomputed factorials fact[i] = i! mod p and inverse factorials invfact[i] = (i!)^{−1} mod p: C(n,k) ≡ fact[n]·invfact[k]·invfact[n−k] (mod p), and P(n,k) ≡ fact[n]·invfact[n−k] (mod p).

04When to Use

Use permutations when the arrangement order matters: seating people in chairs, forming ordered passwords without repetition, or scheduling ordered tasks. Use combinations when order is irrelevant: choosing a subset of team members, selecting cards from a deck, or counting lattice paths that only require choosing positions for one kind of step. In programming contests, choose among three main computational strategies: (1) Precompute factorials and inverse factorials modulo a prime when n is large (up to 10^6 or more) and you have many queries. This gives O(1) per query after O(N) preprocessing. (2) Build Pascal’s triangle (dynamic programming) when n is small (like up to a few thousand) or when you need all C(n,k) for many k; it’s also useful for educational proofs. (3) Use a multiplicative O(k) method when n is large but k is small or you only need a few queries; this avoids heavy memory and preprocessing. When working modulo a composite number, be careful—Fermat’s inverse does not apply; consider extended Euclid or prime factorization techniques. For extremely large n,k with small prime modulus, Lucas’s theorem may be appropriate. Always check constraints to pick the right tool.

⚠️Common Mistakes

• Ignoring order vs. no order: Using C(n,k) when the problem is about ordered selections (should be P(n,k)), or vice versa. Clarify whether permutations or combinations are needed first. • Overflow in factorials: n! grows extremely fast; storing exact factorials in 64-bit integers overflows quickly. In competitive programming, almost always compute results modulo a prime and avoid raw factorials beyond small n. • Forgetting symmetry: Not reducing k to min(k, n−k) can lead to extra work and even overflow in multiplicative methods. Symmetry halves the number of steps. • Wrong modular inverse: Using Fermat’s inverse a^{p−2} mod p when the modulus is not prime or when a ≡ 0 mod p. Ensure modulus is prime and the denominator is coprime to the modulus. • Insufficient precomputation size: Precomputing factorials only up to N but later querying C(n,k) for n > N. Always precompute up to the maximum needed n across all queries. • Off-by-one and invalid ranges: Not handling cases where k < 0 or k > n, which should return 0 for C(n,k) and P(n,k). Also ensure base cases like C(n,0) = 1 are handled. • Mixing integer and modular arithmetic: Doing division before taking modulo or attempting a/b mod p directly. Always replace division by multiplication with modular inverses under prime moduli.

Key Formulas

Permutation count

Explanation: Counts ordered selections of k distinct items from n. It multiplies n choices for the first position, n−1 for the second, etc.

Combination count

Explanation: Counts unordered selections of k from n. It divides out the k! reorderings of the same set to avoid overcounting.

Symmetry

Explanation: Choosing k items is equivalent to choosing which n−k items to leave out, cutting work roughly in half.

Pascal's identity

Explanation: Either include a particular element (then choose k−1 from n−1) or exclude it (choose k from the remaining n−1).

Factorial recurrence

Explanation: Builds factorials incrementally and provides base for many combinatorial formulas.

Falling factorial

Explanation: A compact way to express permutations; it directly multiplies the descending sequence of choices.

Binomial theorem

Explanation: Connects binomial coefficients to polynomial expansion; shows why row sums of binomial coefficients are powers of two.

Row sum

Explanation: Each subset of an n-element set is counted exactly once, and there are 2^n subsets.

Hockey-stick identity

Explanation: Summing along a diagonal of Pascal's triangle equals a shifted binomial coefficient; useful in combinatorial sums.

Vandermonde's identity

Explanation: Choosing k items from two disjoint sets can be partitioned by how many are chosen from each set.

Fermat inverse

Explanation: When p is prime and a is nonzero mod p, we can compute the modular inverse by fast exponentiation.

Precompute formula

Explanation: With factorial and inverse factorial arrays modulo a prime p, each binomial coefficient query becomes O(1).

Relation between P and C

Explanation: First choose the k elements (unordered), then arrange them in k! orders to get permutations.

Complexity Analysis

There are three common computational strategies with different trade-offs: 1) Precomputation with factorials and inverse factorials modulo a prime p: Building fact[0..N] and invfact[0..N] takes O(N) time and O(N) space. Modular inverse of fact[N] is computed in O(log p) using fast exponentiation, and invfact[i-1] = invfact[i]·i mod p enables an O(N) backward fill. Each query C(n,k) is then O(1): fact[n]·invfact[k]·invfact[n−k] mod p. This is ideal when you have many queries and N (the maximum n) fits in memory (e.g., up to 10^6 or a few times 10^7 depending on limits). 2) Pascal’s triangle (DP): Building all C(n,k) for 0 ≤ takes O() time and O() space if you store the full table, or O(N) space if you only keep the current row. This is useful for small N (hundreds to a few thousands) or when you need all coefficients for a fixed n. It is too slow and memory-heavy for large N. 3) Multiplicative method for a single C(n,k) (mod p): Compute C(n,k) = ∏_{i=1}^{k} (n−k+i)/i by multiplying numerator terms modulo p and multiplying by modular inverses of denominators. This costs O(k log p) if you compute each inverse with fast exponentiation, or O(k) if you precompute small inverses. This is great when k is small (e.g., ) or for a few queries, avoiding large precomputation arrays. Space-wise, precomputation uses O(N) memory, Pascal DP can be O() unless optimized per row, and the multiplicative method uses O(1) extra space.

Code Examples

O(1) binomial and permutation queries with factorial precomputation (mod 1e9+7)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Fast exponentiation: computes a^e mod MOD
5long long mod_pow(long long a, long long e, long long MOD) {
6    long long r = 1 % MOD;
7    while (e > 0) {
8        if (e & 1) r = (__int128)r * a % MOD;
9        a = (__int128)a * a % MOD;
10        e >>= 1;
11    }
12    return r;
13}
14
15struct Comb {
16    int N;                // maximum n supported
17    long long MOD;        // prime modulus
18    vector<long long> fact, invfact;
19    Comb(int N_, long long MOD_) : N(N_), MOD(MOD_), fact(N_+1), invfact(N_+1) {
20        // Precompute factorials fact[i] = i! % MOD
21        fact[0] = 1;
22        for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
23        // Compute invfact[N] = (fact[N])^{-1} using Fermat's little theorem
24        invfact[N] = mod_pow(fact[N], MOD - 2, MOD);
25        // Fill inverse factorials downward: invfact[i-1] = invfact[i] * i
26        for (int i = N; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;
27    }
28    long long nCk(int n, int k) const {
29        if (k < 0 || k > n || n < 0 || n > N) return 0;
30        return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
31    }
32    long long nPk(int n, int k) const {
33        if (k < 0 || k > n || n < 0 || n > N) return 0;
34        return fact[n] * invfact[n-k] % MOD; // since P(n,k) = n!/(n-k)!
35    }
36};
37
38int main() {
39    ios::sync_with_stdio(false);
40    cin.tie(nullptr);
41
42    const long long MOD = 1'000'000'007LL;
43    int Q;               // number of queries
44    int maxN;            // maximum n across all queries
45
46    // Example input format:
47    // Q
48    // type n k
49    // type: 0 for C(n,k), 1 for P(n,k)
50    cin >> Q;
51    vector<tuple<int,int,int>> queries(Q);
52    maxN = 0;
53    for (int i = 0; i < Q; ++i) {
54        int type, n, k;
55        cin >> type >> n >> k;
56        queries[i] = {type, n, k};
57        maxN = max(maxN, n);
58    }
59
60    Comb comb(maxN, MOD);
61    for (auto [type, n, k] : queries) {
62        if (type == 0) {
63            cout << comb.nCk(n, k) << "\n"; // C(n,k) mod MOD
64        } else {
65            cout << comb.nPk(n, k) << "\n"; // P(n,k) mod MOD
66        }
67    }
68    return 0;
69}
70

We precompute factorials and inverse factorials modulo a prime and answer each binomial or permutation query in O(1). Fermat’s little theorem computes the inverse of fact[N], and we fill invfact downwards in O(N). This is ideal for many queries with n up to around 10^6.

Time: Preprocessing: O(N), Each query: O(1)Space: O(N)
Pascal’s triangle DP for small n (build all C(n,k) modulo a prime)
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    ios::sync_with_stdio(false);
6    cin.tie(nullptr);
7
8    int N;               // build rows 0..N
9    long long MOD = 1'000'000'007LL; // can be changed or set to 0 for no modulo (risk overflow)
10    cin >> N;
11
12    vector<vector<long long>> C(N+1, vector<long long>(N+1, 0));
13    for (int n = 0; n <= N; ++n) {
14        C[n][0] = C[n][n] = 1;           // base cases
15        for (int k = 1; k < n; ++k) {
16            C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MOD; // Pascal's identity
17        }
18    }
19
20    // Example: print row N and verify symmetry
21    for (int k = 0; k <= N; ++k) cout << C[N][k] << (k+1<=N? ' ' : '\n');
22
23    // Example query: demonstrate symmetry C(N,k) == C(N,N-k)
24    int q; cin >> q; // number of (k) queries
25    while (q--) {
26        int k; cin >> k;
27        long long a = C[N][k];
28        long long b = C[N][N-k];
29        cout << a << " " << b << "\n"; // should be equal modulo MOD
30    }
31    return 0;
32}
33

This program builds Pascal’s triangle up to row N using C(n,k) = C(n−1,k−1) + C(n−1,k). It prints the N-th row and allows symmetry checks. This approach is great for small N or when you need many C(N,k) values for the same N.

Time: O(N^2)Space: O(N^2)
O(k) multiplicative computation of C(n,k) modulo a prime (no big tables)
1#include <bits/stdc++.h>
2using namespace std;
3
4long long mod_pow(long long a, long long e, long long MOD) {
5    long long r = 1 % MOD;
6    while (e) {
7        if (e & 1) r = (__int128)r * a % MOD;
8        a = (__int128)a * a % MOD;
9        e >>= 1;
10    }
11    return r;
12}
13
14long long mod_inv(long long a, long long MOD) { // MOD must be prime; a % MOD != 0
15    return mod_pow((a % MOD + MOD) % MOD, MOD - 2, MOD);
16}
17
18long long nCk_multiplicative(long long n, long long k, long long MOD) {
19    if (k < 0 || k > n) return 0;
20    k = min(k, n - k); // use symmetry to reduce steps
21    long long res = 1 % MOD;
22    for (long long i = 1; i <= k; ++i) {
23        long long num = (n - k + i) % MOD;          // numerator term
24        long long den = i % MOD;                    // denominator term
25        res = (__int128)res * num % MOD;
26        res = (__int128)res * mod_inv(den, MOD) % MOD; // divide by i via modular inverse
27    }
28    return res;
29}
30
31int main() {
32    ios::sync_with_stdio(false);
33    cin.tie(nullptr);
34
35    const long long MOD = 1'000'000'007LL; // prime
36    long long n, k; cin >> n >> k;
37    cout << nCk_multiplicative(n, k, MOD) << "\n";
38    return 0;
39}
40

This computes C(n,k) in O(k) time by multiplying the k numerator terms and dividing by each i using modular inverses (Fermat). It is excellent for single or few queries, especially when k is small relative to n, and avoids O(N) memory.

Time: O(k log MOD) if computing each inverse by pow; O(k) if inverses are precomputedSpace: O(1)
Counting grid paths with combinations: number of shortest paths on an h×w grid
1#include <bits/stdc++.h>
2using namespace std;
3
4long long mod_pow(long long a, long long e, long long MOD) {
5    long long r = 1 % MOD;
6    while (e) {
7        if (e & 1) r = (__int128)r * a % MOD;
8        a = (__int128)a * a % MOD;
9        e >>= 1;
10    }
11    return r;
12}
13
14struct Comb {
15    int N; long long MOD; vector<long long> fact, invfact;
16    Comb(int N_, long long MOD_) : N(N_), MOD(MOD_), fact(N_+1), invfact(N_+1) {
17        fact[0] = 1;
18        for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
19        invfact[N] = mod_pow(fact[N], MOD - 2, MOD);
20        for (int i = N; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;
21    }
22    long long nCk(int n, int k) const {
23        if (k < 0 || k > n || n < 0 || n > N) return 0;
24        return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
25    }
26};
27
28int main() {
29    ios::sync_with_stdio(false);
30    cin.tie(nullptr);
31
32    long long MOD = 1'000'000'007LL;
33    int h, w; cin >> h >> w;
34    // Number of shortest paths from (0,0) to (h-1,w-1) with only Right/Down moves is C(h+w-2, h-1).
35    int n = h + w - 2;
36    int k = h - 1;
37    Comb comb(n, MOD);
38    cout << comb.nCk(n, k) << "\n";
39    return 0;
40}
41

Any shortest path consists of exactly h−1 Down moves and w−1 Right moves, in some order. Choosing which of the n = h+w−2 steps are Down uniquely determines a path, so the answer is C(n, h−1) modulo 1e9+7.

Time: Preprocessing: O(h+w), Query: O(1)Space: O(h+w)