Prerequisite:

The previous post established the four selection cases. Here we go deeper: circular arrangements, derangements, Pascal’s triangle, and the binomial theorem. These are the classical results every mathematician and algorithm designer should know cold.

Permutations of a Set

A permutation of a set $S$ of $n$ elements is a bijection $\sigma: S \to S$, equivalently an ordered arrangement of all $n$ elements. The set of all permutations of $S$ is denoted $S_n$ (the symmetric group), and $|S_n| = n!$.

Permutations with repetition. If items are not all distinct - say we have a multiset with $n$ elements where type $i$ appears $n_i$ times, and $\sum n_i = n$ - the number of distinct arrangements is the multinomial coefficient:

$$\binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! , n_2! \cdots n_k!}$$

Proof. Start with $n!$ arrangements of labeled items. For each type $i$, the $n_i!$ internal permutations of that type’s items produce identical arrangements, so divide by each $n_i!$.

Example. The word MISSISSIPPI has 11 letters: M(1), I(4), S(4), P(2). Distinct arrangements: $\frac{11!}{1!,4!,4!,2!} = 34{,}650$.

Circular Permutations

Arranging $n$ distinct objects in a circle (where only relative order matters, not starting position) gives $(n-1)!$ arrangements.

Proof. Fix one element to eliminate rotational equivalence. The remaining $n-1$ elements can be arranged in $(n-1)!$ ways.

If the circle also has reflective symmetry (e.g., a necklace), we further divide by 2: $\frac{(n-1)!}{2}$ distinct necklaces.

Derangements

A derangement is a permutation $\sigma$ of ${1, 2, \ldots, n}$ such that $\sigma(i) \neq i$ for all $i$ - no element appears in its original position. The number of derangements is $D_n$.

Theorem. $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$

Proof via inclusion-exclusion. Let $A_i$ be the set of permutations where element $i$ is fixed (i.e., $\sigma(i) = i$). We want $\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right| = n! - |A_1 \cup \cdots \cup A_n|$.

By inclusion-exclusion: $$|A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!$$ since fixing $k$ elements leaves $(n-k)!$ arrangements for the rest. There are $\binom{n}{k}$ such $k$-element subsets, so:

$$D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)! = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!} = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

The partial sums of $\sum_{k=0}^n (-1)^k/k!$ converge to $e^{-1}$, so $D_n \approx n!/e$ and the probability that a random permutation is a derangement approaches $1/e \approx 0.368$.

Values: $D_1 = 0,\ D_2 = 1,\ D_3 = 2,\ D_4 = 9,\ D_5 = 44$.

Recursive formula: $D_n = (n-1)(D_{n-1} + D_{n-2})$.

Pascal’s Triangle and Pascal’s Identity

Pascal’s Identity. $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Proof. Fix one element $x \in S$, $|S| = n$. Every $k$-subset either contains $x$ (choose the remaining $k-1$ from $n-1$ elements: $\binom{n-1}{k-1}$ ways) or does not (choose all $k$ from $n-1$ elements: $\binom{n-1}{k}$ ways).

Pascal’s triangle encodes this recursion: each entry is the sum of the two entries above it.

n=0:          1
n=1:        1   1
n=2:      1   2   1
n=3:    1   3   3   1
n=4:  1   4   6   4   1
n=5: 1  5  10  10   5   1

Row $n$ contains $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. The row sum is $\sum_{k=0}^n \binom{n}{k} = 2^n$.

The Binomial Theorem

Theorem (Binomial Theorem). For any $x, y$ and non-negative integer $n$: $$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$

Proof. Expanding $(x+y)^n$ means choosing, for each of the $n$ factors $(x+y)$, either $x$ or $y$. A term $x^k y^{n-k}$ arises from exactly those selections where $x$ is chosen in $k$ specific factors. The number of ways to choose which $k$ factors contribute $x$ is $\binom{n}{k}$.

Corollaries.

  • $\sum_{k=0}^n \binom{n}{k} = 2^n$ (set $x=y=1$).
  • $\sum_{k=0}^n (-1)^k\binom{n}{k} = 0$ (set $x=1, y=-1$).
  • $\sum_{k=0}^n k\binom{n}{k} = n \cdot 2^{n-1}$ (differentiate and set $x=y=1$).

Vandermonde’s Identity

Theorem (Vandermonde). For non-negative integers $m, n, r$: $$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$$

Proof. Count $r$-subsets of a set $S = A \cup B$ with $|A|=m$, $|B|=n$, $A \cap B = \emptyset$. A subset can take $k$ elements from $A$ and $r-k$ from $B$ for any $0 \leq k \leq r$; sum over $k$.

Special case $m = n = r$: $\binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2$.

CS Perspective: Generating Permutations and Fisher-Yates

Lexicographic generation. The standard algorithm generates all $n!$ permutations in lexicographic order in $O(1)$ amortized time per permutation:

  1. Find the rightmost position $i$ such that $\sigma(i) < \sigma(i+1)$.
  2. Find the smallest $\sigma(j) > \sigma(i)$ to the right of $i$.
  3. Swap $\sigma(i)$ and $\sigma(j)$, then reverse the suffix after position $i$.

Fisher-Yates shuffle. To generate a uniformly random permutation of $n$ elements in $O(n)$ time:

for i from n-1 down to 1:
    j = random integer in [0, i]
    swap A[i] and A[j]

Correctness. At step $i$, element $A[i]$ is chosen uniformly from $A[0..i]$. By induction, the resulting permutation is uniform over all $n!$ possibilities. A naive approach (pick a random permutation by repeatedly drawing random positions) runs in $O(n^2)$ or produces non-uniform distributions.

Derangement generation. Rejection sampling (generate a random permutation, reject if it has a fixed point) succeeds with probability $\approx 1/e$, so the expected number of trials is $e \approx 2.718$: an $O(n)$ expected-time algorithm.

Next: Inclusion-Exclusion - the general formula for counting unions and its applications to derangements, Euler’s totient, and sieve theory.

Read Next: