Prolog
When I was introduced to permutations and combinations, I understood the basic formula for permutations, but I did not fully comprehend the formula for combinations. The explanation assumed too much insight on my part. While I did not fully appreciate the explanations, the calculated values always matched the physical reality that I could duplicate. I am going to demonstrate permutations and combinations at the most basic level, and I hope you will have a physical understanding of them. I will also share the basic formulas as well. At this writing, I only have a formal derivation in my head. I will commit it to writing later. My overall goal is to give you a better understanding of permutations and combinations than I had.
Basic Information
If some of the math symbols, terms and concepts are not familiar, then you may find an explanation at Math Definitions.
Defining a Permutation
Suppose you have a finite set of things. They could be numbers, colors, people, events, or anything else. For simplicity, consider the set of letters Α = {a,b,c}. The order of the items can be rearranged in a number of ways.
(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)
These sequences are in the set of permutations of Α, where the order of elements in each sequence distinguishes each permutation.
P(Α) = {(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}
Counting Permutations
One could simply derive all of the permutations and then count them, but there is a simple mathematical formula for determining the number of permutations. To derive the formula, use this simple procedure for deriving permutations for a set containing N distinct elements. First choose an element and place it on the one of N cells. Then choose the second element and place it on of the remaining N-1 cells. Continue this process until all of the elements are in a cell. Finally, continue the process over and over again until all possible combinations are chosen. The resulting formula is:
|P(Α)| = N-factorial or N!, where |Α| = N
The formula shows how many elements there are in the permutation file, given that the base file contains N distinct elements. But the formula doesn’t provide a way to construct the permutation file.
Constructing Permutations
One way to construct a file of permutations is to start with an empty file, and repeatedly introduce a distinct element from the base file, one at a time and create permutation files of subsets, one at a time until all of the elements have been added. The problem: How is the new element added?
For illustration purposes, suppose we have progressed to the following permutation level:
Α3 ∈ Α, where Α3 = {a,b,c}.
P(Α3) = {(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}
Adding the next distinct character, say element ‘d’, would be added to each element in the set of permutations to create more than one new permutation as follows.
Select a permutation, starting with the first.
Create new permutations by adding the new element ‘d’ to the beginning of the permutation, yielding (d,a,b,c)
Then create successive permutations by adding the new element ‘d’ after each successive element in the original permutation, yielding (a,d,b,c) …
Adding ‘d’ to (a,b,c) would result in the following new permutations replacing the original.
(d,a,b,c),(a,d,b,c),(a,b,d,c),(a,b,c,d)
This process would create a new set of permutations containing a permutation with the new element at the beginning, and a new permutation with the new element inserted after each of the N elements in each old permutation sequence for a total of N+1 elements. Assuming that old set is a complete set, then the new set’s cardinality should be:
|P(ΑN+!)| = (N+1) ⋅ |P(ΑN)| = (N+1)!
Proof by Math Induction
We must prove that the set of permutations is complete with no duplicate sequences. A proof by induction will suffice. The first part of an induction proof is to show that the first case is true. Permutations start with the null set.
∅ = {}, a set with no elements.
P(@empty;) = {()}, a set with 1 element consisting of an empty permutation. the state of nothing occurs only once.
|P(@empty;)| = 1 = 0!
Construct the permutation of {a} by applying using P(∅) as the base set.
P(∅) = {()}, a set with only one member, ().
create permutations by adding the element a to the empty permutation, ().
First, add the element a to the beginning of () creating (a).
Since there are no elements in the sequence (), the set is complete with one element.
P({a}) = {(a)}
|P({a})| = 1 = 1!
With only 1 member on P({a}), all members are distinct by definition.
The second step is to prove that the transition from a base permutation to the next level by adding a new, distinct member using the method shown above will yield a set with the appropriate number of unique permutations. The number of permutations is shown in the example above to be the correct factorial amount. It is given that the bas permutation set contains a set of distinct sequences with no duplications.
By adding a new distinct member to the base set and inserting the member in different locations in a base sequence, the insertion of the new element to a single base sequence generates unique sequences, because the new element is added in a different location for each new permutation.
Each new permutation where the new element is in the same location is generated from a different base sequnce, and each are distinct, Therefore the base elements generated from different base elements are distinct.
So the newe set of permutations has ditinct members, and the cardinality is the correct factorial.
Homework
Using P({a}) as the starting point, generate the following permutation sets using the method shown abov e and verify that you have correct answers.
P({a,b}) = {{b,a),(a,b)}
P({a,b,c}) = {(c,b,a),(b,c,a),(b,a,c),(c,a,b),(a,c,b),(a,b,c)}
P({a,b,c,d}) = (d,c,b,a),(c,d,b,a),(c,b,d,a),(c,b,a,d),(d,b,c,a),(b,d,c,a),(b,c,d,a),(b,c,a,d),(d,b,a,c),(b,d,a,c),(b,a,d,c),(b,a,c,d),
(d,c,a,b),(c,d,a,b),(c,a,d,b),(c,a,b,d),(d,a,c,b),(a,d,c,b),(a,c,d,b),(a,c,b,d),(d,a,b,c),(a,d,b,c),(a,b,d,c),(a,b,c,d)
Does the cardinality of the permutation sets agree with the expected result?
What is the value of P({a,b,c,d,e})?
Click for Next Math Page: Combinations