7.11: Factorials and Combinations
Kelly and Kyle are playing a card game, and Kyle is wondering why there never seem to be repeated hands. He figures that since there are only 52 cards in the deck, and each hand has five cards, there really should be more duplicate hands. After all, 5 is nearly 1/10 of 52.
Kelly tells him that she thinks there are thousands of possible combinations, and that she would be really surprised to see the same 5 card hand twice or more in a given game.
Who is correct? Why?
Watch This
Embedded Video:
- Khan Academy: Permutations and Combinations
Guidance
Recall that a factorial of a positive integer n is the product of n, and all of the positive integers less than n. We write this as n! = n(n - 1)(n - 2) .. (3) (2) (1).
In order to develop the binomial theorem, we need to look at a related idea: combinations. If you have studied probability, you may be familiar with combinations and permutations. A combination is the number of ways you can choose r objects from a group of n objects, if the order of choosing does not matter. An example will help clarify the idea of a combination:
Example A
In a class of 20 students, 3 students are going to be chosen to form a committee to plan a fieldtrip. How many possible committees are there?
Solution
- To answer this question, we need to figure out how many ways we can choose groups of 3 students from the 20 on the class. The order of choosing does not matter. That is, if I choose Amy, Juan, and Nina, it is the same as choosing Juan, then Amy, then Nina, or any other ordering of the three students.
In general, we can find the number of combinations of r objects chosen from n objects by the following:
\begin{align*}_{n}C_{r} = \binom{n} {r} = \frac{n!} {r!(n - r)!}\end{align*} |
---|
(Note that there are two different symbols for combinations: \begin{align*}_{n}C_{r}\end{align*} and \begin{align*}\binom{n} {r}\end{align*} You can use either one, though \begin{align*}_{n}C_{r}\end{align*} is what is used on the TI-83/84.
- Therefore the number of combinations of 3 people from 20 people in the class is
\begin{align*}\frac{20!} {3!17!} = 1140\end{align*} |
---|
Example B
How many different groups of 3 cards can be chosen from 20 different cards, assuming order does not matter? Use a graphing calculator.
Solution
To find \begin{align*}\binom{20} {3} \end{align*}
- Press: 20 <TI font_MATH> and then move right to the PRB menu.
- Press 3. This takes you back to the main screen. You should see 20 \begin{align*}_{n}C_{r}\end{align*}.
- Now press 3 >,TI font_ENTER>.
- You should see the answer, 1140.
Example C
Calculate by hand: How many different 4-person teams can be made from 7 people?
Solution
Smaller numbers, such as these, are not too difficult to calculate by hand.
- \begin{align*}\binom{7} {4} = \frac{7!} {4!3!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} {4 \cdot 3 \cdot 2 \cdot 1 \cdot 3 \cdot 2 \cdot 1} = \frac{7 \cdot 6 \cdot 5} {3 \cdot 2 \cdot 1} = 7 \cdot 5 = 35\end{align*}.
Canceling factors in the numerator and denominator simplifies the calculation.
Concept question wrap-up Recall in the introduction we learned of the disagreement between Kelly and Kyle? Kelly thinks there are thousands of possible 5-card combinations in a deck of cards, Kyle thinks there should not be all that many. This is a classic combinations problem in the form "52, choose 5":
Looks like Kelly undershot by quite a bit too! |
---|
Vocabulary
A combination refers to choosing one or more objects from a set when the order of choosing does not matter.
A factorial refers to the product of the positive integers from 1 to some value n: 1 × 2 × 3 × 4 × .... × (n - 1) × n = n!
Guided Practice
Questions
1) Simplify: \begin{align*}\frac{(m + 3)!}{m + 1}!\end{align*}
2) Demonstrate that: \begin{align*}_{2(4)}C_2 = 2(_4C_2) + 4^2\end{align*}
3) In how many ways can i pick 6 jelly beans from a container containing 10 jelly beans?
4) At the carnival, you decide to play a game of chance. You buy 15 tickets for the game. You have a 75% chance of winning each time you play the game. What is the probability that you will win exactly 8 of the 15 games?
5) Explain why the following equality holds.
- \begin{align*}_{(n+1)}C_r = _nC_r + _n C _{r-1}\end{align*}
Solutions
1) First we need to expand the numerator and denominator:
- \begin{align*}\frac{(m + 3)(m + 2)(m + 1)(m)(m - 1)...(1)}{(m + 1)(m)(m - 1)...(1)}\end{align*}
- \begin{align*}(m + 3)(m + 2)\end{align*} ..... Cancel common factors
- \begin{align*} m^2 + 5m +6\end{align*} ..... Simplify
2) Evaluate both sides:
- \begin{align*}_8C_2 = 28\end{align*}
- \begin{align*}_4C_2 = 6\end{align*}
- \begin{align*} 4^2 = 16\end{align*}
Check: \begin{align*}28 = 2(6) + 16\end{align*}
- \begin{align*}28 = 12 + 16\end{align*}
- \begin{align*}28 + 28\end{align*} - the equality holds.
3) We calculate using the formula:\begin{align*}_{10}C_6 = \frac{10!}{6!(10 - 6)!}\end{align*}
- \begin{align*}10! = (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)\end{align*}
- \begin{align*}10! = 3628800\end{align*}
- \begin{align*}6! = (1)(2)(3)(4)(5)(6)\end{align*}
- \begin{align*}6! = 720\end{align*}
- \begin{align*}(10 - 6)! = (1)(2)(3)(4)\end{align*}
- \begin{align*}(10-6)! = 24\end{align*}
\begin{align*}\therefore _{10}C_6 = \frac{3628800}{720 \cdot 24} \to 210\end{align*}
4) The chance is about 4%
- For each of the 15 games, there is 75% chance of winning, and a 25% chance of losing.
- The probability of exactly 8 wins is \begin{align*}\mathit \ \binom{15}{8}(.75)^{8}(.25)^{7}\approx 0.039 \to 3.9%\end{align*}
- Note that this is only the probability of winning exactly 8 games, no more, no less.
5) Proof of equality:
- a) remove one item from the set.
- b) either the (r) item we want to come out of the remaining (n)items, or
- c) we choose (r - 1) item from the (n) remaining items and we include the one item we removed.
Practice
Simplify and Evaluate the Factorials.
- \begin{align*}\frac{(b - 2)!}{(b - 5)!}\end{align*}
- \begin{align*}\frac{(a + 2)!}{(a + 1)!}\end{align*}
- \begin{align*}\frac{7!}{3! 3!}\end{align*}
- \begin{align*}\frac{9!}{8!}\end{align*}
- \begin{align*} 4! + 3!\end{align*}
- \begin{align*}\frac {6!}{5!}\end{align*}
Show that the equality holds by evaluating both sides of the equation:
- \begin{align*}_4C_2 = _4C_{4-2}\end{align*}
- \begin{align*}_{(7+1)}C_4=_7C_4 + _7C_{(4-1)}\end{align*}
Explain conceptually why the following equality holds:
- \begin{align*}_{2n}C_2 = 2(_nC_2) + n^2\end{align*}
Solve
- \begin{align*} _{8}C_{5}\end{align*}
- \begin{align*} _{6}C_{3}\end{align*}
- In a class of 200 students, 25 will be chosen randomly to participate in a research study. How many possible groups of 25 students can be chosen? (Hint: use a calculator!)
- A die is rolled 10 times. What is the probability of rolling exactly four 4’s? (Hint: the probability of rolling a 4 is 1/6. The probability of not rolling a 4 is 5/6.)
- The local TV station forecasts a 30% chance of rain every day for the next week. What is the probability that it will rain on exactly 6 out of the next 7 days?
- Consider the following situation: a basketball player is going to attempt to make 20 free throws. She is assuming that she has an 80% chance of making each shot. What is the probability that she will make exactly 19 out of 20 shots?
- Two students were discussing this problem. Student A says that the problem is a Bernoulli trial, and that the probability is \begin{align*}\binom{20}{19}(.8)^{19}(.2)^1\end{align*} Student B disagrees, and says that the situation is not a Bernoulli trial. What reasoning might student B use to support his argument?
!
The factorial of a whole number is the product of the positive integers from 1 to . The symbol "!" denotes factorial. .combination
Combinations are distinct arrangements of a specified number of objects without regard to order of selection from a specified set.factorial
The factorial of a whole number is the product of the positive integers from 1 to . The symbol "!" denotes factorial. .Permutation
A permutation is an arrangement of objects where order is important.Probability
Probability is the chance that something will happen. It can be written as a fraction, decimal or percent.Image Attributions
Here you will review factorials and combinations in preparation for their use in Pascal's Triangle and the Binomial Theorem.