Counting for Fun, Basics – Part 6: Combinations and Multisets

A combination1234 is similar to a permutation, but order doesn’t matter.

The cardinality of r-combinations
An r-combination is an unordered selection of r elements from a set of n elements and has the notations C( n, r) or n\choose r. Repetition of elements from the selection are not allowed. This number is also known as the binomial coefficient and is stated as “n choose r”.
C( n, r ) = {n\choose r} = \frac{n!}{r!(n - r)!}

Example 1
Given the set of letters {a, b, c}, what is the 2 combination of the set?
This is “3 choose 2”, or C( 3, 2).
C(3, 2) = {3\choose 2} = \frac{3!}{2!(3 - 2)!} = \frac{3!}{2!\cdot1!} = \frac{3\cdot\cancel{2!}}{\cancel{2!}} = 3
Enumerated 2-combination as proof:
a, b
a, c
b, c

Example 2
How many ways are there to choose 3 players from a 10-member chess team to play at a regional tournament?
Order of the three players doesn’t matter here, so this is a combination problem.
C(10, 3) = {10\choose3} = \frac{10!}{3!(10 - 3)!} = \frac{10!}{3!\cdot7!} = \frac{10\cdot9\cdot8\cdot\cancel{7!}}{3!\cdot\cancel{7!}} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1} = \frac{720}{6} = 120
120 ways to select 3 players from a team of 10.

 

What if allowing repetition is needed? In this case the formula for counting the combinations slightly changes. These are r-combinations with repetition, otherwise known as multisets.

The cardinality of r-multisets
An r-multiset is computed as follows
{r + n - 1 \choose r}

 

Example 3
What is the cardinality of the 2-multiset from the set {1, 2, 3}?
{2 + 3 - 1\choose2} = {4\choose2} = \frac{4!}{2!(4 - 2)!} = \frac{4\cdot3\cdot\cancel{2!}}{\cancel2!\cdot2!} = \frac{12}{2\cdot1} = 6
Enumerated 2-multiset results for proof:
1, 1
1, 2
1, 3
2, 2
2, 3
3, 3

Example 4
How many ways are there to select 5 cans of soda from three flavors: orange, root beer, or cola, if there are at least five of each flavor to pick from? In this case r is equal to 5, the number of cans that need to be selected from n, which is equal to 3, the different kinds of soda we can select from.
{5 + 3 - 1\choose 5} = {7\choose 5} = \frac{7!}{5!(7 - 5)!} = \frac{7\cdot6\cdot\cancel{5!}}{\cancel{5!}\cdot2!} = \frac{42}{2\cdot1} = 21

 

 

1. Wikipedia contributors. (2022, February 24). Combination. In Wikipedia, The Free Encyclopedia. Retrieved from https://en.wikipedia.org/w/index.php?title=Combination&oldid=1073690135
2. Rosen, K. H. (1999). Discrete mathematics and its applications. (4th ed., pp.xxx). WCB/McGraw-Hill. ISBN 0-07-289905-0.
3. Epp, S. S. (2020). Discrete mathematics with applications.(5th ed., pp.xxx). Cengage. ISBN 978-1-337-69419-3.
4. Johnsonbaugh, R. (2018). Discrete mathematics. (8th ed., pp.xxx). Pearson. ISBN-13 978-0321964687.