Combinatorics

Definition: The field of discrete math concerned with counting, arrangement, and combination of elements from finite sets, without necessarily listing every possibility explicitly.

How It Works

Permutations P(n, r) = n! / (n - r)!: ordered arrangements of r items chosen from n, order matters, AB and BA count separately
Combinations C(n, r) = n! / (r!(n - r)!): unordered selections of r items from n, order does not matter, AB and BA count as the same selection
The Multiplication Principle: if one choice can be made in m ways and a second, independent choice in n ways, the two together can be made in m × n ways
Factorial notation n! (n × (n-1) × ... × 1) counts the number of ways to arrange n distinct items in a sequence, with 0! = 1 defined by convention so the formulas stay consistent at the boundary
The Addition Principle: if a choice can be made via method A in m ways or method B in n mutually exclusive ways, the total is m + n
Complementary counting flips a hard “at least one” question into an easier one: count everything, then subtract the cases with none, often far simpler than counting the “at least one” cases directly
The Pigeonhole Principle: if n items are placed into m containers and n > m, at least one container holds more than one item, a purely structural guarantee, not a probability
Permutations with repetition allowed use n^r instead of n!/(n-r)!, since each of the r positions independently has all n choices available again
Combinations with repetition (multisets) use the “stars and bars” formula C(n + r - 1, r), for selecting r items from n types where repeats are allowed
Binomial coefficients C(n, r) are exactly the entries of Pascal’s Triangle, and appear directly in the Binomial Theorem’s expansion of (x + y)^n
The Inclusion-Exclusion Principle corrects for overlap when counting the union of overlapping sets: |A ∪ B| = |A| + |B| - |A ∩ B|, generalizing to any number of sets

Formula Reference

Scenario	Formula	Example use
Ordered, no repeats	`P(n,r) = n!/(n-r)!`	Ranking 3 winners from 10 racers
Unordered, no repeats	`C(n,r) = n!/(r!(n-r)!)`	Choosing a 5-person committee from 20
Ordered, repeats allowed	`n^r`	4-digit PIN codes (digits can repeat)
Unordered, repeats allowed	`C(n+r-1, r)`	Choosing 3 scoops from 5 ice cream flavors, repeats allowed
Distinct arrangements with duplicates	`n! / (n1!·n2!·...)`	Arranging letters in a word with repeated letters

Under the Hood

This tree is P(3, 2) made visible: 3 choices for the first letter, then 2 remaining choices for the second, giving 3 × 2 = 6 leaves, matching P(3,2) = 3!/(3-2)! = 6/1 = 6. Each leaf is a distinct ordered outcome. If order didn’t matter, AB and BA would collapse into one outcome, AC/CA into another, and BC/CB into another, leaving exactly C(3,2) = 3 distinct groups, which is the tree’s leaf count divided by 2!, the number of ways to order each pair internally.

This division is the general relationship between the two formulas: C(n, r) = P(n, r) / r!, because every unordered selection of r items corresponds to exactly r! different ordered arrangements of that same selection. Overcounting by exactly that factor and then dividing it back out is the entire mechanical difference between “how many ordered lists” and “how many groups.”

Pascal’s Triangle makes this same relationship visible row by row: row n lists C(n,0), C(n,1), ..., C(n,n) left to right, and each entry is the sum of the two entries diagonally above it in the previous row, a direct consequence of the identity C(n,r) = C(n-1,r-1) + C(n-1,r).

Worked Example 1

Given: A committee of 3 people must be selected from a pool of 8 candidates, with no distinct roles, just membership.
Step: Order doesn’t matter (any member is just “on the committee”), so use combinations: C(8, 3) = 8! / (3! · 5!).
Answer: C(8,3) = (8·7·6)/(3·2·1) = 336/6 = 56 possible committees.

Worked Example 2

Given: The same pool of 8 candidates, but now selecting a President, a Secretary, and a Treasurer, three distinct roles.
Step: Order matters now because who gets which role changes the outcome, so use permutations: P(8, 3) = 8! / 5!.
Answer: P(8,3) = 8·7·6 = 336 possible assignments, exactly 3! = 6 times more than the unordered count, matching C(n,r) = P(n,r)/r!.

Worked Example 3

Given: Prove that in any group of 367 people, at least two must share the same birthday (ignoring leap years, 365 possible dates).
Step: There are 367 people (items) and only 365 possible birthdays (containers). Since 367 > 365, the Pigeonhole Principle applies directly.
Answer: At least one date must be shared by at least two people, a certainty, not a probability, regardless of which 367 people are chosen.

Worked Example 4

Given: A pizza shop offers 5 toppings, and a customer can choose any number of them, including zero or all five, for one pizza.
Step: Each of the 5 toppings independently has 2 states, included or not, so by the Multiplication Principle the total is 2 × 2 × 2 × 2 × 2 = 2^5.
Answer: 32 distinct possible pizzas, including the plain, no-topping pizza and the fully-loaded one.

Worked Example 5

Given: An ice cream shop has 5 flavors, and a customer orders a 3-scoop cone where the same flavor can repeat and order doesn’t matter (a scoop of vanilla-vanilla-chocolate is the same cone regardless of stacking order).
Step: This is combinations with repetition: C(n + r - 1, r) = C(5 + 3 - 1, 3) = C(7, 3).
Answer: C(7,3) = 7!/(3!·4!) = 35 distinct possible cones, far fewer than the 5^3 = 125 you’d get if order mattered and repeats were counted as ordered sequences.

Why It Matters

Essential for algorithmic probability analysis, cryptography key-space calculations, and brute-force search space estimation before deciding whether an exhaustive search is even feasible
Directly determines password and cryptographic key strength, a keyspace of 62^8 (alphanumeric, 8 characters) versus 62^16 is the difference between crackable and computationally infeasible
Guides database query planning and test coverage design, knowing how many distinct input combinations exist tells a team whether exhaustive testing is realistic or sampling is required
Underlies probability theory entirely, most classical probability calculations reduce to counting favorable outcomes over total outcomes, both combinatorics problems
Drives algorithm complexity analysis, recognizing a problem’s search space is C(n,k) rather than n^k can be the difference between an intractable brute force and a feasible one
Powers lottery and gambling odds calculations, the near-impossible odds of a jackpot are a direct combinations calculation over the ticket’s number pool
Sizes hash table load factors and collision probability, the Birthday Paradox’s underlying math directly predicts how quickly hash collisions start appearing as a table fills up

Common Pitfalls

Double-counting or under-counting by failing to distinguish ordered (permutation) from unordered (combination) selections, the single most common combinatorics error
Forgetting to divide by the repeated-arrangement factor when items are indistinguishable, arranging the letters of “MISSISSIPPI” needs 11! divided by 4!·4!·2! for the repeated I, S, and P letters
Computing large factorials directly instead of canceling common terms first, 100!/98! should be simplified to 100 × 99 algebraically, not computed as two enormous numbers then divided
Applying the Multiplication Principle to choices that aren’t actually independent, when an earlier choice restricts what’s available later, the simple product overcounts
Misapplying the Pigeonhole Principle by rounding incorrectly, “at least one container has more than one item” requires strictly n > m, not n ≥ m
Confusing C(n+r-1, r) (combinations with repetition) with plain C(n, r), using the wrong formula whenever a problem allows repeated selections
Ignoring the Inclusion-Exclusion correction when two counted categories overlap, adding |A| + |B| directly double-counts anything in both
Overlooking that “at least one” phrasing often signals complementary counting is easier, computing the total minus the zero-occurrence case instead of summing every “exactly k” case separately

Comparison

	Permutations	Combinations	With Repetition	Pigeonhole Principle
Order matters	Yes	No	Depends on variant	N/A, existence argument
Formula	`n!/(n-r)!`	`n!/(r!(n-r)!)`	`n^r` or `C(n+r-1,r)`	N/A
Answers	“How many ordered arrangements?”	“How many groups?”	“How many with repeats allowed?”	“Must a collision exist?”
Typical use	Rankings, passwords, sequences	Committees, lottery numbers, subsets	Passwords with repeat characters allowed	Proving forced collisions/matches
Grows how fast (in n)	Factorial	Factorial, but smaller than P(n,r)	Exponential	N/A
Common mistake	Forgetting order matters	Using n! instead of dividing by r!	Using the no-repeat formula by mistake	Off-by-one on the inequality

Example

The Pigeonhole Principle: in any group of 367 people, at least two must share the exact same birthday, a classic, rigorous proof that requires no probability, statistics, or assumptions about the people involved, only the count 367 exceeding 365 possible dates.

RSA and other public-key cryptosystems rest on combinatorial keyspace size: a 2048-bit RSA key draws from a search space so large (on the order of 2^2048 possibilities) that even the fastest supercomputers cannot brute-force it within any practical timeframe, a direct application of the same counting principles used to size a lock’s combination space.

Referenced by

Dig deeper

Spot an error in this note?