A raccoon is likely indifferent to the order in which it scavenges it’s dinner. Image derived and altered from wikimedia commons.

[This post is targeted at a Level 2 student. You should be familiar with Permutations II.]

A combination is a way of choosing elements from a set where order does not matter. Consider the following question: A high school physical education teacher has to decide on which two sports the students will be able to play in class today. There are 6 different sports that the school has the correct equipment for. How many choices for the two sports does the coach have?

Recall that in permutations, we said that if we wanted to arrange 2 items from 6 elements, there would be $\frac{6!}{4!}$ ways that we could do that. This doesn’t quite solve our problem, since the teacher sees no difference from choosing soccer first and then basketball, or choosing basketball first and then soccer. So each possible choice is counted twice, and we will have to divide our answer by 2. So the answer is actually $\frac{6!}{4!(2)}$.

We can generalize this idea using the following example: Lisa has 12 different ornaments in her closet. She wants to give five to her mom as a birthday gift. How many ways can she do this?

We can again think of giving Lisa’s mom a first ornament, a second ornament, a third ornament, etc. So we know that this would give $\frac{12!}{7!}$ choices. Lisa’s mom is receiving all five ornaments at once, so the order in which we decide on them does not matter. If we pick the bear first and then the frog second, it’s the same as if we picked the frog first and the bear second. How many ways could we have picked any set of 5 ornaments? There are $5!$ orderings of the chosen ornaments, so we could have picked a certain combination $5!$ different ways. Thus the total number of choices for Lisa 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, if we are picking $k$ elements from an $n$ element set and we do not care about the order, there are $\frac{n!}{k!(n-k)!}$ ways to do it. We represent this as a binomial coefficient, using the notation $n \choose k$.

### Worked Examples

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

Solution: From the concluding paragraph, the answer should be equal to ${13 \choose 3}$. Let’s work out how we can arrive at that answer. Let us first assume that the 3 chocolate chip cookies are distinct. We want a row of 13 cookies. There are $13 \times 12 \times 11$ different places that we could put them. However, as we realized earlier, the order of these chocolate chip cookies doesn’t actually matter. Hence, we have to divide out by $3 \times 2 \times 1$, to obtain $\frac {13 \times 12 \times 11}{3 \times 2 \times 1} = 286$.

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

Solution: This is slightly trickier to approach. It’s not immediately obvious what set we are choosing from. We’d use a technique called “Stars and Bars”, which was popularized by William Feller.We do so by creating a bijection between a solution $a + b + c + d = 10$ along with a sequence of 13 digits, of which 10 of them are 1′s, and 3 of them are 0′s. Given a set of 4 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 want to pick 3 places for the 1′s, and let the rest be 0′s. Hence, there are ${13 \choose 3}= 286$ ways.

For an extremely detailed explanation, you should refer to Solution to a Combinatorics Challenge.

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

The answers are the same not simply because we counted that there are 286 ways, but because there is a bijection between them. In the second question, we saw the bijection between such solutions $a+b+c+d=10$ and the sequences of length 13 consisting of 10 0′s and 3 1′s. In the first question, we can create a bijection between the arrangement of cookies and the sequences of 0′s and 1′s, by letting each raspberry cheesecake cookie be a 1, and each chocolate chip cookie be a 0. Hence, we do have a bijection between solutions to the above questions, which is why they have the same answer!

### Test Yourself

1. How many ways can three different appetizers be chosen from a menu that has 10 choices?

2. In New York city, all the streets are arranged in a grid. A hospital is located 5 blocks east and 6 blocks north of an accident. How many ways are there to get there, if we only go 1 block north or 1 block east at each intersection?

3. An office with 8 people wants to have 2 teams of 2 players to participate in a charity tournament. How many ways can the teams be made? Note: A player cannot be in multiple teams.

4. How many ordered integer solutions $(a, b, c, d)$ are there to $a + b + c + d = 20$ subject to $a \geq 1, b \geq 2, c \geq 3, d \geq 4$?

5. Winston must choose 4 courses for his final semester of school. He must take at least 1 science class and at least 1 arts class. If his school offers 4 science classes, 3 arts classes and 3 other classes, how many different choices for classes does he have?

The third should be 30C5 x 25C5 x 20C5 x 15C5. Four teams will be formed, with 5 players each. 10 people will be left over.

The fourth answer should be 13C3 which is 13x12x11/6 which is 286.

The first is 10C3 which is 120.

Am I right?

I agree with your methods for #1, #3. #4, I think, is a little more tricky because the restriction is more strict than just “positive”. (1, 1, 1, 17), for example, is not allowed but the 13C3 counts that.

• Rethink #3. As the hint says, “Be very careful”

For example, if the office had 3 people, and we wanted to form 3 teams of 1 person each, is there ${3 \choose 1} \times {2 \choose 1} \times {1 \choose 1}$ way? Or is there only 1?

I think 3rd should be (30C20)*(20C5)*(15C5)*(10C5)*(5C5).

2. for 1: 10C3 choices.

3. can someone tell how to solve test yourself #2 ?

I remember solving this in olympiad maths class,but I forgot the method

First should be 10c3

1. Ans: Since it is not mentioned that selection of specific appetizer is a choice therefore same can be selected thus no. of choices is (10)^3=1000.
2. Ans: Since one has to go 1 block forward in both east & north direction thus hospital can be reached in 5*6 i.e., 30 ways.
3. Ans. Since a choice that 1 play cannot contribute for both team thus actually it is a sum of combination type. As 2 players for each contained in 1 team & total 2 team has been formed thus actually 4 players need to be selected from 8 players. So total no of choices is 8C4 thus70 and for two team it is 70/2 i.e., 35.
5. Ans. It is also a combination type of problem.
a. 4C1*3C2*3C1=36
b. 4C1*3C3=12
c. 4C3*3C1=12
d. 4C1*3C1*3C2=36
e. 4C2*3C1*3C1=54
Therefore total no. of choices=(36*2+12*2+54)=150

• Please check all your work. I disagree with most of them. This is a post on Combinations, and most of these questions (especially the basic ones) would be using combinations.

For 1, note that it is stated “different appetizers”.

8. for #3 one team can be selected in 8c2 ways and 2nd team can be selected in 6c2 ways…so no of possibilities=8c2*6c2=420…am i right?

9. for #5 is the answer 12?