Permutations are for lists, order matters.
Better Explained
Combinations are for groups, order does not matter.
Permutations
A Permutation is an ordering of elements from a group of objects.
Permutations of a set
Say we have n elements and we want to arrange all of them with a specific order.
To count the number of possible arrangements we use the formula:
![\[n! = n \cdot (n-1) \cdot (n-2) \cdot … \cdot 1\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-7175f6af9b1320f3c3959fca7368c64f_l3.png "Rendered by QuickLaTeX.com")
Permutations of a Subset
Say we want to order a subset of items picked from a super-set.
To count how many ways we can Pick k elements from a group of n and arrange in a particular order, we use the P(n,k) formula.
![\[P(n, k) = \frac{n!}{(n-k)!}\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-0ab6020c6cfaa07767f2b6644d717551_l3.png "Rendered by QuickLaTeX.com")
When we want to order all the elements of a set, the P(n,n) formula reduces to:
![\[P(n, n) = \frac{n!}{(n-n)!} = n!\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-8e9850d01ee49b15e7f45c9275e5a3c0_l3.png "Rendered by QuickLaTeX.com")
Combinations
A Combination is an unordered choice of elements from a bigger set.
The C(n,k) formula tells us how many ways you can Choose k elements from a group of n, where the order is not relevant:
![\[C(n, k) = {n \choose k}= \frac{n!}{k!(n-k)!}\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-fee006abd86a12fb7e226938933f1f87_l3.png "Rendered by QuickLaTeX.com")
P(n,k) vs C(n,k)
The P(n,k) and C(n,k) formulas differ for a factor n!.
![\[P(n,k) = C(n, k) \cdot k!\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-c9879380d0d4c35b14fdcf3d5dae19f5_l3.png "Rendered by QuickLaTeX.com")
Proof: Indeed, once you have chosen a set of k elements, you get the number of permutations by multiplying by k!
![\[\begin{aligned} P(n,k) & = C(n, k) \cdot k! \\ & = {n \choose k} \cdot k! \\ & = \frac{n!}{ \cancel{k!} \cdot (n-k)!} \cdot \cancel{k!} \\ & = \frac{n!}{(n-k)!} \end{aligned}\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-e6c6ac401faf35f397188b12573ea6f7_l3.png "Rendered by QuickLaTeX.com")
Exercises
Here are a few exercises about permutations and combinations
Ex1 – Permutations of a set
In how many ways we can arrange five cards A, B, C, D, and E?
Hence, the total number of ways to arrange the cards is
![\[5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-a9aa3e9b8547395e7641b00a31df1084_l3.png "Rendered by QuickLaTeX.com")
Indeed, as 1st card, we can pick one out of five, as 2nd we pick one out of four, .. and so on until we get the last card for which we have no choice.
Ex 2 – Permutations of a subset
In how many ways we can sort the first 2 books in a shelf with 8 books?
Let’s use the formula:
![\[{7 \choose 3}= \frac{7!}{3! \cdot 4!}= \frac{7\cdot\cancel{6} \cdot 5 \cdot \cancel{4 \cdot 3 \cdot 2}}{(\cancel{3 \cdot 2}) \cdot (\cancel{4 \cdot 3 \cdot 2})!} = 35\]](https://asciiware.com/wp-content/ql-cache/quicklatex.com-b4d380fd084b5720a23bea30cb849d59_l3.png "Rendered by QuickLaTeX.com")
Indeed, to choose the 1st book, we can pick one out of eight, and as 2nd we pick one out of seven.
Ex 2 – Combinations of a subset
How many sets of 3 different book can you borrow from a library containing 7 books?
References
- How to use permutations and combinations, Mario’s Math Tutoring, Youtube
- Easy Permutations and Combinations, Better Explained
- Combinations, brilliant
- Combination formula, Khan Academy
0 Comments