Discrete Math · Counting Techniques
How to count arrangements and selections under constraints — casework vs. complementary counting, the stars-and-bars trick, repeated-letter permutations, fast modular nCr, and the identities that tie Pascal's triangle together.
Section 1
The whole topic at a glance. Keyword first, then the terse rule; everything here is unpacked below. Watch the margin markers: ⭐ trick, ⚠ pitfall, 💡 tip.
Two counting engines
Rounds problem (constraint: C1@R1 ⇒ not C2@R2)
Gap constraint · 8 books, ≥2 between A&B
At-most selection · committee 6 from 15, ≤1 of 3 special
Repeated letters · BALLOON, two O's together
Stars & bars · x₁+…+x₅=40, xᵢ ≥ 3
Computing nCr
Key identities
Section 2
Every technique from the ground up. Read this once and the reference above becomes pure recall.
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.
When a constraint is violated by only a handful of arrangements, count as if the rule didn't exist and subtract the violators. Here the violating set is exactly "C1 in R1 and C2 in R2 and anything in R3" = 1·1·3 = 3, so the answer is 60 − 3 = 57 in one line — no casework needed.
Interviewers love watching whether you reach for casework or complement. The tell: if you can describe the forbidden arrangements more simply than the allowed ones, complement is almost always faster and less error-prone.
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.
People remember to subtract the adjacent case and forget that "one book between" also violates "at least 2." You must remove both the 0-gap and 1-gap cases. Miss the 1-gap term and you'll be off by exactly 12·6! = 8640.
Any "these items stay together" condition becomes: treat them as a single block, arrange the blocks, then multiply by the internal arrangements of the block. Adjacent pair AB → one block → ×2! for its internal order. This "glue" move reappears in the BALLOON problem below.
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.
Order matters → permutation nPr = n! / (n−r)! (arrangements, like a podium of gold/silver/bronze). Order doesn't → combination nCr = n! / (r!·(n−r)!) (a plain group, like a committee). They differ by exactly the r! ways to reorder a chosen group: nPr = nCr · r!. Deciding "does order matter?" is the first question in almost every counting problem.
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.
"At most one" → cases {0, 1}. "At least one" → often easier as total − (none). "Exactly k" → one case. Translating the English phrase into the set of allowed counts is 80% of these problems; the arithmetic is the easy part.
The two cases are mutually exclusive outcomes, so they add. Within a single case, the independent sub-choices (which special, which others) multiply. Mixing these up — adding within a case or multiplying across cases — is the most common combinatorics error.
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).
"Keep OO together" (glue) and "L repeats" (divide by 2!) are independent adjustments to the base count. Apply glue first to fix the unit count, then divide by the factorials of whatever repeats remain among the units. They don't interfere.
When you glue distinct letters (like A and B earlier) you multiply by 2! for their internal order. When you glue identical letters (OO) the internal order is 1 — don't multiply. Blindly adding a ×2! for every glued block is a frequent slip.
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.
Any lower bound xᵢ ≥ m is handled by pre-assigning m to that variable (substitute xᵢ = yᵢ + m) so the leftover count starts at zero. Five variables each ≥ 3 simply reduce the target from 40 to 25 before you touch the formula.
(n+k−1)C(k−1) and (n+k−1)C(n) give the same number (choosing bar positions vs. star positions). Use whichever has the smaller lower index for hand computation: 29C4 is far easier than 29C25 even though they're equal.
Stars and bars only counts identical items into distinct bins with no upper limit. Upper bounds (e.g. xᵢ ≤ 7) break the formula and need inclusion–exclusion on top. Distinct items into bins is a different problem entirely (that's surjections / Stirling numbers).
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.
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;
}
If you'll query lots of nCr (or want to avoid overflow reasoning), fill a table with C[i][j] = C[i−1][j−1] + C[i−1][j] (section 07). Pure addition, no division, no modulus — and it doubles as the answer for any modulus.
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).
The whole speed-up hinges on computing a single modular inverse (of the biggest factorial) and deriving all others by a backward multiply. Computing an inverse for every factorial would add an O(N log p) factor for no reason. On large inputs that extra factor is the difference between a solution that finishes in time and one that doesn't.
Fermat's little theorem only gives the inverse when p is prime. If the modulus isn't prime, a^(p−2) is meaningless as an inverse — fall back to Pascal's recurrence in a DP table (next section), which never divides. Also always guard r<0 || r>n → 0 to avoid indexing garbage.
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.
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.
The factorial-inverse method (section 6) is faster but demands a prime modulus. When the modulus is composite, build an nCk DP table with Pascal's identity: slower (O(n·k)) but division-free and always correct.
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.
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.
A common slip on the hockey stick is to let the lower index drift; the identity keeps the lower index fixed (r) and slides the upper index from r up to n. The real payoff of all three, though, is the one-line story behind each — "include it or not" (Pascal), "sum a diagonal" (hockey stick), "split the pool" (Vandermonde). Those pictures are far easier to reconstruct under pressure than the algebra.
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.
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.
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.)
Circular seating, a necklace of beads, a cycle with no marked beginning — all overcount by the number of ways to rotate (and sometimes flip) the same object. Count as if positions were fixed, then divide by the size of that symmetry. It's the same "divide out what you can't tell apart" move as the repeated-letters formula.
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₁+…+xk) ≥ 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.
Whenever a constraint is an inequality, ask whether one new non-negative variable can make it an equality. "≤ n" becomes "= n" with a slack bin; "each xᵢ ≥ m" becomes "≥ 0" by pre-spending m. Reshaping the constraint is almost always easier than inventing a new formula.
Click any question to reveal a spoken-length answer.