Definition D1
An arrangement is an ordered listing of r distinct elements chosen from a set X of n elements; the number of arrangements is nPr.
Proof.
(1)An arrangement is (a₁, …, a_r) with a_i ∈ X and a_i ≠ a_j for i ≠ j.convention
(2)Different positions give different arrangements. Order is part of the arrangement.convention
∎
Definition D2
A subset of X consisting of r elements is called a combination; their number is nCr.
Proof.
A subset has no positions. Only which elements it contains determines the subset.convention
∎
Definition D3
r! means the product from r down to 1: r(r−1)⋯2·1.
Proof.
r is a natural number at least 1, and r! is a natural number at least 1.convention, N
∎
Definition D4
a ÷ b means the x satisfying b × x = a.
Proof.
a ÷ b has a value only when such an x is unique.convention
∎
Lemma L1
Fixing one r-element subset A of X, the arrangements made only of the elements of A number exactly r!.
Proof.
(1)A has r elements, so r choices are possible for the first position.assumption, D2
(2)The terms of an arrangement are distinct, so once the first position is fixed, the second has the remaining r−1 choices.(1), D1
(3)In the same way, 1 choice remains for the last position.(2), D1
(4)Multiplying the counts of each stage gives r(r−1)⋯2·1(1), (2), (3), A1
(5)That value is r!.(4), D3
∎
Lemma L2
The set of all arrangements of length r is partitioned into pieces all of size r!, and the number of pieces is nCr.
Proof.
(1)To an arrangement p = (a₁, …, a_r) assign the set of its terms S(p) = {a₁, …, a_r}.convention, D1
(2)The terms are distinct, so |S(p)| = r, and S(p) is an r-element subset of X.(1), D1, D2
(3)Defining p ~ q as S(p) = S(q), this relation is reflexive, symmetric, and transitive.(1), E
(4)Hence the set of all arrangements is partitioned into the pieces of this relation.(3), A4
(5)Each piece is {p : S(p) = A} for some r-element subset A.(2), (4)
(6)That piece is the collection of arrangements made only of the elements of A, so its size is r!.(5), L1
(7)r! is at least 1, so for every r-element subset A the piece is nonempty.(6), D3, N
(8)If A ≠ A′, the two pieces are distinct, since the arrangements in one have term set A and in the other A′.(1), (5)
(9)Therefore A ↦ {p : S(p) = A} is a bijection from all r-element subsets to all pieces.(5), (7), (8)
(10)The number of pieces is the number of r-element subsets, nCr.(9), A3, D2
∎
Theorem T1
nPr = nCr × r!
Proof.
(1)The number of arrangements of length r is nPr.D1
(2)The set of those arrangements is partitioned into nCr pieces of size r!.L2
(3)nPr = nCr × r!(1), (2), A2
∎
Corollary C
nCr = nPr / r!
Proof.
(1)nPr = nCr × r!T1
(2)nCr × r! = r! × nCrA6
(3)nPr ÷ r! is the x satisfying r! × x = nPr.D4
(4)nCr is such an x.(1), (2), (3)
(5)r! is a natural number at least 1, so r! ≠ 0D3, N
(6)If r!x = r!y then x = y, so such an x is unique.(5), A5
(7)nCr = nPr / r!(4), (6), D4
(8)By the multiplication principle nPr = n(n−1)⋯(n−r+1), so nCr = n(n−1)⋯(n−r+1) / r!(7), D1, A1
∎