Deriving Permutation and Combination Formulas: A Step‑by‑Step Guide

Preface: The author pays tribute to Stephen Hawking’s spirit and writes this series to honor him.

Permutation Formula Derivation and Proof

Definition: From a set of n distinct elements, selecting m (where m ≤ n ) elements and arranging them in order forms a permutation; the total number of such arrangements is the permutation number A(n,m).

Formula:

(When n = m , the denominator is 0! = 1, so A(m,m) = m!, which is the full permutation.)

Derivation: In a set of n numbers, choose the first element in n ways, the second in n‑1 ways, …, the m ‑th in n‑m+1 ways, and the last step has only one choice. Multiplying these choices gives n(n‑1)(n‑2)…(n‑m+1) = n!/(n‑m)!.

Combination Formula Derivation and Proof

Definition: From a set of n distinct elements, selecting m (where m ≤ n ) elements without regard to order forms a combination; the total number of such groups is the combination number C(n,m).

Formula:

Derivation: First compute the permutation number A(n,m). Since a combination is unordered, divide by the number of ways to order the m selected elements, which is A(m,m)=m!. Thus C(n,m)=A(n,m)/m!.

Proof: A(n,m) = C(n,m) * A(m,m). Step 1: Choose m elements from n (combination). Step 2: Arrange those m elements (full permutation). Applying the multiplication principle confirms the formula.

Repeated Combination Formula Derivation and Proof

Definition: A repeated combination allows selecting m elements from n distinct elements with replacement, forming a multiset.

Formula:

Analysis (Ball‑and‑Separator Model): Treat the n distinct elements as n boxes separated by n‑1 identical dividers. Place m identical balls into these boxes. The number of ways equals the number of permutations of m + n‑1 items divided by the repetitions of the identical balls and dividers: (m+n‑1)! / (m! (n‑1)!).

Combination Identity Formula

Readers are encouraged to derive the identity themselves.