Lesson 37 — Permutations and Arrangements

Definitions

Factorial

$n! = n \cdot (n-1) \cdot (n-2) \cdots 1$. Convention: $0! = 1$.

Growth:

Stirling's approximation: $n! \approx \sqrt{2\pi n}(n/e)^n$.

Simple permutation

$P_n = n!$ — ways to order $n$ distinct objects in a line.

Permutation with repetition

For $n$ objects with $n_1$ of type 1, $n_2$ of type 2, ..., $n_k$ of type $k$: $P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

Anagrams of "ARARA" (3 A's, 2 R's): $5!/(3! \cdot 2!) = 10$.

Simple arrangement

$A_n^p = n(n-1)(n-2) \cdots (n-p+1) = \frac{n!}{(n-p)!}$

Ways to order $p$ objects selected from $n$ available.

Circular permutation

$n$ objects in a circle: $(n-1)!$. Reason: the "first position" is arbitrary.

Difference between permutation and arrangement

• Permutation: uses all $n$ objects.
• Arrangement: selects $p \leq n$ and orders them.

When $p = n$: arrangement equals permutation.