Permutations

Definition

A permutation is an ordered arrangement of objects.

Permutations without Repetition

All $n$ Objects

The number of ways to arrange $n$ distinct objects: $P(n) = n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

Example: Arrange letters A, B, C, D: $4! = 24 \text{ ways}$

$r$ Objects from $n$ (r-permutations)

The number of ways to arrange $r$ objects from $n$ distinct objects: $P(n, r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$

Example: First 3 places from 8 runners: $P(8, 3) = 8 \times 7 \times 6 = 336$

Permutations with Repetition

Arranging with Unlimited Supply

If we can use each of $n$ types of objects any number of times, arrangements of length $r$: $n^r$

Example: 4-digit PIN using digits 0-9: $10^4 = 10,000$

Arranging with Fixed Counts

If we have $n$ objects where:

• $n_1$ are of type 1
• $n_2$ are of type 2
• ...
• $n_k$ are of type $k$

And $n_1 + n_2 + \cdots + n_k = n$: $\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

Example: Arrangements of MISSISSIPPI:

• 11 letters: 1 M, 4 I's, 4 S's, 2 P's $\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \cdot 24 \cdot 24 \cdot 2} = 34,650$

Circular Permutations

Arrangements in a circle where only relative positions matter: $(n-1)!$

Why? Fix one object to remove rotational equivalence, arrange remaining $n-1$.

With Reflections Considered Same

If reflections (flipping) also count as same: $\frac{(n-1)!}{2}$

Example: Seating 6 people around a table:

• Rotations same: $(6-1)! = 120$
• Rotations and reflections same: $\frac{5!}{2} = 60$

Permutations with Restrictions

Adjacent Constraints

Objects must be adjacent: Treat them as a single "super-object".

Example: Arrange ABCDE with A and B adjacent:

1. Treat AB as one unit: arrange 4 units = $4!$
2. A and B can swap within: $2!$
3. Total: $4! \times 2! = 48$

Objects must NOT be adjacent: Total minus adjacent cases.

Position Constraints

Example: Arrange 1,2,3,4,5 so that 1 is not first and 5 is not last:

• Total: $5! = 120$
• 1 is first: $4! = 24$
• 5 is last: $4! = 24$
• 1 first AND 5 last: $3! = 6$
• Answer: $120 - 24 - 24 + 6 = 78$

Relative Order Constraints

Example: Arrange ABCDE so A comes before B: By symmetry, A before B in exactly half: $\frac{5!}{2} = 60$

Derangements

A derangement is a permutation where no element is in its original position.

The number of derangements of $n$ elements: $D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} = n! \left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

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

With $D_0 = 1$ and $D_1 = 0$.

$n$	$D_n$	$D_n/n!$
0	1	1
1	0	0
2	1	0.5
3	2	0.333
4	9	0.375
5	44	0.367

As $n \to \infty$: $D_n/n! \to 1/e \approx 0.368$

Permutation as Functions

A permutation of set $S$ can be viewed as a bijection $\sigma: S \to S$.

Cycle Notation

$(1 \; 3 \; 2)$ means: $1 \to 3 \to 2 \to 1$

Every permutation decomposes into disjoint cycles.

Permutation Composition

Apply right to left: $\sigma \circ \tau$ means first $\tau$, then $\sigma$.

Identity Permutation

$e$ or $\text{id}$: every element maps to itself.

Inverse Permutation

$\sigma^{-1}$: reverse each cycle's direction.