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:

n^k

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

\underbrace{n \times n \times \cdots \times n}_{k \text{ elements}} = n^k

With Order, No Repetition

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

Formula:

P(n, k) = \frac{n!}{(n-k)!}

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. The first position has $n$ choices, the second has $n-1$ (one element is already used and repetition is not allowed), the third has $n-2$ , and so on. The $k$ th position has $n-k+1$ choices left. By the multiplication rule, the total number of sequences we can form is:

n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}

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$ .

\binom{n + k - 1}{k}

Proof: A selection is fully described by how many items we pick of each type. So we just need to count solutions to:

x_1 + x_2 + \cdots + x_n = k, \quad x_i \geq 0

where $x_i$ is the number of times type $i$ is picked.

This is the stars and bars trick. Represent each picked item with a star ( $\star$ ) and use bars ( $\mid$ ) to separate the $n$ types. With $n=5$ flavors and $k=3$ scoops, picking 2 of flavor 1 and 1 of flavor 3 looks like:

\underbrace{\star \, \star}_{\text{flavor 1}} \mid \underbrace{\phantom{\star}}_{\text{flavor 2}} \mid \underbrace{\star}_{\text{flavor 3}} \mid \underbrace{\phantom{\star}}_{\text{flavor 4}} \mid \underbrace{\phantom{\star}}_{\text{flavor 5}}

Every selection becomes a row of $k$ stars and $n-1$ bars, $n+k-1$ symbols in total. Picking a selection is the same as picking which $k$ of those $n+k-1$ positions hold a star:

\binom{n+k-1}{k}

Without Order, No Repetition

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

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Proof: Let $S = \{ 1, \ldots, n \}$ . Every $k$ -permutation of $S$ can be built in exactly one way by:

Taking $k$ elements from $S$ (no repetition, no order, like drawing $k$ balls from a bag of $n$ numbered balls). By definition this is $\binom{n}{k}$ .
Ordering these $k$ elements. There are $k!$ ways to do this (as proven 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}

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