Combinations

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 \(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.

Proof of \(\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}:\)

Now suppose we want to choose \(k\) objects from \(n\) objects, then the number of combinations of \(k\) objects chosen from \(n\) objects is denoted by \(n \choose k\). Since \({_nP_k}=k!{n \choose k}\), it follows that

\[{n \choose k} = \frac{1}{k!}(_nP_k)= \frac{n!}{k!(n-k)!}.\]

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 \({13\choose3}=\frac{13\times12\times11}{3\times2\times1}=286.\) \(_\square\)

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 \({7\choose3}\times{4\choose2} = 210.\) Therefore, the number of groups each containing 3 consonants and 2 vowels is \(210.\) Since each group contains 5 letters, which can be arranged amongst themselves in \(5!= 120\) ways, the required number of words is \(210\times120 = 25200.\ _\square\)

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 \(3\) males out of \(7\) is \({7 \choose 3} = \frac{7\times 6\times 5}{3 \times 2 \times 1}=35.\) Similarly, the number of ways to select \(2\) females out of \(5\) is \({5 \choose 2} = \frac{5\times 4}{2 \times 1}=10.\) Hence, by the rule of product, the answer is \(35 \times 10=350\) ways. \(_\square\)

There are \(9\) children. How many ways are there to group these \(9\) children into 2, 3, and 4?

---

The number of ways to choose \(2\) children out of \(9\) is \({9\choose2}=\frac{9 \times 8}{2 \times 1}=36.\) The number of ways to choose \(3\) children out of \(9-2=7\) is \({7 \choose 3}=\frac{7 \times 6 \times 5}{3 \times 2 \times 1}=35.\) Finally, the number of ways to choose \(4\) children out of \(7-3=4\) is \({4 \choose 4}=1.\) Hence, by the rule of product, the answer is \(36 \times 35 \times 1=1260\) ways. \(_\square\)

There are \(9\) distinct chairs. How many ways are there to group these chairs into 3 groups of 3?

---

The number of ways to choose \(3\) chairs out of \(9\) is \({9\choose3}=\frac{9 \times 8 \times 7}{3 \times 2 \times 1}=84.\) The number of ways to choose \(3\) chairs out of \(9-3=6\) is \({6 \choose 3}=\frac{6 \times 5 \times 4}{3 \times 2 \times 1}=20.\) Finally, the number of ways to choose \(3\) chairs out of \(6-3=3\) is \({3 \choose 3}=1.\) 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 \[\frac{84 \times 20 \times 1}{3 !}=280\] ways. \(_\square\)

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 \( k \) unordered elements from an \( n \) element set is \( \frac{n!}{k!(n-k)!} \). This is a binomial coefficient, denoted \( n \choose k \).

How many ordered non-negative integer solutions \( (a, b, c, d) \) are there to the equation \( a + b + c + d = 10 \)?

---

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, and 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, 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 \( {13 \choose 3}= 286 \) such sequences. \(_\square\)

There are \(5\) shirts all of different colors, \(4\) pairs of pants all of different colors, and \(2\) 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 \(2\) shirts out of \(5\) for both Amy and Bunny to wear, so \({5\choose2}2!=20.\)
We choose \(2\) pairs of pants out of \(4\) for them to wear, so \({4\choose2}2!=12.\)
We choose \(2\) pairs of shoes out of \(2\) for them to wear, so \({2\choose2}2!=2.\)

Therefore, by the rule of product, the answer is \(20 \times 12 \times 2=480\) ways. \(_\square\)

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 \(5+5=10\) countries into 5 groups of 2 each is as follows:

\[\frac{{10\choose2} \times {8\choose2} \times {6\choose2} \times {4\choose2} \times {2\choose2}}{5 !} =\frac{ 45 \times 28 \times 15 \times 6 \times 1}{120}=945. \qquad (1)\]

Since it is required that at least one group must have only European countries, we need to subtract from \((1)\) 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:

\[5 ! = 5 \times 4 \times 3 \times 2 \times 1=120. \qquad (2)\]

Therefore, taking \((1)-(2)\) gives our answer \(945-120=825.\) \(_\square\)

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 \(r, y\) and \(b\) 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 \(r+y+b=15,\) and then subtract the numbers of cases where \(r>10, y>10\) or \(b>10.\)

Using stars and bars, the number of cases satisfying \(r+y+b=15\) is \({17\choose2}=136. \qquad (1)\)

Now, the following gives the number of cases where \(10<r\le15:\)

• If \(r=11,\) then \(y+b=4,\) implying there are 5 such cases.
• If \(r=12,\) then \(y+b=3,\) implying there are 4 such cases.
• If \(r=13,\) then \(y+b=2,\) implying there are 3 such cases.
• If \(r=14,\) then \(y+b=1,\) implying there are 2 such cases.
• If \(r=15,\) then \(y+b=0,\) implying there is 1 such case.

Hence, the number cases where \(10<r\le15\) is \(5+4+3+2+1=15.\) Since exactly the same logic applies for the cases where \(10<y\le15\) or \(10<b\le15,\) the total number of cases to subtract from \((1)\) is \(3\times 15=45. \qquad (2)\)

Therefore, taking \((1)-(2)\) gives our answer \(136-45=91.\) \(_\square\)

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 \(X\) be the number of all the possible sale strategies during a calendar week. What is the remainder of \(X\) upon division by 1000?

---

Let \(a, b, c, d, e, f, g\) 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 \(3\times 7=21\) 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 \(a\) on sale is \({7\choose 3}.\) Then the number of ways to put each of the remaining 6 kinds on sale in those 3 days is \({6\choose 2}\times {4\choose 2}\times {2\choose 2} .\) The following table is one example of this operation, where \(a\) is on sale for all 3 days during the week, whereas each of the other 6 kinds is on sale only once:

pizza

Since we are done with \(a,\) we now put one \(b\) in each of 2 of the remaining 4 days, the number of ways of doing which is \({4 \choose 2}.\) Then, excluding \(c\) which was already on sale together with \(b\) on the first day, we put \(d, e, f, g\) in the 2 days where \(b\) was just put. However, since the combinations \((d, e)\) and \((f, g)\) were already used when dealing with \(a,\) the number of ways to put \(d, e, f, g\) in the two columns together with \(b\) is \({4 \choose 2}-2.\)

Finally, we put one \(c\) 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 \[{7\choose 3}\times {6\choose 2}\times {4\choose 2}\times {4\choose 2}\times\left({4 \choose 2}-2\right)\times 2=151200.\]

Therefore, the remainder of \(151200\) upon division by 1000 is 200. \(_\square\)

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 \(k=3\) indistinguishable balls into \(n=4\) labeled urns, which is known as balls and urns or stars and bars. Thus, our answer is \[\binom{n+k-1}{k} =\binom{n+k-1}{n-1}=\binom{3+4-1}{3}=20. \ _\square \]

Let \(x+y+z=m,\) where \(x, y, z\) are integers such that \(x\ge 1, y\ge 2, z\ge 3.\) If the number of ordered triples \((x, y, z)\) satisfying the equation is \(21,\) what is \(m?\)

---

Let \(x-1=a, y-2=b, z-3=c,\) where \(a, b, c\) are non-negative because \(x\ge 1, y\ge 2, z\ge 3,\) then

\[\begin{align} x+y+z&=m\\ (a+1)+(b+2)+(c+3)&=m\\ a+b+c&=m-6. \qquad (1) \end{align}\]

Since the number of ordered non-negative integer triples \((a, b, c)\) satisfying \((1)\) is \(21,\) using the technique of stars and bars, we obtain

\[\begin{align} \binom{3+(m-6)-1}{m-6} =\binom{m-4}{m-6}=\binom{m-4}{2}&=21\\ \frac{(m-4)(m-5)}{2!}&=21\\ m^2-9m+20&=42\\ m^2-9m-22&=0\\ (m+2)(m-11)&=0\\ m&=11 \end{align}\]

because \(m>0.\ _\square\)