An Introduction to Combinatorics

Combinatorics is fascinating. It's about counting. The concept and exercises are often simple to understand, but the solutions can be tricky to find. Does order matter? Are repetitions allowed?

I wanted to write a short summary for myself where I could find the main formulas and have an intuitive proof of why they work. The proofs may not be extremely rigorous, but I think they are fairly easy to understand.

In these explanations, you will mainly encounter 2 letters, $n$ (the total number of elements in the set) and $k$ (the length of the sequence you want to get). For example, if you have an alphabet with 4 letters $a, b, c, d$ and you want to form a 2-letter password, then $n=4$ and $k=2$ .

With Order, Repetition Allowed

Example: How many unique 6-letter passwords can you create? (assuming that the allowed characters are A-Za-z0-9 for a total of 62 chars) → $62^6 = 56\,800\,235\,584$ .

Formula:

$\begin{aligned}n^k\end{aligned}$

Proof: We fill the $k$ positions one by one. Each position have $n$ possible elements because repetition is allowed. By the multiplication rule, the total number of sequences we can form is:

$\begin{aligned}\underbrace{n \times n \times \cdots \times n}_{k \text{ elements}} = n^k\end{aligned}$

$\square$

With Order, No Repetition

Example: How many ways can the top 3 finishers be arranged from 10 runners? → $\frac{10!}{7!} = 720$ .

Formula:

$\begin{aligned}P(n, k) = \frac{n!}{(n-k)!}\end{aligned}$

This is called a $k$ -permutation.

The number of $n$ -permutations is hence $P(n,n) = n!$ .

Proof: We fill the $k$ positions one by one. We have $n$ possible elements for the first position, $n-1$ for the second position (since repetition is not allowed and one element has been used)... and for the $k$ th element, there are $n-k+1$ choices. By the multiplication rule, the total number of sequences we can form is:

$\begin{aligned}n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}\end{aligned}$

$\square$

Without Order, Repetition Allowed

Example: How many ways to choose 3 scoops of ice cream from 5 flavors (flavors can repeat)? → $\binom{7}{3} = 35$ .

$\begin{aligned}\binom{n + k - 1}{k}\end{aligned}$

Proof: TODO, this one is harder. Try it on your own, I will publish it later.

Without Order, No Repetition

Example: How many 5-card hands can be drawn from a 52-card deck? → $\binom{52}{5} = 2\,598\,960$ .

$\begin{aligned}\binom{n}{k} = \frac{n!}{k!(n-k)!}\end{aligned}$

Proof: Let's define $S = \{ 1, \ldots, n \}$ . Each $k$ -permutation of $S$ arises only once as a result of these steps, done one after the other:

Take $k$ elements inside $S$ (no repetition, no order, like drawing $k$ balls from a bag containing $n$ balls numbered from $1$ to $n$ ). By definition this is $\binom{n}{k}$ .
Order these $k$ elements. There are $k!$ ways of ordering them (see $k$ -permutation proof above).

By the multiplication rule,

$\begin{aligned}\underbrace{\binom{n}{k}}_{1.}\,\underbrace{k!}_{2.} &= \underbrace{P(n,k)}_{\text{k-permutation of $S$}} \\ \binom{n}{k} &= \frac{P(n,k)}{k!} \\ \binom{n}{k} &= \frac{n!}{k!(n-k)!} \end{aligned}$

$\square$

If you are interested and want to know more, a good reference is Introductory Combinatorics by Richard A. Brualdi.

Unrelated "promotion" PS: If you’d like to support my work and build web apps quickly without tedious setup, consider buying my template 1Server 😉.