In Mathematics we use the following definition:
· If the order does matter it is a Permutation.
· If the order doesn't matter, it is a Combination.
Here is an example of permutation: suppose you buy a combination lock for your locker. The combination for your lock is set at “647”. Obviously, the order of the combination matters. "647" works, but “476” will not work, nor will “764”.
Here is an example of combination: suppose you prepare your salad with apple, banana, and grapes. The salad will be identical whether you prepare it with apple, banana, grapes, or banana, apple, grapes, or grapes, banana, apple.
In Math terms, permutation is ordered combination; combination is un-ordered combination.
Permutation Formula
We define p (n, m) as the number of ways to choose m out of n number of things (no repetition, order matters).
For example, choose 3 numbers out of 10 numbers 0,1,2,3,4,5,6,7,8,9 to form the combination of your combination lock.
Suppose 0! = 1, 1! = 1, 2! = 2 × 1, 3! = 3 × 2 × 1, … etc., (The factorial function); then we have:
1. No-repetition, ordered: P (n, m) = n (n-1) (n-2) …… (n – m + 1) = n! / (n - m)!
For example, if our combination lock does not allow 3 digits to be the same, then our combination lock has P (10, 3) = 10! / (10 - 3)! = 720 (non-repetitive, ordered) combinations.
What if repetition is allowed in the permutation? For example, when our combination lock allows the 3 digits to be the same, how many ways can our (ordered) combination be set? This is easy, it will be:
10 × 10 × 10 = 1,000
Or to use a more generic formula:
2. Repetition, ordered: n × n × ... (r times) = nr
Combination Formula
When you choose m out of n things to form an un-ordered combination, and if repetition is NOT allowed, your ways of combination will be:
3. No-repetition, un-ordered: C (n, m) = p (n, m) / m! = n! / ((n-m)! × m!), or C (n, m) = C (n, n - m)
In our above combination lock example, suppose we are only interested in knowing how many 3 digit combination can be chosen from 0 to 9 to form our combination lock without having to consider which number is chosen first. In this case, 4,7,6 would be the same combination as 7,4,6, but not the same combination as 5,7,6.
In our counting of the total un-ordered combination, we will only need to REDUCE the total ordered combination (or permutation). We know for example, the ordered combinations of:
4,7,6
4,6,7
7,4,6
7,6,4
6,4,7
6,7,4
Can be reduced, by a factor of 3! = 6, to only 1 un-ordered combination of 4,7,6.
C (10, 3) = P (10, 3) / 3! = 720 / 6 = 120