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!

## Comments

There are no comments in this discussion.