Skip to content

Mathematics · Ch 4 — Combinatorics and Mathematical Induction

Properties of Permutations

4.4.2

Properties of Permutations

Three algebraic identities connect permutations of related orders, each proved directly from nPr=n!(n−r)!^nP_r=\dfrac{n!}{(n-r)!}.

Property 1. nPn=nPn−1^nP_n = {}^nP_{n-1}.

Proof. nPn−1=n!(n−(n−1))!=n!1!=n!=n!(n−n)!=nPn^nP_{n-1}=\dfrac{n!}{(n-(n-1))!}=\dfrac{n!}{1!}=n!=\dfrac{n!}{(n-n)!}={}^nP_n.

Property 2 (the reduction formula). nPr=n×n−1Pr−1^nP_r = n\times{}^{n-1}P_{r-1}.

Proof. n×n−1Pr−1=n×(n−1)!((n−1)−(r−1))!=n!(n−r)!=nPrn\times{}^{n-1}P_{r-1}=n\times\dfrac{(n-1)!}{((n-1)-(r-1))!}=\dfrac{n!}{(n-r)!}={}^nP_r. Iterating, nPr=n×n−1Pr−1=n(n−1)×n−2Pr−2=n(n−1)(n−2)×n−3Pr−3=⋯=n(n−1)⋯(n−(r−1))^nP_r=n\times{}^{n-1}P_{r-1}=n(n-1)\times{}^{n-2}P_{r-2}=n(n-1)(n-2)\times{}^{n-3}P_{r-3}=\cdots=n(n-1)\cdots(n-(r-1)) — recovering Theorem 4.1 as a chain of reductions.

Property 3. nPr=n−1Pr+r×n−1Pr−1^nP_r = {}^{n-1}P_r + r\times{}^{n-1}P_{r-1}.

Proof. Write both terms over the common denominator (n−r)!(n-r)!: …

Start your 14-day free trial to unlock the full solution →
← Previous · 4.4.1Permutations of distinct objectsNext · 4.4.3 →Objects always together (String method)