7.3: Permutations and Combinations
- Page ID
- 40935
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We saw in the last section that, when working with permutations, the order is always important. If we were choosing 3 people from a group of 7 to serve on a committee with no assigned roles, the nature of the problem would change.
For example, if we were choosing 3 people from a group of 7 to serve on a committee as president, vice-president and treasurer, the answer would be \(_{7} P_{3}=210\) But - if we wanted to choose 3 people from a group of 7 with no assigned roles, then some of the choices in the permutation would be the same.
In a permutation:
1st place: Alice 1st place: Bob 2nd place: Bob \(\quad\) 2nd place: Charlie 3rd place: Charlie \(\quad\) 3rd place: Alice
the two choices listed above would be considered as being different and would be counted separately. In a "combination" in which the order of selection is not important and there are no assigned roles, we must compensate for these extra choices.
If we are choosing 3 people from a group of 7 to serve on a committee with no assigned roles then we should consider that any selection from a permutation that includes the same three people should only be counted once.
So, when we select the three people, we should consider how many different ways there are to group them and then remove those extra choices. In this example, we are choosing three people. Each group of three can be arranged in six different ways \(3 !=3 * 2=6,\) so each distinct group of three is counted six times.
In order to find the actual number of choices we take the number of possible permutations and divide by 6 to arrive at the actual answer:
\[
_{7} C_{3}=\frac{7 P_{3}}{3 !}=\frac{7 !}{4 ! * 3 !}
\]
In a combination in which the order is not important and there are no assigned roles the number of possibilities is defined as:
\[
_{n} C_{r}=\frac{n !}{(n-r) ! * r !}
\]
One way to remember the difference between a permutation and a combination is that on a combination pizza it doesn't make any difference whether the sausage goes on before the pepperoni or whether the onions are put on first-so in a combination, order is not important!
EXERCISES 7.3
Find the value of the following expressions.
1) \(\quad _{10} C_{4}\)
2) \(\quad _{8} C_{3}\)
3) \(\quad _{10} C_{6}\)
4) \(\quad _{8} C_{5}\)
5) \(\quad _{15} C_{12}\)
6) \(\quad _{18} C_{2}\)
7) \(\quad _{n} C_{4}\)
8) \(\quad _{9} C_{r}\)
9) How many three-topping pizzas can be made if there are twelve toppings to choose from?
10) How many bridge hands of 13 cards are possible from a deck of 52 cards?
11) How many poker hands of 5 cards are possible from a deck of 52 cards?
12) How many different bridge hands of 13 cards are possible if none of the cards is higher than 10 (i.e. no face cards)?
13) How many different poker hands of 5 cards are possible if none of the cards is higher than \(8 ?\)
14) If a person has 10 different t-shirts, how many ways are there to choose 4 to take on a trip?
15) If a band has practiced 15 songs, how many ways are there for them to select 4 songs to play at a battle of the bands? How many different performances of four songs are possible?
16) Fifteen boys and 12 girls are on a camping trip. How many ways can a group of seven be selected to gather firewood:
\(\quad\) a) with no conditions
\(\quad\) b) the group contains four girls and three boys
\(\quad\) c) the group contains at least four girls
17) A class of 25 students is comprised of 15 girls and 10 boys. In how many ways can a committee of 8 students be selected if:
\(\quad\) a) there are no restrictions
\(\quad\) b) no males are included on the committee
\(\quad\) c) no females are included on the committee
\(\quad\) d) the committee must have 5 boys and 3 girls
18) From a group of 12 male and 12 female tennis players, two men and two women will be chosen to compete in a men-vs-women doubles match. How many different matches are possible?
19) In a seventh-grade dance class, there are 20 girls and 17 boys.
\(\quad\) a) How many ways can the students be paired off to create dance couples consisting of one boy and one girl?
\(\quad\) b) How many ways are there to create a group of 17 boy/girl couples?
\(\quad\) c) How many ways are there to create a group of 18 couples without restrictions?