Counting permutations and combinations of objects
This section is dedicated to counting orderings, or permutations, of objects in a set, as well as subsets of specified cardinalities, or combinations, of elements of some wider set.
Definition – permutation
A permutation is a rearrangement of the elements of a set.
Example – permutations of a simple set
For the set {1, 2, 3}, the set of all permutations is {123, 132, 213, 231, 312, 321}, so there are six permutations of this set. Certainly, there is nothing special about elements 1, 2, and 3. Any set of three distinct elements would have the same number of permutations.
As you might suspect, however, listing permutations becomes more and more cumbersome for larger sets, so we need a rule for counting them more efficiently.
Theorem – permutations of a set
The number of permutations of a set of size n is n! = n(n – 1)(n – 2)…(2)(1), which is pronounced n factorial.
Proof...