Combinatorics

Overview

Combinatorics is the art of counting. In quant interviews, computing a classical probability always reduces to counting — favorable outcomes over total outcomes. This topic covers the four fundamental counting structures, the binomial theorem, and the key problem-solving tools (inclusion-exclusion, pigeonhole, complement) that appear repeatedly in interview problems.

1. Counting Principles

1.1 Principle of Multiplication

Definition

Let $E_1, E_2, \ldots, E_k$ be finite sets. The number of ways to perform $k$ successive independent choices, where choice $i$ has $n_i = |E_i|$ options, is:

\boxed{|E_1 \times E_2 \times \cdots \times E_k| = \prod_{i=1}^{k} n_i}

Example

A PIN code has 4 digits, each chosen from $\{0, \ldots, 9\}$ . Total number of codes: $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ .

1.2 Principle of Addition

Definition

Let $E_1, E_2, \ldots, E_n$ be pairwise disjoint finite sets ( for ). Then:

Remarque

The disjointness condition is essential. If the sets overlap, you must use the Inclusion-Exclusion principle (see section 5.1). The addition principle is the special case of inclusion-exclusion where all intersections are empty.

Example

A password must start with either a letter (26 choices) or a digit (10 choices), but not both. Number of valid first characters: $26 + 10 = 36$ .

2. Arrangements

2.1 Full Permutation

Definition

A permutation of a set of $n$ distinct elements is a bijection from $\{1, \ldots, n\}$ to itself, i.e. an ordered arrangement of all $n$ elements. The number of permutations of $n$ elements is:

n! = n \times (n - 1

Example

Number of ways to arrange 5 books on a shelf: $5! = 120$ .

2.2 Arrangement without repetition

Definition

An arrangement of $k$ elements chosen from $n$ distinct elements, where order matters and each element is used at most once, is called a $k$ -arrangement of $n$ . The number of such arrangements is:

A_{n}^{k} = \frac{n!}{(n - k)!} = n (n - 1) \dots (n - k + 1

Example

Number of ways to assign gold, silver, and bronze medals among 10 athletes: $A_{10}^3 = 10 \times 9 \times 8 = 720$ .

💡Tip

Use $A_n^k$ whenever the problem involves ranking or ordered selection without replacement — podium positions, scheduling, assigning distinct roles to people.

2.3 Arrangement with repetition

Definition

A sequence of length $k$ over an alphabet of $n$ distinct elements, where each element may be used multiple times, is a function from $\{1, \ldots, k\}$ to the alphabet. The number of such sequences is:

\boxed{n^k}

💡Tip

Use $n^k$ for passwords, binary strings, dice roll sequences, or any problem where each step has the same $n$ independent options. Key special cases: $2^k$ for binary strings, $6^k$ for sequences of dice rolls.

2.4 Multiset Permutation

Definition

Given $n$ elements where element $i$ appears $n_i$ times with $\displaystyle\sum_{i=1}^{r} n_i = n$ , the number of distinct ordered arrangements is:

Example

Number of distinct arrangements of the letters in MISSISSIPPI — M×1, I×4, S×4, P×2, total $n = 11$ :

\frac{11!}{1!\,4!\,4!\,2!} = 34{,}650

3. Combinations

3.1 Combination (unordered, no repetition)

Definition

A combination of $k$ elements from a set of $n$ distinct elements is a subset of size $k$ , where order does not matter and each element appears at most once. The number of such subsets is:

\boxed{\binom{n}{k} = C_n^k = \frac{n!}{k!\,(n-k)!}}

Properties

$\binom{n}{k} = \binom{n}{n-k}$ (symmetry)

Example

Number of 5-card hands from a standard 52-card deck: $\binom{52}{5} = 2{,}598{,}960$ .

3.2 Combination with Repetition — Stars & Bars

Definition

The number of ways to choose $k$ elements from $n$ distinct types where order does not matter and repetition is allowed equals the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_n = k$ , and is given by:

Remarque

For strictly positive solutions ( $x_i \geq 1$ ), substitute $y_i = x_i - 1$ to reduce to the non-negative case, giving .

Example

How many ways to choose 3 scoops from 5 flavors, repetition allowed? $\binom{7}{3} = 35$ .

How many ways to distribute 10 identical balls into 4 distinct boxes?

\binom{10+4-1}{3} = \binom{13}{3} = 286

💡Tip

Use stars and bars whenever you distribute identical objects into distinct containers, or count integer solutions to a sum constraint. If objects are distinct, use the multiplication principle instead.

4. Binomial Theorem & Identities

4.1 Binomial Theorem

Theorem

For any $a, b \in \mathbb{R}$ and $n \in \mathbb{N}$ :

\boxed{(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}}

Example

$(1 + x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ .

4.2 Key Identities

Properties

$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ (set )

💡Tip

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$ counts all subsets of an -element set — the most tested identity. The alternating sum is useful to verify that a combinatorial expression sums to zero or to evaluate telescoping sums.

5. Advanced Techniques

5.1 Inclusion-Exclusion

Theorem

For any finite sets $A_1, \ldots, A_n$ :

∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{i} ∣ A_{i} ∣ - \sum_{i <}

Example

How many integers from 1 to 100 are divisible by 2 or 3? We have $|A_2| = 50$ , $|A_3| = 33$ , , so .

💡Tip

Use inclusion-exclusion when counting elements satisfying at least one of several conditions. For divisibility problems: $|A_p| = \lfloor N/p \rfloor$ and $|A_p \cap A_q| = \lfloor N / \text{lcm}(p,q) \rfloor$ .

5.2 Pigeonhole Principle

Theorem

If $n$ objects are distributed into $k$ containers with $n > k$ , then at least one container contains at least:

\boxed{\left\lceil \frac{n}{k} \right\rceil \text{ objects}}

Remarque

This is a pure existence theorem — it guarantees that a configuration must exist without constructing it. In interviews it appears as "prove there must exist two objects sharing property P" or "show that some value must repeat."

Example

In any group of 13 people, at least 2 share the same birth month (13 people, 12 months $\Rightarrow \lceil 13/12 \rceil = 2$ ).

5.3 Complement Counting

Definition

Given a sample space $\Omega$ and a desired event $A$ , complement counting computes $|A|$ indirectly via its complement $\overline{A} = \Omega \setminus A$ :

💡Tip

Use complement counting whenever the condition is "at least one" or "not all" — their complements ("none" or "all") are usually straightforward. The Birthday Problem is the canonical example: $P(\text{at least 2 share a birthday among } n) = 1 - \frac{365 \times 364 \times \cdots \times (365-n+1)}{365^n}$ .

6. Quick Reference

Decision Table — Which Formula?

Order matters?	Repetition allowed?	Formula	Name
✅ Yes	✅ Yes	$n^k$	Sequence with repetition
✅ Yes	❌ No	$\dfrac{n!}{(n-k)!}$	Arrangement