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$.

## 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!

No vote yet

1 vote

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

There are no comments in this discussion.