Combinations

A combination is a way of choosing elements from a set in which order does not matter.

Consider the following example: Lisa has $12$ different ornaments and she wants to give $5$ ornaments to her mom as a birthday gift (the order of the gifts does not matter). How many ways can she do this?

We can think of Lisa giving her mom a first ornament, a second ornament, a third ornament, etc. This can be done in $\frac{12!}{7!}$ ways. However, Lisa’s mom is receiving all five ornaments at once, so the order Lisa decides on the ornaments does not matter. There are $5!$ reorderings of the chosen ornaments, implying the total number of ways for Lisa to give her mom an unordered set of $5$ ornaments is $\frac{12!}{7!5!}$.

Notice that in the answer, the factorials in the denominator sum to the value in the numerator. This is not a coincidence. In general, the number of ways to pick $k$ unordered elements from an $n$ element set is $\frac{n!}{k!(n-k)!}$. This is a binomial coefficient, denoted $n \choose k$.

Worked Examples

1. How many ways are there to arrange 3 chocolate chip cookies and 10 raspberry cheesecake cookies into a row of 13 cookies?

Solution: There are $13 \times 12 \times 11$ ways to chose 3 distinct chocolate chip cookies. However, the order of these chocolate chip cookies doesn't matter. Hence, we divide by $3 \times 2 \times 1$, to obtain $\frac {13 \times 12 \times 11}{3 \times 2 \times 1} = 286$ ways.

2. How many ordered non-negative integer solutions $(a, b, c, d)$ are there to the equation $a + b + c + d = 10$?

Solution: To solve this problem, we use a technique called "Stars and Bars", which was popularized by William Feller. We create a bijection between the solutions to $a + b + c + d = 10$ and sequences of 13 digits, consisting of ten 1's, and three 0's. Given a set of four integers whose sum is 10, we create a sequence that starts with $a$ 1's, then has a 0, then has $b$ 1's, then has a 0, then has $c$ 1's, then has a 0, then has $d$ 1's. Conversely, given such a sequence, we can set $a$ to be equal to the length of the initial string of 1's (before the first 0), set $b$ equal to the length of the next string of 1's (between the first and second 0), set $c$ equal to the length of the third string of 1's (between the second and third 0) and set $d$ equal to the length of the fourth string of 1's. It is clear that such a procedure returns the starting set, hence we have a bijection .Now, it remains to count the number of such sequences. We pick 3 positions for the 1's and the remaining positions are 0's. Hence, there are ${13 \choose 3}= 286$ such sequences.

3. Both of the previous answers are 286. Is this a happy coincidence?

In the second question, we gave a bijection between solutions to $a+b+c+d=10$ and sequences of length 13 with 10 0's and 3 1's. For the first question, we can also create a bijection between the arrangement of cookies and the sequences of length 13 with 10 0's and 3 1's, by letting each raspberry cheesecake cookie be a 1, and each chocolate chip cookie be a 0. Therefore, we have a bijection between solutions to the first and second questions, which explains why they have the same answer!