Combinatorics Basics

Why Counting Without Enumerating Matters

Combinatorics is the part of algorithms that asks “how many?” without listing every possibility. That is incredibly useful because the list of possibilities usually grows too fast to inspect directly. A grid path problem may have thousands of routes. An arrangement problem may have millions of orderings. A probability question may depend on the number of favorable outcomes divided by the number of total outcomes. If you can count structurally instead of generating every case, many seemingly exponential problems collapse into a few arithmetic operations.

The core distinctions are simple but important. Factorials count full orderings. Permutations count ordered selections of part of a set. Combinations count unordered selections where order does not matter. Pascal’s triangle packages the recurrence behind combinations into a reusable table. And in programming contests or interview settings, a modulus is often added because the exact count becomes enormous. This lesson connects those ideas instead of treating them as isolated formulas.

Factorials, Permutations, and Combinations

A factorial counts how many ways n distinct items can be ordered. For 4 books on a shelf, the first position has 4 choices, the second has 3 remaining choices, then 2, then 1. That product is 4! = 24. If you only need to choose and order r items from n, the count is nPr = n! / (n-r)!. You are taking the first r decisions of the full ordering process and ignoring the rest.

Combinations remove order from the story. Suppose you choose a 3-person committee from 5 candidates. If you first count ordered selections, each unordered committee gets counted 3! times, once for every internal ordering of the chosen people. That is why nCr = n! / (r!(n-r)!). You start from the ordered count and divide out the overcount caused by treating different internal orders of the same group as different outcomes.

Choose 2 from {A, B, C}

Permutations (order matters): AB, AC, BA, BC, CA, CB -> 6 = 3P2
Combinations (order does not matter): AB, AC, BC -> 3 = 3C2

Pascal’s Triangle and the Combination Recurrence

Pascal’s triangle is not just a nice picture. It is the recurrence behind combinations: C(n, r) = C(n-1, r-1) + C(n-1, r). The reasoning is beautifully concrete. Focus on one specific element, say the person named Maya. Every size-r group either includes Maya or does not. Groups that include Maya need r-1 more elements from the remaining n-1 people. Groups that exclude Maya need all r elements from the remaining n-1. Add those two cases and you get the recurrence.

This recurrence is valuable when factorial formulas are awkward or when you want all values for many rows. It also creates a direct bridge to dynamic programming. Build row 0 as [1], then each new row starts and ends with 1, while every interior value is the sum of the two values above it. You are literally counting how many ways to reach each state through two simpler predecessor states.

Worked Example: Unique Paths as a Combination

Consider a 3 by 7 grid where a robot starts at the top-left corner and must reach the bottom-right corner by moving only right or down. The robot must move down exactly 2 times and right exactly 6 times, for a total of 8 moves. So the problem is not really about path simulation. It is about choosing which 2 of the 8 move slots will be downward moves. That count is C(8, 2) = 28, which is the same as C(8, 6) by symmetry.

You can also see the same answer through Pascal’s recurrence. Each cell’s path count equals the sum of the counts from the cell above and the cell to the left, because every path into the current cell must come from one of those two directions. The combinatorial formula and the DP table are two views of the same structure. One counts move positions directly; the other counts ways to arrive locally step by step.

That dual view is worth remembering because some problems are easier to model locally, while others are easier to count globally. If obstacles appear in the grid, the direct combination shortcut usually breaks and the DP view survives. If the grid is large and empty, the combinatorial view may be far cleaner than filling an entire table. Good problem solving often means switching between these equivalent interpretations until one of them matches the constraints naturally.

Computing nCr mod p Efficiently

When n is large and many queries arrive, recomputing factorials from scratch is wasteful. The standard approach under a prime modulus p is to precompute factorial[i] = i! mod p and inverseFactorial[i] = (i!)^{-1} mod p. Then nCr mod p becomes factorial[n] × inverseFactorial[r] × inverseFactorial[n-r] mod p. The only remaining question is how to compute modular inverses efficiently.

For a prime modulus, Fermat’s little theorem gives a clean answer: a^(p-1) ≡ 1 mod p for any a not divisible by p, so a^(p-2) behaves like the modular inverse of a. That means the fast exponentiation machinery from the previous lesson becomes directly useful here. Precompute factorials once, compute inverse factorials with modPow, and each combination query becomes O(1). This is one of the best examples of DSA topics reinforcing each other instead of living in separate chapters.

Go Implementation

The implementation below packages the precomputation into a small combiner type. This is a common contest and interview pattern because it keeps the expensive work in one constructor and makes each query trivial.

Common Mistakes and Interview Signals

A frequent mistake is applying the combination formula with plain integer division after already taking values modulo p. Ordinary division does not make sense under a modulus the way multiplication does; you need modular inverses. Another mistake is forgetting to ask whether order matters. If the interviewer says “ways to choose,” think combinations. If they say “arrangements,” “rankings,” or “ordered sequences,” think permutations or full factorial-style counting.

Another interview signal is repeated counting queries with the same upper bound. If the prompt asks for many nCr values, that is a clue that preprocessing is welcome. If it asks for one modest answer, a direct multiplicative formula may be simpler and less error-prone. Counting problems are full of these context switches, so the goal is not to memorize one formula, but to match the computation strategy to the scale and shape of the query workload.

Practice Problems

Quiz

Summary

• Factorials count full orderings, permutations count ordered selections, and combinations count unordered selections.
• Pascal’s triangle is the dynamic-programming form of the combination recurrence.
• Many path-counting problems are really slot-selection problems in disguise.
• For many queries under a prime modulus, precompute factorials and inverse factorials.
• Always ask whether order matters before choosing a counting formula.