Combinatorics — Counting Techniques

Section 1

Quick Reference#

The whole topic at a glance. Keyword first, then the terse rule; everything here is unpacked below. Watch the margin markers: ⭐ trick, ⚠ pitfall, 💡 tip.

Section 2

Full Walkthrough#

Every technique from the ground up. Read this once and the reference above becomes pure recall.

01Two ways to count: casework and the complement#

Counting is turning a "how many ways?" question into arithmetic instead of a list. Two engines do almost all the work: split the problem into separate cases and add, or count everything and subtract the arrangements you don't want.

Before the tricks, two rules underpin everything. The product rule (the "and then" rule): if you make a choice in one stage and then an independent choice in the next, multiply the counts. Picking a shirt (3 ways) and then pants (4 ways) gives 12 outfits. The sum rule (the "or" rule): if an outcome falls into one of several non-overlapping buckets, add the buckets.

The complement trick (counting the opposite) is the one you'll reach for most. Think of it like clearing a room: instead of counting everyone allowed to stay, you count the total crowd and subtract the few who must leave. It shines when the forbidden arrangements are fewer or simpler than the allowed ones.

Worked example — the three-round contest. Round 1 has 4 challenges, round 2 has 5, round 3 has 3. Constraint: if challenge 1 (C1) is chosen in R1, then challenge 2 (C2) can't be chosen in R2.

Casework (the direct route). Case 1: contestant picks C1 in R1 (1 way). Then R2 can be any of its 5 except C2 → 4 ways, and R3 → 3 ways: 1·4·3 = 12. Case 2: doesn't pick C1 in R1 → 3 remaining choices, R2 unrestricted (5), R3 (3): 3·5·3 = 45. Total 12 + 45 = 57.

02Gap constraints: keeping items apart#

A gap constraint asks for a minimum separation between specific items in an arrangement. Direct counting is painful; count the total and subtract the arrangements where the items are too close.

Analogy — assigned seating at a wedding. Two guests who can't stand each other (A and B) must have at least two people between them. Rather than seat everyone else first and squeeze A and B into legal spots, you seat everyone freely, then throw out the seatings where A and B ended up adjacent or with just one person between.

Problem. 8 distinct books on a shelf; books A and B must have at least 2 other books between them. Total arrangements ignoring the rule: 8!. "Too close" splits into two bad cases.

Bad case 0 — no book between (adjacent). Treat "AB" as one glued block. That block plus the other 6 books = 7 units → 7! arrangements. A and B can be AB or BA inside the block → ×2. Total 2·7!.

Bad case 1 — exactly one book between. Choose which single book sits between them: 6C1 ways. Glue "A?B" into a block → that block plus 5 remaining books = 6 units → 6!. A and B swap → ×2. Total 6C1·6!·2 = 12·6!.

Subtract both from the total and factor out 6!: 8! − 2·7! − 12·6! = 6!(8·7 − 2·7 − 12) = 6!(56−14−12) = 720·30 = 21 600.

03"At most" selections: split by how many special items you take#

A selection (combination) counts groups where order doesn't matter. When a rule limits how many "special" members you can include, split into cases by the exact number of special items chosen, then add.

Analogy — a committee with rival factions. You're forming a 6-person committee from 15 people, but 3 of them are rivals and at most one rival may join. "At most one" is a fork: either zero rivals or exactly one. Handle each branch and sum.

Split the 15 into 3 special and 12 others.

Case A — zero special. All 6 come from the 12 others: 12C6 = 924.
Case B — exactly one special. Pick 1 of 3 specials (3C1) and the other 5 from the 12 others (12C5 = 792): 3·792 = 2376.
Total 924 + 2376 = 3300.

04Arranging with repeats: the multiset permutation#

When some items are identical, distinct arrangements shrink because swapping two identical items changes nothing. Divide the total permutations by the factorial of each repeat count.

Analogy — indistinguishable twins in a photo line-up. Line up 5 people and you get 5! photos. But if two are identical twins, swapping them produces the same photo — so you've double-counted, and you divide by 2!.

Problem — the word BALLOON, with the two O's forced together. First apply the glue trick: bind "OO" into one block. The units become B, A, L, L, (OO), N — that's 6 units. Arrange the 6 units: 6!. But L repeats twice, so divide by 2!. The OO block's internal order is 1 (the two O's are identical, so there's nothing to multiply by).

05Stars and bars: distributing identical items#

Stars and bars counts the ways to split n identical items among k distinct bins. Picture n stars in a row; drop k−1 bars among them, and each gap-pattern is one distribution.

Analogy — pouring water into buckets. You have 25 identical liters to pour among 5 labelled buckets, and buckets can be empty. Line up the 25 liters as stars; the 4 dividers you insert decide where one bucket ends and the next begins.

Problem. Count integer solutions of x₁+x₂+x₃+x₄+x₅ = 40 with each xᵢ ≥ 3. The formula needs a floor of 0, so first pay off the minimums: substitute xᵢ = yᵢ + 3 with yᵢ ≥ 0. Each of the 5 variables donates 3, removing 15 from the total:

Now n = 25 stars, k = 5 bins: (25 + 5 − 1) C (5 − 1) = 29C4.

06Computing nCr in code#

For small n with no modulus, multiply it out directly. Only when n is large or the problem asks for "answer mod p" do you need factorials and modular inverses.

Small n: just multiply#

Most everyday problems have small numbers and no modulus. Build the answer one factor at a time, dividing as you go — the running value is always a valid binomial coefficient, so each division is exact.

long nCr(int n, int r) {
    if (r < 0 || r> n) return 0;
    r = Math.min(r, n - r);          // symmetry: fewer factors
    long c = 1;
    for (int i = 0; i < r; i++) c = c * (n - i) / (i + 1);   // exact at every step
    return c;
}

Large n or "answer mod p": factorials + inverses#

Why the naïve way fails. nCr = n! / (r!·(n−r)!). For large n the factorials overflow, so we work modulo a big prime (p = 10⁹+7). But you can't just "divide mod p" — division isn't defined on remainders. The fix is a modular inverse: a value that plays the role of 1/a in modular arithmetic.

Analogy — a factory that stamps parts once. Rather than recomputing each factorial and inverse per query (slow assembly), you run one precomputation pass that stamps out every factorial and every inverse-factorial into arrays. After that, answering a query is just picking three parts off the shelf and multiplying.

Fermat's little theorem gives the inverse cheaply when p is prime: a⁻¹ ≡ a^(p−2) (mod p), computed by fast exponentiation in O(log p). The clever part: you only need one such inverse — for the largest factorial — because the rest fall out of the relation invfact[i−1] = invfact[i]·i (since 1/(i−1)! = (1/i!)·i).

07The three identities that tie it together#

Three combinatorial identities let you compute and reason about binomial coefficients without factorials. Each has both an algebraic form and a "why" you can see in Pascal's triangle.

Pascal's identity — build the triangle#

Plain reading: to choose k items from n, either you include the last item (then choose k−1 from the first n−1) or you don't (choose k from the first n−1). Adding those two disjoint cases gives the total. This is the recurrence behind Pascal's triangle — and, crucially, it uses only addition, so it works for any modulus, prime or not.

Hockey stick identity — sum down a diagonal#

Fix the lower index r and sum as the upper index climbs from r to n. In Pascal's triangle these terms lie along a diagonal; their sum equals the single entry just below-and-left of the last term — the "blade" hanging off the diagonal "shaft," which is where the name comes from.

Vandermonde's identity — split the pool#

Plain reading: to choose r items from a combined pool of n+m, split the pool into a group of n and a group of m. Decide how many (k) come from the first group; the rest (r−k) come from the second. Summing over all splits of k reconstructs the whole count.

08Three more moves worth keeping#

A few reusable reframings that turn an unfamiliar count into one you already know. Each is a small substitution or symmetry — reach for them before grinding out casework.

Symmetry: choose the smaller half#

Choosing which r to include is the same as choosing which n−r to leave out, so the two counts are equal. Use it to compute the cheaper side: 100C98 is just 100C2 = 4950. It also halves the work when you build a row of Pascal's triangle — the row reads the same forwards and backwards.

Circular arrangements: pin one seat#

Around a round table there's no fixed "first" seat — every line-up can be rotated into n identical-looking copies, so the n! arrangements overcount by a factor of n. Pin one person down as the reference point and arrange the remaining n−1 around them: (n−1)! seatings. (If a reflection counts as the same seating too, divide by 2 more.)

Turning "≤" into "=" with a slack bin#

Stars and bars needs an exact sum, but plenty of problems ask for at most n. Introduce one extra bin that soaks up whatever is left over — it holds n − (x₁+…+x_k) ≥ 0. Now the constraint is a clean equality with k+1 bins and the formula applies directly. The slack variable is the "pay the minimum" substitution run in reverse.

09Interview & practice Q&A#

Click any question to reveal a spoken-length answer.

10Key takeaways#