Permutations & Combinations – Advanced Study Notes
MIT‑Level, First‑Principles Treatment
Notation
- (n!) = factorial of (n) (product of the first (n) positive integers).
- (\binom{n}{k}) = binomial coefficient ("(n) choose (k)").
- (P(n,k) = \frac{n!}{(n-k)!}) = number of (k)-permutations of an (n)-set.
- (Q(n,k)) = number of (k)-combinations of an (n)-set.
1. Fundamental Principle of Counting
Theorem (Multiplication Principle).
If a process can be broken into (m) successive stages, where stage (i) can be performed in (a_i) ways (independent of previous stages), then the total number of ways to perform the whole process is (\prod_{i=1}^{m} a_i).
Proof.
We may view the set of all possible sequences ((x_1,\dots,x_m)) with (x_i\in X_i) and (|X_i|=a_i). The Cartesian product (X_1\times\cdots\times X_m) has (\prod a_i) elements. ∎
This principle underlies every counting argument.
2. Permutations
2.1 Permutations of Distinct Elements
Definition.
Given a set (S={1,2,\dots,n}), a permutation is a bijection (\sigma:S\to S). The set of all permutations is the symmetric group (S_n).
Theorem.
(|S_n| = n!).
Proof.
Choose the image of 1: (n) possibilities.
Choose the image of 2: (n-1) possibilities (since 1 is already used).
Continue until the last element. Multiply by the multiplication principle: (n(n-1)\cdots 1 = n!). ∎
2.2 (k)-Permutations (Partial Orderings)
Definition.
A (k)-permutation of an (n)-set is an ordered (k)-tuple of distinct elements.
Theorem.
(P(n,k)=\dfrac{n!}{(n-k)!}).
Proof.
Choose the first element: (n) ways.
Choose the second: (n-1) ways, …, choose the (k)-th: (n-k+1) ways. Multiply: (n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}). ∎
2.3 Permutations of a Multiset
Let a multiset contain (n) objects with multiplicities (m_1,m_2,\dots,m_r) ((\sum m_i = n)).
Theorem (Multiset Permutation Formula).
The number of distinct linear arrangements is
[
\frac{n!}{m_1! m_2! \cdots m_r!}.
]
Proof.
Start with (n!) permutations of (n) labeled tokens. Tokens of the same type are indistinguishable, so each arrangement is counted (m_i!) times for each type. Divide by all such overcounts. ∎
2.4 Permutations with Restrictions
2.4.1 Fixed Points & Derangements
A fixed point of (\sigma) satisfies (\sigma(i)=i).
A derangement is a permutation with no fixed points.
Theorem (Derangement Count).
Let (D_n) denote the number of derangements of (n) items. Then
[
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.
]
Proof (Inclusion–Exclusion).
Let (A_i) be the set of permutations fixing (i).
[
|A_i| = (n-1)!,\quad |A_i\cap A_j| = (n-2)!,\dots
]
Apply inclusion–exclusion:
[
n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n \binom{n}{n} 0! = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.
]
∎
2.4.2 Circular Arrangements
For arranging (n) distinct objects around a circle (up to rotation), the count is ((n-1)!).
Proof. Fix one object in a reference position to break rotational symmetry; the remaining (n-1) can be arranged arbitrarily. ∎