×

# 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
3 years, 6 months ago

## Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...