Permutations and Combinations

Factorial

For a positive integer $n$, the factorial is:

$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

By convention, $0! = 1$.

Factorials count the number of ways to arrange $n$ distinct objects in a sequence. The first position has $n$ choices, the second has $n-1$, and so on.

Example: Arranging Books

Six distinct books can be arranged on a shelf in $6! = 720$ ways.

Permutations

A permutation is an ordered arrangement of objects.

Permutations of $n$ Objects Taken $r$ at a Time

The number of ways to arrange $r$ objects selected from $n$ distinct objects:

$P(n, r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$

Intuition: We have $n$ choices for the first position, $n-1$ for the second, down to $n-r+1$ for the $r$th position.

Special case: $P(n, n) = n!$ arrangements of all $n$ objects.

Example: Committee Officers

From 10 people, select a president, vice-president, and treasurer. The order matters: select 3 and assign them to distinct roles.

$P(10, 3) = 10 \times 9 \times 8 = 720$

Combinations

A combination is an unordered selection of objects.

Combinations of $n$ Objects Taken $r$ at a Time

The number of ways to select $r$ objects from $n$ distinct objects (order does not matter):

$\binom{n}{r} = C(n, r) = \frac{n!}{r!(n-r)!}$

Why divide by $r!$? Each unordered selection corresponds to $r!$ ordered arrangements. The permutations overcount by exactly this factor.

Example: Selecting Books

How many ways to select 3 books from a set of 6?

$\binom{6}{3} = \frac{6!}{3! \cdot 3!} = \frac{720}{36} = 20$

Compare with permutations: $P(6, 3) = 120$. Each unordered set appears as $3! = 6$ permutations.

Example: Committee Members

From 10 people, select 3 committee members (no roles assigned):

$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{720}{6} = 120$

Key Properties of Binomial Coefficients

Symmetry

$\binom{n}{r} = \binom{n}{n-r}$

Intuition: Selecting $r$ objects to include is equivalent to selecting $n-r$ objects to exclude.

Pascal’s Identity

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Intuition: Any selection of $r$ from $n$ objects either includes a specific object (leaving $\binom{n-1}{r-1}$ ways) or excludes it (leaving $\binom{n-1}{r}$ ways).

Sum

$\sum_{r=0}^{n} \binom{n}{r} = 2^n$

This counts all subsets of an $n$-element set. Each element can be either in or out: $n$ independent binary choices.

Balls and Bins

The techniques extend to distributing objects into containers.

Distinct Balls into Distinct Bins

$n$ distinct balls into $k$ distinct bins: $k^n$ ways. Each ball independently chooses a bin.

Identical Balls into Distinct Bins

$n$ identical balls into $k$ distinct bins, no restrictions: equivalent to placing $k-1$ dividers among $n+k-1$ positions.

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

Intuition: Imagine placing all $n$ balls in a row with $k-1$ dividers. The balls before the first divider go to bin 1, between first and second dividers to bin 2, and so on.

Example: Server Distribution

13 servers into 3 datacentres with capacities 6, 4, and 3. This counts arrangements where we partition the 13 labelled servers into groups of those sizes:

$\binom{13}{6} \binom{7}{4} \binom{3}{3} = 1716 \times 35 \times 1 = 60{,}060$

Alternatively: $\frac{13!}{6! \cdot 4! \cdot 3!}$ (multinomial coefficient).

Permutations with Repetition

When some objects are identical, the number of distinct arrangements is:

$\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

where $n_i$ is the number of objects of type $i$.

Example: DNA Sequences

How many distinct sequences can be formed from 3 A’s, 2 C’s, 1 G, and 1 T?

$\frac{7!}{3! \cdot 2! \cdot 1! \cdot 1!} = \frac{5040}{12} = 420$

Example: Bit Strings

Distinct bit strings from three 0’s and two 1’s:

$\frac{5!}{3! \cdot 2!} = \frac{120}{12} = 10$

These are: 00111, 01011, 01101, 01110, 10011, 10101, 10110, 11001, 11010, 11100.

Hypergeometric Formula

When sampling without replacement, we use hypergeometric counts.

Select $n$ items from a population of $N$ containing $m$ “special” items. The number of ways to get exactly $i$ special items:

$\binom{m}{i} \binom{N-m}{n-i}$

Choose $i$ special items from the $m$ available, and $n-i$ ordinary items from the $N-m$ non-special.

Summary Table

Problem	Formula
Arrange all $n$ objects	$n!$
Arrange $r$ from $n$	$P(n,r) = \frac{n!}{(n-r)!}$
Choose $r$ from $n$	$\binom{n}{r} = \frac{n!}{r!(n-r)!}$
Arrange with repetitions	$\frac{n!}{n_1! \cdots n_k!}$
$n$ identical into $k$ bins	$\binom{n+k-1}{n}$