Combinatorics
It is useful to be able to find the number of combinations and permutations of sets.
Watch the video and then answer the questions below.
Fifteen-minute video
You can also view this video on YouTube
Key Points
Enumeration
To enumerate is to list of all the elements of a set. The extensional definition of a set it an enumeration of that set. I can enumerate all numbers in the set \(\{ x : x < 5 \} \) as follows:
1, 2, 3, 4
Simple!
Combination
A combination is a way of picking \( k \) elements out of a set of \( n \) elements.
If we had a set of 4 elements \( \{ a, b, c, d \} \) and picked 3, there would be 4 combinations we could pick:
abc acd abd bcd
\[ ^nC_k = \frac{n!}{k!(n-k)!} \]
Read \( ^nC_k \) as “n choose k”.
Where \( n \) is the size of the set and \( k \) is the size of the subset we are picking. Here \( ^4C_3 = \frac{4!}{3!(4-3)!} = \frac{4 \times 3 \times 2 \times 1}{3!1!} = \frac{24}{6} = 4 \)
This is also known as the binomial coefficient and can be written:
\( {n}\choose{k} \)
Permutation
The order of elements in a set is a permutation. If we had the a set of coloured balls \( \{ R, G, B \} \), there would be 6 different ways to order them:
RGB RBG
BGR BRG
GBR GRB
\[ ^nP_k = \frac{n!}{(n-k)!} \]
Where \( n \) is the size of the set and \( k \) is the size of the subset we are ordering. Here \( ^3P_3 = \frac{3!}{(3-3)!} = \frac{3 \times 2 \times 1}{0!} = \frac{6}{1} = 6 \)
Calculating Factorial in Java
Factorial can be shown mathematically using a piecewise function:
\[ n! = \begin{cases} 0 & n = 0 \\ (n-1)! & n \gt 0 \end{cases} \]
This lends itself to a recursive definition in Java (one that calls itself):
Questions
1. Check your understanding
1. Factorials
By hand, solve the following factorials.
2. Combinations
By hand, work out the answers to the following combinations. You can use the formula given above to help you.
3. Permutations
By hand, work out the answers to the following permutations. You can use the formula given above to help you.
2. Maths to Code Practice
Write a function int permutation(int n, int k) to calculate the permutation \(^nP_k\) for values of \( n \) and \( k \). It will need to implement the following equation:
\[ ^nP_k = \frac{n!}{(n-k)!} \]
You can make use of the recursive factorial function given above.
3. Question Generator
Summary
In this section we have learned about combinatorics.
- You should know how factorial is calculated.
- You should understand what a combination is.
- You should understand what a permutation is.
- You should be able to use their formulas to calculate these.
In the next section we will look at probability trees.