Combinations: The Binomial Theorem
The standard deck of playing cards consists of 52 cards comprising of four suits: clubs C, diamonds D, hearts H, and spades S. Each suit has 13 cards: ace A, 2, 3, ..., 10, jack J, queen Q, and king K.
If three cards were drawn from a standard deck, in succession and without replacement, then by the rule of product, there are 52 x 51 x 50 = P(52,3) card possibilities, such as AH (ace of hearts), 9C (nine of clubs), and KD (king of diamonds).
If three cards were instead drawn from a standard deck at one time, where the order of the selection of the cards is no longer important, then there are six permutations (AH-9C-KD, AH-KD-9C, 9C-AH-KD, 9C-KD-AH, KD-9C-AH, KD-AH-9C) that correspond to just one, unordered selection of three cards. Each selection, or combination, of three cards, with no reference to order, corresponds to 3! permutations of the three cards, where the following demonstrates this in equation form:
3! x (number of card selections of size 3 from a deck of 52 cards) = (number of card arrangements of size 3 from a deck of 52 cards) = P(52,3) = 52!/49!
Therefore, three cards can be drawn without replacement from a standard deck in 52!/(3!49!) ways.
In general, if there are n distinct objects, then each selection, or combination, of amount r of these objects, with no reference to order, corresponds to r! permutations/arrangements of size r from the n objects. Therefore, the number of combinations of size r from a collection of n objects is the following:
where C(n,r) is read as, "n choose r."
For all n ≥ 0, C(n,0) = C(n,n) = 1.
For all n ≥ 1, C(n,1) = C(n,n-1) = n.
For all n ≥ 0, n < r, C(n,r) = 0.
When dealing with any counting problems and order is relevant, then permutations, arrangements, and the rule of product are used. When order is not relevant, then combinations are used.
Example
A hostess is having a dinner party for some members of her charity committee. Because of the size of her home, she can invite only 11 of the 20 committee members. Order is not important, so she can invite "the lucky 11" in C(20,11) = 20!/(11!9!) ways.
Example
Lynn and Patti decide to buy a PowerBall ticket. To win the grand prize for PowerBall, one must match five numbers selected from 1 to 49 inclusive and then must also match the powerball, which is an integer from 1 to 41 inclusive. Lynn selects the five numbers (between 1 and 49 inclusive). She can do this in C(49,5) ways, because matching does not involve order. Meanwhile, Patti selects the powerball, where there are C(42,1) ways to select it. By the rule of product, Lynn and Patti can select the six numbers for their PowerBall ticket in C(49,5) x C(42,1) = 80,089,128 ways.
Example
At Rydell High School, the gym teacher must select nine girls from the junior and senior classes for a volleyball team. If there are 28 juniors and 25 seniors, she can make the selection in C(28 + 25,9) = C(53,9) ways.
If two juniors and one senior are the best spikers and must be on the team, then the rest of the team can be chosen in C(53 - 3, 9 - 3) = C(50,6) ways.
For a certain tournament, the team must comprise four juniors and five seniors. The teacher can select the four juniors in C(28,4) ways. For each of these selections, she has C(25,5) ways to choose the five seniors. By the rule of product, she can select her team in C(28,4) x C(25,5) ways for this particular tournament.
Sometimes problems can use the method of combinations or permutations.
Example
At Rydell High School, the gym teacher must make up four volleyball teams of nine girls each from the 36 freshman girls in her P.E. class. In how many ways can she select these four teams? Let the teams be called A, B, C, and D.
To form team A, she can select any nine girls from the 36 enrolled in C(36,9) ways. Since 9 girls are already in one team, there are 36 - 9 = 27 girls left to be selected. To form team B, she can select any nine girls from the 27 remaining in C(27,9) ways. Similarly, to form team C, she can select nine girls from the 27 - 9 = 18 girls remaining in C(18,9) ways and form team D by selecting nine girls from the nine remaining in C(9,9) ways. By the rule of product, the four teams can be chosen in C(36,9) x C(27,9) x C(18,9) x C(9,9) ways.
Using permutations, consider that the 36 students are lined up:
Each of the four teams A, B, C, and D need nine members each. Nine A's, nine B's, nine C's, and nine D's. The number of arrangements for these 36 letters is 36!(9!9!9!9!) ways, which is equal to C(36,9) x C(27,9) x C(18,9) x C(9,9).
Sometimes problems require the use of combinations and permutations/arrangements.
Example
The number of arrangements of the letters in TALLAHASSEE is 11!/(1!3!2!1!2!2!).
The number of arrangements of the letters in TALLAHASSEE with no adjacent A's can be found by first calculating the number of arrangements of the letters in TALLAHASSEE without the A's, TLLHSSEE, which is 8!/(1!2!1!2!2!) = 5040 ways. Notice that there are nine remaining spaces between each letter, including the beginning and end of the letters. Those are the nine possible locations for the three A's. Since there's only three A's to be filled, there are a total of C(9,3) = 84 ways to select the three locations for the A's. Because this can be done for all the other 5039 possible arrangements of the letters, by rule of product, there is a total of 5040 x 84 ways to arrange the letters in TALLAHASSEE such that the A's are not consecutive.
Sigma Notation
Given a list of n + 1 terms, such as am, am+1, am+2, ..., am+n, where m and n are integers and n ≥ 0, a concise way to write the sum of this list of terms is to use the notation called the Sigma notation.
The letter i is called the index of the summation, and this index accounts for all integers that start with the lower limit m to (and including) the upper limit m + n.
The above demonstrates that the index i does not have to be called i.
The above demonstrates that for this summation, the index i can be equal to either 1 or 0, because 0² is 0 anyway.
The above demonstrates that for this summation, if the index i (lower limit) and the upper limit increase by n, then i = i - n. If the lower limit and the upper limit decrease by n, then i = i + n.
The above demonstrates that if there is a scalar inside the summation, it can be simplified by factoring it out of the summation.
The above demonstrates that, instead of the index being a term itself, if the index was a subscript of a term, and the upper limit and lower limit increased by n, then i = i - n. If the upper limit and the lower limit decreased by n, then i = i + n. This is similar to the previous example of when the index was a term itself.
The above demonstrates that if there is no index present in the term a, then the term is written as a sum of an amount equal to the upper limit's value m, which is further simplified m(a).
Using summation notation can also simplify permutation and combination problems.
Example
A student is given directions about his exam that the student must answer seven of the ten questions, where at least three are selected from the first five out of ten questions.
There are three cases to consider:
Case 1: The student chooses to answer three of the first five questions and the four remaining questions of the last five questions. The number of ways the student can choose the three questions from the first five is C(5,3), and the number of ways the student can choose the four remaining from the last five questions is C(5,4). By the rule of product, the total ways the questions can be chosen given the conditions is C(5,3) x C(5,4) ways.
Case 2: The student chooses to answer four of the first five questions and the three remaining questions of the last five questions. By the rule of product, the total ways the questions can be chosen given the conditions is C(5,4) x C(5,3) ways.
Case 3: The student chooses to answer all of the first five questions and the two remaining questions from the last five. By the rule of product, the total ways the questions can be chosen given the conditions is C(5,5) x C(5,2) ways.
Using summation notation to simplify the total number of ways to select the questions to be answered:
C(5,3) x C(5,4) + C(5,4) x C(5,3) + C(5,5) x C(5,2)
Over-counting is a situation that seems to appear often in enumeration problems that look easy.
Example
Suppose that Ellen draws five cards from a standard deck of 52 cards. In how many ways can her selection result in a hand with no clubs?
We assume the deck of cards discarded all cards with clubs on them. That's 13 cards gone, and so there are a total of 52 - 13 = 39 cards for Ellen to choose from. Therefore, a total of C(39,5) ways to choose five cards with no clubs.
To found how many ways for Ellen to choose five cards from a standard deck where there are at least one club in her selection, the total number of ways Ellen can choose 5 cards from a standard deck with no regards whether her selection has clubs or not is C(52,5). In the previous question, it was found that there is a total of C(39,5) ways to choose five cards with no clubs at all. Therefore, the difference between these two selections (C(52,5) - C(39,5) = 2,023,203) equals the total number of possible selections of five cards with at least one club in the selection.
Using permutations and combinations for the previous question, suppose Ellen already has one club in her hand. Out of all the club cards there are in a standard deck, there is a total of C(13,1) ways she can select this club card. Since she already has at least one club card in her hand, the other four cards do not matter, and so since there are 52 - 1 = 51 cards left with 4 selections remaining, Ellen can choose the last four cards a total of C(51,4) ways. By the rule of product, this is a total of C(13,1) x C(51,4) = 3,248,700 ways.
However, notice that this answer is much bigger than the previous answer. That means either one of these answers is wrong. Since over-counting is more common in enumeration problems, the question with the larger answer is generally wrong. The reason the second answer is wrong is because, suppose Ellen first selects 3C (three of clubs). Next, she selects 5C-KC-7H-JS. Now suppose she instead first selects 5C, then 3C-KC-7H-JS. In fact, these two selections are not really different from each other. Additionally, suppose she selects the KC first, then 3C-5C-7H-JS. This selection is no different from the other two selections either. That is because we were considering like selections as being distinct, when in fact order does not matter in combination problems.
Instead, to use permutations correctly without over-counting, it is better to create cases.
Case 1: one club, four non-clubs, which is a total of C(13,1) x C(39,4) ways.
Case 2: two clubs, three non-clubs, which is a total of C(13,2) x C(39,3) ways.
Case 3: three clubs, two non-clubs, which is a total of C(13,3) x C(39,2) ways.
Case 4: four clubs, one non-club, which is a total of C(13,4) x C(39,1) ways.
Case 5: five clubs, no non-clubs, which is a total of C(13,5) x C(39,0) ways.
Note that there has to be at least one club in hand, so C(13,0) x C(39,5) is not a case.
Using summation notation to add these cases together:
C(13,1) x C(39,4) + C(13,2) x C(39,3) + C(13,3) x C(39,2) + C(13,4) x C(39,1) + C(13,5) x C(39,0)
Results Relating to the Concept of Combinations
There are three results that relate to the concept of combinations: binomial theorem, multinomial theorem, and the following result:
For the integers n and r, where n ≥ r ≥ 0, then C(n,r) = C(n,n-r). When dealing with a selection of size r from a collection of n distinct objects, the selection process leaves behind n - r objects. Therefore, C(n,r) = C(n,n-r) shows the existence of a correspondence between the selections of size r (the objects chosen) and the selections of size n - r (the objects not chosen but left behind).
Example
Let n = 5, r = 2, and the distinct objects are called 1, 2, 3, 4, and 5. Then the following table demonstrates the correspondence between C(n,r) and C(n,n-r):
Notice how C(n,r) and C(n,n-r) both have 10 possible combinations each. That is why C(n,r) = C(n,n-r).
Binomial Theorem
If x and y are variables and n is a positive integer, then the following equation can be written:
If n = 4, then (x + y)n = (x + y)⁴ = (x + y)(x + y)(x + y)(x + y), and the coefficient for the term x²y² in that expansion of four factors is the number of ways two x's can be selected from four x's, where these four x's are available from the four factors. Although the x's appear the same, they will be distinguished as four different x's: the x in the first factor, the x in the second factor, the x in the third factor, and the x in the fourth factor.
When selecting two x's from the four factors, two factors are used and then two factors remain. Those two remaining factors are then used to select the two y's that are also needed.
The following table demonstrates the six possible selections/combinations of choosing two factors for the two x's need and, since C(n,r) = C(n,n-r), the table also demonstrates the six possible selections/combinations of choosing the remaining factors for the two y's needed. Let the first factor (x + y) = 1, the second factor (x + y) = 2, the third factor (x + y) = 3, and the fourth factor (x + y) = 4.
There is a total of six combinations. Therefore, the coefficient for x²y² from the expansion (x + y)⁴ is 6. This method is much easier than expanding (x + y)⁴ and simplifying.
In general, the coefficient of xkyn-k, where 0 ≤ k ≤ n, is the number of different ways k x's (and corresponding to n - k y's) can be selected from n available factors, which is equal to C(n,k), where C(n,k) is called the binomial coefficient.
Note that, since C(n,k) = C(n,n-k), the following two notations are equivalent:
Example
Using the binomial theorem, the coefficient for xkyn-k = x⁵y² in the expansion of (x + y)n = (x + y)⁷ is C(n,k) = C(7,5) = 21.
To obtain the coefficient for a⁵b² in the expansion of (2a - 3b)⁷, first replace 2a with x and -3b with y, which results in finding the coefficient for x⁵y² in the expansion of (x + y)⁷, which is C(n,k) = C(7,5). Therefore C(7,5)x⁵y² = C(7,5)(2a)⁵(-3b)² = (2)⁵(-3)²C(7,5)(a)⁵(b)² = 6048a⁵b².
Note that, for each integer n ≥ 0, the following is true:
Multinomial Theorem
If n and t are positive integers, then the coefficient for x1n1x2n2x3n3...xtnt from the expansion of (x1 + x2 + ... + xt)n is the following:
where each ni is an integer such that 0 ≤ ni ≤ n for all 1 ≤ i ≤ t, and n1 + n2 + ... + nt = n.
It is also written as the following:
This equation is called a multinomial coefficient. When t = 2, the multinomial coefficient simplifies to the binomial coefficient.
Example
In the expansion of (x + y + z)⁷, by the multinomial theorem, the coefficient for x²y²z³ is the following:
The coefficient for xyz⁵ is the following:
And the coefficient for x³z⁴ is the following:
Example
To know the coefficient for a²b³c²d⁵ from the expansion of (a + 2b - 3c + 2d + 5)¹⁶, let a = v, 2b = w, -3c = x, 2d = y, and 5 = z. Then the multinomial becomes (v + w + x + y + z)¹⁶. By the multinomial theorem, the coefficient for v²w³x²y⁵z⁴ is the following:
Substituting the original variables becomes the following:
To check if this answer is correct, consider the first case of letter a. If no letter can be repeated, then there are 5 combinations to make a two letter pair with a. For case b, there are 4 combinations to make a two letter pair with b, because the pairs with a are already counted and order does not matter (ab = ba). For case c, there are 3 combinations to make two letter pairs with c. With d, there are 2 combinations. For e, there is one combination. And lastly, there are zero combinations for case f to make a new two letter pair with the other letters, because they have already been counted.
Therefore, there are 5 + 4 + 3 + 2 + 1 + 0 = 15 total combinations of the letters in size 2, no repetition and order is irrelevant.
Therefore, there are 5!/2! ways to arrange the five letters of size 3.
Therefore, there are 10 ways to select 3 letters from 5 letters.
a. There are a total of 20 people to select the committee of 12. Since no restrictions apply, then the following is the number of ways to select the 12 committee members:
b. There must be 6 men and 6 women in the committee of 12. Therefore, the following is the number of ways to select 6 men from 10 possible men and 6 women from 10 possible women:
c. Case 1: there are 2 women, 10 men
Case 2: there are 4 women, 8 men
Case 3: there are 6 women, 6 men
Case 4: there are 8 women, 4 men
Case 5: there are 10 women, 2 men
Note that we cannot have 12 women in the committee because there are only 10 women.
Therefore, the following is the total number of ways to select the committee of 12 such that there has to be an even number of women:
d. Case 1: there are 10 women, 2 men
Case 2: there are 9 women, 3 men
Case 3: there are 8 women, 4 men
Case 4: there are 7 women, 5 men
Note that there cannot be 6 women, because then there will be 6 men, and so then there is an equal amount of men and women in the committee.
Therefore, the total number of ways to select the committee of 12 such that there are more women than men is the following:
e. Case 1: there are 8 men, 4 women
Case 2: there are 9 men, 3 women
Case 3: there are 10 men, 2 women
Note that there cannot be a committee of 12 men, because there are only 10 men.
Therefore, the total number of ways to select the committee of 12 such that there are at least eight men is the following:
a. If there are no restrictions, the student can choose any seven of the ten questions on the exam. The following is the total number of ways he can select the seven questions:
b. If he must answer the first two questions, there is only one way to choose that. With five questions left to answer out of eight questions to choose from, the following is the total number of ways he can select the last five questions from the remaining eight questions:
c. Case 1: answers 4 of the first six, answers the remaining 3 of the last four
Case 2: answers 5 of the first six, answers the remaining 2 of the last four
Case 3: answers 6 of the first six, answers the remaining 1 of the last four
Therefore, the following is the number of ways he can select the seven questions out of the total ten questions such that he must answer at least four questions from the first six questions:
Combinations are used when there is a large possible selection to choose from instead of a selection that fits the number of objects.
If the S's are ignored, the following is the total number of ways to arrange the letters MIIIPPI
Notice how there are eight possible spaces to place each S (_M_I_I_I_P_P_I_). The total number of ways to select the positions for each S (there is a total of four S's) is the following:
Therefore, by the rule of product, the total number of arrangements of the word MISSISSIPPI such that there are no consecutive S's is the following:
a. Notice that each term's denominator goes up by 1, starting from 2 (lower limit) to n (upper limit). Therefore:
c. Notice that each term goes up by 1, starting from 1 (lower limit) to 7 (upper limit). Additionally, every even term is being subtracted. Therefore:
d. Notice that each term's numerator goes up by +1, starting from 0 (lower limit) to n (upper limit). Additionally, each term's denominator is going up by +1, starting from 0 (lower limit) to n (upper limit). Therefore:
a. Since xkyn-k = x⁹y³ and (x + y)n = (x + y)¹², by the binomial theorem, the coefficient for x⁹y³ from the expansion of (x + y)¹² is the following:
b. Let x = x, 2y = y. Since xkyn-k = x⁹y³ and (x + y)n = (x + y)¹², by the binomial theorem, the coefficient for x⁹y³ from the expansion of (x + y)¹² is the following:
Substituting back x = x and y = 2y gives the coefficient for x⁹y³ from the expansion of (x + 2y)¹²:
c. Let 2x = x and -3y = y. Since xkyn-k = x⁹y³ and (x + y)n = (x + y)¹², by the binomial theorem, the coefficient for x⁹y³ from the expansion of (x + y)¹² is the following:
Substituting back x = 2x and y = -3y gives the coefficient for x⁹y³ from the expansion of (2x - 3y)¹²:
a. Since xn1yn2zn3 = xyz² and (x + y + z)n = (x + y + z)⁴, then by the binomial theorem, the coefficient for xyz² from the expansion of (x + y + z)⁴ is the following:
b. Since wn1xn2yn3zn4 = xyz² and (w + x + y + z)n = (w + x + y + z)⁴, then by the binomial theorem, the coefficient for xyz² from the expansion of (w + x + y + z)⁴ is the following:
c. Let 2x = x, -y = y, -z = z. Since xn1yn2zn3 = xyz² and (x + y + z)n = (x + y + z)⁴, then by the binomial theorem, the coefficient for xyz² from the expansion of (x + y + z)⁴ is the following:
Substituting back x = 2x, y = -y, and z = -z, the coefficient for xyz² from the expansion of (2x - y - z)⁴ is the following:
e. Let 2w = w, -x = x, 3y = y, -2z = z. Since wn1xn2yn3zn4 = w³x²yz² and (w + x + y + z)n = (w + x + y + z)⁸, then by the binomial theorem, the coefficient for w³x²yz² from the expansion of (w + x + y + z)⁸ is the following:
Substituting back w = 2w, x = -x, y = 3y, and z = -2z, the coefficient for w³x²yz² from the expansion of (2w - x + 3y - 2z)⁸ is the following:
Show that for all m,n ∈ ℤ⁺, the following is true:
Suppose there is a group of m + n people and a team of m + 1 people needs to be created, assigning one of them as captain of the team.
The first way to do this is choose m team members out of the m + n people and then choose one of the the remaining n people as captain. By the rule of product, this can be done C(m + n,m)n ways.
The second way to do this is to choose m + 1 people for the team out of the m + n people, then choose one of the m + 1 players as captain. By the rule of product, this can be done C(m + n,m + 1)(m+1) ways.
Therefore, the above equation is true.
Use the binomial theorem to calculate the following:
Using the binomial theorem, the above can be rewritten as the following:
