A combination is a way of choosing elements from a set in which order does not matter. A wide variety of counting problems can be cast in terms of the simple concept of combinations, therefore, this topic serves as a building block in solving a wide range of problems.
Consider the following example: Lisa has different ornaments and she wants to give 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 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 reorderings of the chosen ornaments, implying the total number of ways for Lisa to give her mom an unordered set of ornaments is .
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 unordered elements from an element set is . This is a binomial coefficient.
Now suppose we want to choose objects from objects, then the number of combinations of objects chosen from objects is denoted by . Since , it follows that
How many ways are there to arrange 3 chocolate chip cookies and 10 raspberry cheesecake cookies into a row of 13 cookies?
We can consider the situation as having 13 spots and filling them with 3 chocolate chip cookies and 10 raspberry cheesecake cookies. Then we just choose 3 spots for the chocolate chip cookies and let the other 10 spots have raspberry cheesecake cookies. The number of ways to do this job is
Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?
The number of ways of selecting 3 consonants out of 7 and 2 vowels out of 4 is Therefore, the number of groups each containing 3 consonants and 2 vowels is Since each group contains 5 letters, which can be arranged amongst themselves in ways, the required number of words is
How many ways are there to select 3 males and 2 females out of 7 males and 5 females?
The number of ways to select males out of is Similarly, the number of ways to select females out of is Hence, by the rule of product, the answer is ways.
There are children. How many ways are there to group these children into 2, 3, and 4?
The number of ways to choose children out of is The number of ways to choose children out of is Finally, the number of ways to choose children out of is Hence, by the rule of product, the answer is ways.
There are distinct chairs. How many ways are there to group these chairs into 3 groups of 3?
The number of ways to choose chairs out of is The number of ways to choose chairs out of is Finally, the number of ways to choose chairs out of is Now, since each of these three groups has an equal number of three chairs and the order of the three groups does not matter, by the rule of product our answer is ways.
A combination is a way of choosing elements from a set in which order does not matter.
In general, the number of ways to pick unordered elements from an element set is . This is a binomial coefficient, denoted .
How many ordered non-negative integer solutions are there to the equation ?
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 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 1's, then has a 0, then has 1's, then has a 0, then has 1's, then has a 0, and then has 1's. Conversely, given such a sequence, we can set to be equal to the length of the initial string of 1's (before the first 0), set equal to the length of the next string of 1's (between the first and second 0), set equal to the length of the third string of 1's (between the second and third 0), and set equal to the length of the fourth string of 1's. It is clear that such a procedure returns the starting set, and hence we have a bijection. Now, it remains to count the number of such sequences. We pick 3 positions for the 0's and the remaining positions are 1's. Hence, there are such sequences.
There are shirts all of different colors, pairs of pants all of different colors, and pairs of shoes with different colors. In how many ways can Amy and Bunny be dressed up with a shirt, a pair of pants, and a pair of shoes each?
We choose shirts out of for both Amy and Bunny to wear, so
We choose pairs of pants out of for them to wear, so
We choose pairs of shoes out of for them to wear, so
Therefore, by the rule of product, the answer is ways.
We are trying to divide 5 European countries and 5 African countries into 5 groups of 2 each. How many ways are there to do this under the restriction that at least one group must have only European countries?
The number of ways to divide countries into 5 groups of 2 each is as follows:
Since it is required that at least one group must have only European countries, we need to subtract from the number of possible groupings where all 5 groups have 1 European country and 1 African country each. This is equivalent to the number of ways to match each of the 5 European countries with one African country:
Therefore, taking gives our answer
There are two distinct boxes, 10 identical red balls, 10 identical yellow balls, and 10 identical blue balls. How many ways are there to sort the 30 balls into the two boxes so that each box has 15?
Keeping in mind that the two boxes are distinct, let and be the numbers of red, yellow and blue balls in the first box, respectively. Then we first need to get the number of cases satisfying and then subtract the numbers of cases where or
Using stars and bars, the number of cases satisfying is
Now, the following gives the number of cases where
- If then implying there are 5 such cases.
- If then implying there are 4 such cases.
- If then implying there are 3 such cases.
- If then implying there are 2 such cases.
- If then implying there is 1 such case.
Hence, the number cases where is Since exactly the same logic applies for the cases where or the total number of cases to subtract from is
Therefore, taking gives our answer
PizzaHot makes 7 kinds of pizza, 3 of which are on sale everyday, 7 days a week. According to their policy, any two kinds of pizza that are on sale on a same day can never be on sale on the same day again during the rest of that calender week. Let be the number of all the possible sale strategies during a calendar week. What is the remainder of upon division by 1000?
Let be the 7 kinds of pizza. Then none of these 7 could be on sale for 4 days or more a week because each of the other 6 kinds would have been on sale on a same day in the first 3 days. In fact, since there are pizzas on sale every week, each of the 7 kinds is on sale exactly 3 times a week.
Now, without loss of generality, the number of ways to select 3 days to put on sale is Then the number of ways to put each of the remaining 6 kinds on sale in those 3 days is The following table is one example of this operation, where is on sale for all 3 days during the week, whereas each of the other 6 kinds is on sale only once:
Since we are done with we now put one in each of 2 of the remaining 4 days, the number of ways of doing which is Then, excluding which was already on sale together with on the first day, we put in the 2 days where was just put. However, since the combinations and were already used when dealing with the number of ways to put in the two columns together with is
Finally, we put one in each of the remaining two columns and then fill the columns, the number of ways of doing which is 2. Hence, the number of all the possible sale strategies during a calendar week is
Therefore, the remainder of upon division by 1000 is 200.
Main Article: Combinations with Repetition
You want to distribute 7 indistinguishable candies to 4 kids. If every kid must receive at least one candy, in how many ways can you do this?
You first give one candy to each of the 4 kids to comply with the requirement that every kid must receive at least one candy. Then you are left with 3 candies to distribute to the 4 kids, which is equivalent to a problem of placing indistinguishable balls into labeled urns, which is known as balls and urns or stars and bars. Thus, our answer is
Winston must choose 4 classes 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 (distinct) science classes, 3 (distinct) arts classes and 3 other (distinct) classes, how many different choices for classes does he have?
Details and Assumptions:
- He cannot take the same class twice.
Let where are integers such that If the number of ordered triples satisfying the equation is what is
Let where are non-negative because then
Since the number of ordered non-negative integer triples satisfying is using the technique of stars and bars, we obtain
A pawn is placed on the lower left corner square of a standard by chess board. A 'move' involves moving the pawn, where possible, either
- one square to the right,
- one square up, or
- diagonally (one square up and to the right).
Using these legitimate moves, the pawn is to be moved along a path from the lower left square to the upper right square.
How many such paths are there?