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

Note by Arron Kau
6 years, 2 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$