17. Permutations and combinations

The previous chapter counted with two basic rules. This chapter gives a name and a formula to the two patterns that come up most often: choosing with regard to order (permutations) and without regard to order (combinations).

One question separates the two:

Does swapping the order produce a different result?

• Arranging three people as chair, secretary, treasurer → yes, order matters → permutation.
• Choosing three people to join a team → no, order does not matter → combination.

Factorial

n! is the product of 1 through n, and 0! = 1.

Why 0! = 1: there is exactly one way to arrange an empty sequence, namely to arrange nothing. This convention is not merely a convention — without it, the combination formula below would break on the edge cases r = 0 and r = n.

Factorials grow very fast: 21! no longer fits in long long. That is why problems that use factorials almost always ask for the answer modulo 10⁹ + 7.

Permutations

Arranging all n objects can be done in n! ways: the first choice has n options, the next n − 1, and so on — the decreasing product rule from Chapter 16.

Arranging r of n objects (order matters):

P(n, r) = n! / (n − r)! = n × (n−1) × … × (n−r+1)

Example: from 10 students, a chair, a secretary, and a treasurer are chosen: P(10, 3) = 10 × 9 × 8 = 720.

Where the formula comes from: the first choice has n possibilities, the second n − 1 because one is already used, and so on up to r choices. The form n! / (n − r)! is just a compact way of writing that decreasing product — dividing by (n − r)! discards the tail of the product that is not used.

A small example that can be listed completely: from the letters A B C, choose 2 with order mattering. P(3, 2) = 3 × 2 = 6, and there are indeed six:

AB  AC  BA  BC  CA  CB

Permutations with identical elements. If some objects cannot be told apart, divide by the factorial of the count of each:

n! / (n₁! × n₂! × … )

Example: arrangements of the letters in the word OSNOSN (6 letters: O×2, S×2, N×2): 6! / (2! × 2! × 2!) = 720 / 8 = 90.

Combinations

Choosing r of n objects without regard to order:

C(n, r) = n! / (r! × (n − r)!)

The relation to permutations: every group of r objects can be arranged in r! orders, so C(n, r) = P(n, r) / r!.

Example: from 10 students, 3 are chosen for a team: C(10, 3) = 720 / 6 = 120.

Back to the A B C example. If order is not taken into account, the six arrangements shrink into three groups:

Every combination is represented by 2! = 2 arrangements, so C(3, 2) = 6 / 2 = 3. The divisor r! in the combination formula is exactly the number of arrangements that are considered the same.

A quick way to check whether a problem is a permutation or a combination: swap the positions of two objects that have been chosen. If the result is considered different, it is a permutation; if it is considered the same, a combination.

Frequently used properties:

The third row is the most useful one for programs: it turns combinations into dynamic programming. Read it as: object number n is chosen (the remaining r−1 from n−1) or not chosen (r from n−1).

Notice its shape — "take or do not take, then add up both possibilities" — exactly the shape of the knapsack transition in Chapter 13. The only difference is that knapsack takes the largest, whereas counting adds. When two paths in a problem never produce the same thing, adding them up is the way to count them.

Pascal's triangle

n=0             1
n=1           1   1
n=2         1   2   1
n=3       1   3   3   1
n=4     1   4   6   4   1
n=5   1   5  10  10   5   1

Every number is the sum of the two numbers above it. In code:

long long C[1005][1005];

for (int n = 0; n <= batas; n++) {
    C[n][0] = 1;
    for (int r = 1; r <= n; r++)
        C[n][r] = (C[n-1][r-1] + C[n-1][r]) % MOD;
}

This method is O(n²) and needs no division at all — suitable for n up to a few thousand. Since there is no division, it also works for any modulus, even one that is not a prime number.

Modular combinations for large n

For n up to a million, Pascal's table is too large (10¹² cells). What is used instead is the factorial formula, with division replaced by multiplication by the modular inverse (Chapter 14):

long long fakt[1000005];

void siapkan(int n) {
    fakt[0] = 1;
    for (int i = 1; i <= n; i++) fakt[i] = fakt[i-1] * i % MOD;
}

long long kombinasi(int n, int r) {
    if (r < 0 || r > n) return 0;
    long long atas = fakt[n];
    long long bawah = fakt[r] * fakt[n-r] % MOD;
    return atas * pangkat_mod(bawah, MOD - 2, MOD) % MOD;
}

This is the most common use of Fermat's little theorem at OSN: without the modular inverse, the combination formula cannot be computed.

Problem patterns

Paths on a board. From the top-left corner to the bottom-right corner of a b × k board, you may only step right or down. Every path consists of b−1 down steps and k−1 right steps; the answer is simply choosing the positions of the down steps among all the steps:

C((b−1) + (k−1), b−1)

A small example for a 2 × 3 board: every path consists of 1 down step and 2 right steps, so the answer is C(3, 1) = 3. All three can be listed as step sequences:

right right down
right down right
down right right

The core idea: a path is completely determined by at which steps you move down. So counting paths is the same as choosing the positions of the down steps among all the steps — and that is exactly a combination.

Choosing a team. "How many ways to choose 5 of 12 players" → C(12, 5).

Splitting into two groups. "How many ways to split 10 people into two groups of 4 and 6" → C(10, 4).

Subsets. "How many subsets does a set of n objects have" → 2ⁿ, which is also the sum of one row of Pascal's triangle.

Homework

Most common mistakes

OSN tips

Distinguish three questions that sound similar. Almost every mistake on combinatorics problems comes from picking the wrong one of the three:

The key: if swapping two choices produces an arrangement that is considered different, order matters.

Prepare the factorials once at the start. For problems with many queries, compute fakt[0..n] once, and then every combination becomes one multiplication and one inverse. Recomputing the factorials inside the query loop is the most common cause of Time Limit Exceeded in this chapter.

Modular division always means an inverse. C(n, k) mod p must not be computed with /. For a prime p, the inverse is pangkat(x, p − 2). If there are very many queries, also prepare an array of inverse factorials so that each query does not need its own modular exponentiation.

Check the formula with a brute-force enumerator. For n ≤ 10, all arrangements can be enumerated with next_permutation or a bitmask loop. Comparing the formula with the enumerator on small n finds factor errors within seconds.

Recognize the stars-and-bars form. The phrase "distribute N identical objects to K people" almost always means a combination: with the condition that each person gets at least one, the answer is C(N − 1, K − 1); if someone may get nothing, C(N + K − 1, K − 1). The difference is one word in the problem.

The upper limit for factorials is much smaller than you would guess. 20! is already close to 2.4 × 10¹⁸ and 21! exceeds long long. So a problem that asks for a factorial without a modulo almost certainly limits n ≤ 20 — and if the constraint is larger, a modulo is certainly required.

Summary

• One question separates the two: does swapping the order produce a different result? Yes → permutation, no → combination.
• P(n, r) = n! / (n − r)! is the decreasing product n × (n−1) × … with r factors.
• C(n, r) = P(n, r) / r!, because every group of r objects can be arranged in r! orders.
• Permutations with identical elements: divide by the factorial of the count of each element.
• C(n, r) = C(n−1, r−1) + C(n−1, r) is Pascal's triangle, its DP form, and suits n up to a few thousand.
• For large n, use a modular factorial table and the inverse from Fermat's little theorem (Chapter 14).
• Paths on a board where you may only go right and down are a combination problem: choose at which steps to move down.

OSN-style exercises

The following three problems use combinations in three different disguises: permutations with repeated elements, stars and bars, and selection with a restriction. Recognize the form first, then write the formula.

The skeletons for all three are in exercises/17/osn/.

Problem 1 — Letter Arrangements

You are given a word S. Count how many different words can be formed by rearranging all the letters of S. Two arrangements are considered the same if they have exactly the same letter at every position.

Output the answer modulo 1,000,000,007.

Input format. One line containing the word S, consisting entirely of lowercase letters a through z.

Output format. One line containing the number of distinct arrangements modulo 1,000,000,007.

Constraints. 1 ≤ length of S ≤ 10⁶.

Sample input

aabb

Sample output

6

Explanation. The arrangements are aabb, abab, abba, baab, baba, and bbaa. If the four letters were considered different, there would be 4! = 24 arrangements; but swapping the two as does not produce a new word, and neither does swapping the two bs, so every word is counted 2! × 2! = 4 times.

The skeleton: exercises/17/osn/01-susunan-huruf.cpp

Problem 2 — Sharing Candy

A teacher has N candies that are exactly identical and will distribute them to K children. Every child must get at least one candy, and all the candies must be given out.

Two distributions are considered different if some child receives a different number of candies. Count the number of possible distributions, modulo 1,000,000,007.

Input format. One line containing two integers N and K.

Output format. One line containing the number of distributions modulo 1,000,000,007. If no distribution is possible, print 0.

Constraints.

• 1 ≤ N ≤ 10⁶
• 1 ≤ K ≤ 10⁶

Sample input

5 2

Sample output

4

Explanation. The distributions are (1, 4), (2, 3), (3, 2), and (4, 1). Since the children can be told apart, (1, 4) and (4, 1) count as two different distributions — whereas the candies are identical, so the only thing that distinguishes them is the counts.

The skeleton: exercises/17/osn/02-bagi-permen.cpp

Problem 3 — Choosing Without Neighbors

A room has N chairs lined up in one row. The committee wants to seat K participants, and to prevent cheating, no two participants may sit in adjacent chairs.

Count how many ways there are to choose the chairs that will be occupied, modulo 1,000,000,007. The participants are considered indistinguishable — only the set of chairs is counted.

Input format. One line containing two integers N and K.

Output format. One line containing the number of ways modulo 1,000,000,007. If no way is possible, print 0.

Constraints.

• 1 ≤ N ≤ 10⁶
• 0 ≤ K ≤ 10⁶

Sample input

5 2

Sample output

6

Explanation. The chair choices are (1,3), (1,4), (1,5), (2,4), (2,5), and (3,5). A choice like (2,3) is not valid because the chairs are adjacent.

The skeleton: exercises/17/osn/03-pilih-tanpa-bertetangga.cpp

Stuck or already done? Open the homework solutions page.