4. Permutations and Combinations
- Page ID
- 21225
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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{\longvect}{\overrightarrow}\)
\( \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}\)Contents 4A:
- Intro to Permutations (https://youtu.be/KC_1q9B_ZC8)
- Permutations, example 2 (https://youtu.be/rlnP0Fyzu4Y)
- Permutations, example 3 (https://youtu.be/jenG9qqv4wU)
- Permutation Notation and Guidelines (https://youtu.be/w40Ux--z3Q0)
- Permutations, example 4 (https://youtu.be/hosEvvBUJjY)
- Permutations with stages (https://youtu.be/4ItZ7KyTzSo)
- Permutations with cases and stages (https://youtu.be/r00rtKKtTTc)
- Permutations with complements (https://youtu.be/pnP6ODB1GUM)
- Rearrangements of Letters (https://youtu.be/gVp06_yOTLE)
Example \(\PageIndex{1}\)
Our classroom has 35 seats and 30 students. If any student could sit in any open seat, how many different seating arrangements are possible?
Solution
When the first student walks in, she has 35 options of where to sit. The second student then has 34 options remaining. The third has 33, and so on. Therefore, the answer is \(P(35,30)\).
Prework 4A:
- There are 8 runners in a race. In how many ways can gold, silver, and bronze medals be awarded? Please write your answer using permutation notation and also figure out a numerical value.
- An organization consisting of 8 females and 2 males meets to elect a president, secretary, and treasurer. In how many ways can the positions be filled? In how many ways can they be filled if both sexes must be represented?
- How many 10-letter “words” can be made from the word “antarctica”?
Solutions for Prework 4A:
- Since no runner can receive more than 1 medal, repeats are not allowed. Since the order in which the runners finish determines who gets each medal, the order does matter. Therefore, we use a permutation. There are 8 runners and 3 will get medals so the answer is \(P(8,3)=8\cdot 7\cdot 6=336\).
- One person cannot be in two roles (no repeats), and the roles are clearly different (order matters/different roles) so we can use a permutation. Since there are 10 total people and 3 must be selected, the answer is \(P(10,3)\). For the second part of the problem, we will use the complement. The complement of the set of choices in which both sexes must be represented is the set of choices in which only one sex is represented. There are 0 ways in which only males can fill the roles since there are 3 roles and only 2 males. There are \(P(8,3)\) ways in which only females can fill the roles since there are 8 females. Hence the total number of ways in which only one sex is represented is \(P(8,3)\). Therefore, the number of ways in which both sexes can be represented is \(P(10,3)-P(8,3)\).
- There are 10 letters in "antarctica" with 3 a's, 2 t's, and 2 c's. Hence, the answer is \(\frac{10!}{3!2!2!}\).
Contents 4B:
- Intro to Combinations (https://youtu.be/JL6SyzNLS6k)
- Combination Notation (https://youtu.be/2gb0K-w3Vw8)
- Combination or Permutation? (https://youtu.be/ejhH4J9Yg44)
- Combinations with Cases (https://youtu.be/jCWaLRF8V3c)
- Combinations with Stages (https://youtu.be/zAYTTRtCo38)
- Combinations with Complements (https://youtu.be/xAThjZFRcfM)
The problem in the following video is solved in two ways: first using cases and stages, and then using complements.
Prework 4B:
- Evaluate \(C(10,4)\).
- A student has volunteered to bring the chips for a pot-luck party. She is in a hurry and runs into a grocery store to get 3 different kinds of chips. There are 10 different kinds of chips on the shelf. How many ways can she choose the 3 bags of chips if they all have to be different kinds?
- Out of Sarah, Jennifer, Jason, and Quentin, I randomly select at least one person but at most three people to take the survey, how many groups could I choose?
Solutions for Prework 4B:
-
\(C(10,4)=\frac{10!}{6!4!}=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{6\cdot5\cdot4\cdot3\cdot2\cdot1\cdot4\cdot3\cdot2\cdot1}=210.\)
-
Since the student is getting different kinds of chips, repeats are not allowed. Furthermore, the order in which she purchases the chips does not matter as they all will end up at the party. Therefore we use a combination, so the answer is \(C(10,3)\).
-
We can use combinations here since no one will take the survey more than once (no repeats) and since all participants have the same roll: taking the survey. There are three cases to consider: exactly 1 person takes the survey, exactly 2 people take the survey, exactly 3 people take the survey. Therefore, the answer is \(C(4,1)+C(4,2)+C(4,3)\).