17. Permutations and combinations — Homework Solutions

Problem 1 is worked on paper. The .cpp files for problem 2 through the challenge are in exercises/17/homework/solutions/.

Open this page after trying on your own. For the paper problem, write down your answer first, then compare — reading someone else's answer feels clear even when you may not be able to repeat it yourself. The Tests part contains input and output that have already been checked for the coding problems.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/17/homework/solutions/02-pascal.cpp
./jawab

Problem 1 — Count on paper

a. Arrangements of the letters of BUKU → 12.

Four letters with U appearing twice: 4! / 2! = 24 / 2 = 12.

b. Choosing 3 of 8 students → 336 and 56.

If the three have different tasks, order matters: P(8, 3) = 8 × 7 × 6 = 336. If the tasks are the same, order does not matter: C(8, 3) = 336 / 3! = 56.

Note the relationship: the second answer is the first answer divided by 3!, because every identical group can be arranged in 6 orders.

c. Paths on a 3 × 4 board → 10.

From the top-left corner to the bottom-right it takes 2 steps down and 3 steps right, 5 steps in total. All that remains is choosing 2 positions among 5 for the down steps: C(5, 2) = 10.

d. Choosing at least one of 10 students → 1,023.

There are 2¹⁰ = 1,024 subsets in total, including the empty set. Discard the empty one: 1,023. This is a use of the complement from Chapter 16.

Problem 2 — Pascal's triangle

Problem. Print Pascal's triangle rows 0 through n (≤ 30).

How to think about it. Every row is built from the row above it with C(n, r) = C(n−1, r−1) + C(n−1, r), and every row starts with C(n, 0) = 1. There is no division and no factorial, so there is no rounding risk.

For n = 30, the largest value is C(30, 15) = 155,117,520 — it still fits in int, but use long long as a habit.

Walkthrough.

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

Tests. Input 5 produces six lines:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Input 0 produces one line containing 1. Two quick checks for each row: the numbers are symmetric, and the sum of one row equals 2ⁿ — the last row above sums to 32 = 2⁵.

Common mistakes.

• Filling C[i][r] for r > i. The value is zero and gets printed too.
• Printing a space at the end of the line.
• Using the factorial formula for n = 30. 30! does not fit in long long even though the final result does.

Problem 3 — Modular combinations

Problem. 100,000 queries of C(n, r) mod 10⁹ + 7 with n up to a million.

How to think about it. A Pascal table of a million × a million is impossible. What is used: a factorial table once at the start (a million cells), then every query is answered with

C(n, r) = n! × (r!)⁻¹ × ((n−r)!)⁻¹ mod p

The inverse is computed with Fermat's little theorem, O(log p) per query. Total: 10⁶ for preparation + 10⁵ × 30 for the queries ≈ 4 million steps.

Do not forget ios::sync_with_stdio(false) for input this large.

Walkthrough.

fakt[0] = 1;
for (int i = 1; i < MAKS; i++) fakt[i] = fakt[i - 1] * i % MOD;

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

Check: C(10, 3) = 120, C(30, 15) = 155,117,520 (same as the Pascal result), C(1,000,000, 500,000) mod p = 996,692,777.

Tests.

The third row is very useful for testing: C(30, 15) = 155,117,520 is still smaller than 10⁹ + 7, so if your answer differs here, the mistake is certainly in the formula or the inverse — not in the modulo.

Common mistakes.

• Dividing fakt[n] / bawah with integer division. The stored values are already remainders; the result has nothing to do with the answer (it is often even zero).
• Preparing the factorial table inside the query loop, so it is done 100,000 times.
• Forgetting to handle r > n, which should be 0.

Problem 4 — Paths on a board

Problem. Paths on a b × k board up to 500,000 × 500,000.

How to think about it. Every path is a sequence of steps: b − 1 steps down and k − 1 steps right, in any order. So the problem becomes "choose the positions of the down steps among all the steps":

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

The largest size is about a million, so a factorial table of a million cells is enough.

Walkthrough.

cout << kombinasi((int)(b - 1 + k - 1), (int)(b - 1)) << "\n";

Check: 3 4 gives 10 — the same as the paper answer to problem 1(c).

Tests.

The last row tests the size of the factorial table: paths on a 500,000 × 500,000 board require C(999,998, 499,999), so the factorial table must be prepared up to about one million — not up to 500,000.

Common mistakes.

• Using a DP over the b × k board (dp[i][j] = dp[i-1][j] + dp[i][j-1]). Correct for small boards, but 500,000 × 500,000 cells cannot possibly be stored.
• Miscounting the number of steps: a b × k board has b rows and k columns, so the steps are b − 1 and k − 1, not b and k.

Challenge — Check your formula

Problem. Compare Pascal's triangle with direct enumeration.

How to think about it. cacah(n, r) goes through all 2ⁿ subsets and counts those of size exactly r. For n = 15 that is 32,768 masks times 15 bit checks — light.

The third check (the sum of a row = 2ⁿ) is useful because it is different in nature: it tests a whole row at once, not a single value.

Walkthrough.

long long cacah(int n, int r) {
    long long banyak = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int bit = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) bit++;
        if (bit == r) banyak++;
    }
    return banyak;
}

The output: the formula and the enumeration agree for all n ≤ 15, and the sum of every row equals 2ⁿ.

This habit — testing a combinatorics formula with a small enumeration — is the fastest way to find a wrong formula before the answer is submitted. It is the same as the comparison tester of Chapter 10, only applied to math.

Tests. The answer program prints its own conclusion:

rumus dan cacahan cocok untuk semua n <= 15
jumlah tiap baris sama dengan 2^n

The two checks complement each other. The first compares the formula with direct enumeration, so it catches formula mistakes. The second checks a property that the whole row must satisfy at once, so it catches mistakes that happen to slip through for one particular value of r. This two-layer pattern is exactly the comparison tester of Chapter 10, applied to a formula instead of an algorithm.

Common mistakes.

• Testing with a large n so that the enumeration itself is too slow.
• Writing cacah using a formula again (for example factorials), so that what is compared is two forms of the same formula. The enumeration must be plain.

OSN-style exercises — walkthrough

The answer files are in exercises/17/osn/solutions/.

Problem 1 — Letter Arrangements

How to think about it. Suppose all the letters are considered different — for example, the two as are marked a₁ and a₂. Then there are N! arrangements. But swapping a₁ with a₂ produces the same word, so every word is actually counted several times: as many times as there are ways to order those duplicate letters among themselves.

If letter number h appears cₕ times, every word is counted ∏ cₕ! times. So the answer is:

N! / (c₁! × c₂! × … × c₂₆!)

Since the answer is modulo, the division is done with the inverse: for a prime modulus, x⁻¹ ≡ x^(p−2).

Walkthrough.

vector<long long> fakt(n + 1);
fakt[0] = 1;
for (int i = 1; i <= n; i++) fakt[i] = fakt[i - 1] * i % MOD;

long long cacah[26] = {0};
for (char c : s) cacah[c - 'a']++;

long long hasil = fakt[n];
for (int h = 0; h < 26; h++) {
    if (cacah[h] > 1) hasil = hasil * invers(fakt[cacah[h]]) % MOD;
}

There are at most 26 different letters, so at most 26 modular exponentiations — the cost is negligible compared with preparing the factorials. Measured on the author's machine, a word of length 10⁶ finishes in 0.02 seconds.

Tests.

The first three rows are worth checking by hand; also compare with an enumerating program for words of 6–7 letters.

Common mistakes.

• Dividing with / instead of multiplying by the inverse. The result is almost always wrong because fakt[n] is already reduced modulo.
• Computing n! with long long without a modulo. 21! alone already overflows.
• Using the index c - 'A', when the input is lowercase letters.

Problem 2 — Sharing Candy

How to think about it. Imagine the N candies lined up in one row. Between two adjacent candies there is a gap, and there are N − 1 gaps in total.

Placing a divider in a gap cuts the row into two parts. To get K parts, exactly K − 1 dividers are needed, and each gap gets at most one divider — if two dividers were in the same gap, some child would get nothing.

So the problem turns into: how many ways are there to choose K − 1 gaps out of N − 1 gaps? The answer is C(N − 1, K − 1).

The validity condition is K ≤ N: if there are more children than candies, no distribution is possible.

Walkthrough.

if (k > n) { cout << "0\n"; return 0; }

// C(n-1, k-1)
long long atas = fakt[n - 1];
long long bawah = fakt[k - 1] * fakt[n - k] % MOD;

cout << atas * pangkat(bawah, MOD - 2) % MOD << "\n";

The k > n check must come before the formula — without it, fakt[n - k] is read at a negative index.

Tests.

Common mistakes.

• Using C(N, K). That is the answer to a different problem.
• Using C(N + K − 1, K − 1), which is the formula for the case "some children may get nothing".
• Forgetting to check K > N.

Problem 3 — Choosing Without Neighbors

How to think about it. This is a form that looks new but is really an ordinary combination in disguise.

Imagine the K participants already seated in order from left to right. The condition is that there is at least one empty chair between two neighboring participants. Take that one mandatory empty chair out of every gap between participants — K − 1 chairs in total — and remove them from the count. What remains is N − (K − 1) chairs, and in that remaining row the participants may be chosen freely.

So the answer is C(N − K + 1, K).

A quick check: for N = 5, K = 2, the formula gives C(4, 2) = 6, and there are indeed six valid choices.

The validity condition is K ≤ N − K + 1. Otherwise, the answer is 0.

Walkthrough.

long long atasN = n - k + 1;
if (k > atasN || atasN < 0) { cout << "0\n"; return 0; }

vector<long long> fakt(atasN + 1);
fakt[0] = 1;
for (long long i = 1; i <= atasN; i++) fakt[i] = fakt[i - 1] * i % MOD;

long long bawah = fakt[k] * fakt[atasN - k] % MOD;
cout << fakt[atasN] * pangkat(bawah, MOD - 2) % MOD << "\n";

Tests.

The case 5 0 is often missed. Choosing zero chairs is one way, not zero ways, and the formula indeed gives C(6, 0) = 1.

Common mistakes.

• Using C(N, K) and then subtracting the adjacent ones one by one. It can be correct for K = 2, but it does not generalize.
• Forgetting to check K > N − K + 1, so fakt is read at a negative index.
• Answering 0 for K = 0.

If you are still stuck

• Unsure whether it is a permutation or a combination → Chapter 17, its opening question: does swapping the order produce a different result?
• The answer is r! times too large → it means you used a permutation for a combination problem.
• Modular combinations give the wrong number → Chapter 17, the warning about dividing after the modulo; use the inverse from Chapter 14.

With this chapter, the entire content of the book has been covered. The next step is not a new chapter, but problems: work through the archive of OSN problems on the online judge you registered with in Chapter 01, and reuse the same habits — abstraction, counting steps, testing edge cases.