alternative notation choices for \(\combination{n}{k}\)
choose function
the function \((n,k) \mapsto \combination{n}{k}\)
Checkpoint22.2.1.
What are the domain and codomain of the choose function?
Warning22.2.2.
Permutations and combinations are different. A permutation is a bijection from a set to itself. Given a fixed chosen ordering of the set elements in a list (considered as inputs), a permutation is essentially an re-ordering of the set elements into a second list, to line up outputs with inputs. So order matters in a permutation. On the other hand, a combination is just a set, and order does not matter in a set, only membership matters. That is, two listings of some of the elements from a set are the same combination if all the same elements are listed, regardless of the order of the elements in the two lists. So order does not matter in a combination.
Suppose \(\card{A} = n\text{.}\) Using the solution to Worked Example 22.1.1 as a model for our proof, we note that each ordered list of \(k\) elements taken from \(A\) defines a combination from \(A\text{,}\) but different orderings of the same \(k\) elements yield the same combination. Define two permutations to be “equivalent” if they are orderings of the same elements, so that equivalent permutations are associated to the same combination. Since there are \(k!\) elements in each equivalence class of permutations, we may apply the Division Rule to obtain
Finally, to obtain the rightmost formula in the statement of the theorem, we just need to combine the above formula relating \(\combination{n}{k}\) and \(\permutation{n}{k}\) with the formula for \(\permutation{n}{k}\) from Theorem 21.4.3.
Corollary22.2.4.
We also have \(\combination{n}{n-k} = \combination{n}{k}\text{.}\)
Interpret this last corollary as follows: from a set of \(n\) objects, choosing to include \(k\) elements in a combination is equivalent to choosing \(n-k\) objects to reject.
Worked Example22.2.6.Choosing ice cream.
How many double-scoop ice cream combinations are possible if the local ice cream shop features thirty-one different flavours? (Note: Only flavour combinations are relevant, not which flavour goes on the cone first.)
possibilities for double-scoop cones with two distinct flavours. However, there are an additional \(31\) possibilities for double-scoop cones with two scoops the same flavour. So the answer is
Worked Example22.2.7.Counting colour patterns (revisited).
How many different colour patterns can we achieve by placing three red bottles and five blue bottles on a shelf? (Assume the bottles are indistinguishable except by colour.)
There are \(8\) possible positions in which to place a bottle. To create an arbitrary colour pattern, we can choose \(3\) of the positions to be filled by red bottles, then place blue in the remaining positions. So the answer is
How many ways are there to choose a team of five people from a pool of six first-year students and four senior students if the team must have three first-years and two seniors?
Choose the seniors for team, then the first-years (or vice-versa). Applying the Multiplication Rule to these independent, consecutive tasks yields answer
Choose the first team (\(\combination{20}{4}\) ways), then the second team (\(\combination{16}{4}\) ways), then the third team (\(\combination{12}{4}\) ways). Applying the Multiplication Rule yields a total of
possible teams. However, the way in which we have constructed our teams has imposed an order on the collection of teams (first, second, and third team), when there is no reason to assume such structure. Given a collection of teams, re-ordering the teams themselves (not the people within each team) produces an equivalent collection of teams by membership. As there are \(3!\) ways to reorder the three teams, applying the Division Rule gives us a final answer of
Initially choose the twelve people who will make up the three teams, but without yet assigning anyone to a particular team (\(\combination{20}{12}\) ways). Then, from this reduced pool of candidates, choose the first team (\(\combination{12}{4}\) ways) and the second team (\(\combination{8}{4}\) ways). The third team will now consist of the remaining four people from the twelve initially chosen. The Multiplication Rule gives a preliminary total of
But as in the first solution above, we need to account for the fact that we have artificially ranked teams as first, second, and third. Applying the Division Rule gives us a final answer of