Combinatorics: Counting Arrangements and Choices

Combinatorics answers the question "in how many ways…?" without listing all the possibilities. At competitions the result is usually asked for modulo 109+7, so here we also learn how to calculate that fast and without overflow.

Before you start: prerequisites – Mathematical algorithms, The fast exponentiation algorithm.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The sum rule and the product rule

  • The sum rule: if you choose either one of a possibilities or one of b (which do not overlap), there are a + b possibilities in total.
  • The product rule: if you choose one of a possibilities and independently one of b, there are a · b possibilities in total.

Example: a password of 2 letters (26 possibilities) followed by 3 digits (10 possibilities) – in total 26 · 26 · 10 · 10 · 10 = 676,000 passwords.

Basic formulas

What is countedFormulaExample
arrangements of n different elements (permutations)n!5 books on a shelf: 120
an ordered choice of k out of n (variations)n! / (n−k)!the first three places out of 10 competitors: 720
an unordered choice of k out of n (combinations)C(n, k) = n! / (k!·(n−k)!)a team of 3 out of 10 students: 120
one of n, k times, with repetitionnka 4-digit PIN: 10,000
paths in an a × b grid (only right and down)C(a + b, a)a 2 × 2 grid: 6

If all those possibilities have to be printed, and not only counted, see Generating permutations and combinations.

Pascal's triangle

For C(n, k) the following holds: C(n, k) = C(n−1, k−1) + C(n−1, k): the element n either is in the choice (so we choose k−1 more out of the other n−1) or it is not (we choose all k out of n−1). This way the whole table is calculated only by addition – without division, so it works modulo too. This is also an example of dynamic programming.

#include <iostream>
using namespace std;

const int MOD = 1000000007;
int C[1001][1001];

int main() {
    for (int n = 0; n <= 1000; n++) {
        C[n][0] = 1;
        for (int k = 1; k <= n; k++)
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k]) % MOD;
    }
    int n, k;
    cin >> n >> k;
    cout << C[n][k] << endl;
    return 0;
}

For the input 10 3 the program prints 120, and for 1000 500 it prints 159835829 (modulo 109+7). The 1001 × 1001 table is calculated in about half a million additions – fast, but for n up to 106 it would not fit in memory.

Large values: factorials modulo and the inverse

For a large n the factorials f[i] = i! mod p are calculated in advance. Division modulo is replaced by multiplication by the inverse: when p is a prime number, the inverse of the number a is ap−2 mod p (Fermat's little theorem), and it is calculated with fast exponentiation.

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;          // a prime number
const int MAXN = 1000000;
vector<long long> f(MAXN + 1), invf(MAXN + 1);

long long power(long long a, long long b) {
    long long r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return f[n] * invf[k] % MOD * invf[n - k] % MOD;
}

int main() {
    f[0] = 1;
    for (int i = 1; i <= MAXN; i++) f[i] = f[i - 1] * i % MOD;
    invf[MAXN] = power(f[MAXN], MOD - 2);              // the inverse of the largest factorial
    for (int i = MAXN; i > 0; i--) invf[i - 1] = invf[i] * i % MOD;

    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;
        cout << C(n, k) << "\n";
    }
    return 0;
}

Example

Input

3
10 3
1000 500
5 7

Output

120
159835829
0

After the preparation (about 2 million multiplications) every query C(n, k) takes constant time. Note: the inverse exists only when p does not divide the number – that is why a large prime modulus is used.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

The number of passwords

A password has exactly n characters (n ≤ 1018); every character is a lowercase letter (26) or a digit (10). How many passwords are there? Print the result modulo 109+7.

Example 1

Input

2

Output

1296

Example 2

Input

1000000000000

Output

231007120
TASK 02Difficulty: medium-hard

Paths through a city

The streets of a city form a grid with a blocks to the right and b blocks down (a, b ≤ 106). How many shortest paths are there from the top-left to the bottom-right corner? The result modulo 109+7.

Example 1

Input

2 2

Output

6

Example 2

Input

1000000 1000000

Output

192151600
TASK 03Difficulty: easy

Handshakes and a tournament

There are n people at a meeting (n ≤ 109) and everybody shakes hands with everybody once. How many handshakes were there? Also print how many matches a tournament would have in which every two teams play twice (at home and away).

Example 1

Input

4

Output

6
12

Example 2

Input

1000000000

Output

499999999500000000
999999999000000000
Common mistakes and tips
  • Before calculating, decide: does the order matter (variations/permutations) or not (combinations)?
  • Modulo you may add, subtract and multiply, but not divide – division is replaced by multiplication by the inverse.
  • The product of two numbers smaller than 109+7 fits in a long long, but the product of three does not – after every multiplication take % MOD.
  • When subtracting modulo, add MOD: (a - b + MOD) % MOD.

Check your knowledge

Open the quiz

Mini quiz: combinatorics

1. In how many ways can a president and a deputy be chosen out of 6 students?




2. What is C(6, 2)?




3. Modulo a prime p, what replaces division by a?