7.5: Distinguishable Permutations
- Page ID
- 40937
\( \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}\)If there is a collection of 15 balls of various colors, then the number of permutations in lining the balls up in a row is \(_{15} P_{15}=15 !\). If all of the balls were the same color there would only be one distinguishable permutation in lining them up in a row because the balls themselves would look the same no matter how they were arranged.
If 10 of the balls were yellow and the other 5 balls are all different colors, how many distinguishable permutations would there be?
No matter how the balls are arranged, because the 10 yellow balls are indistinguishable from each other, they could be interchanged without any perceptable change in the overall arrangement. As a result, the number of distinguishable permutations in this case would be \(\frac{15 !}{10 !},\) since there are \(10 !\) rearrangements of the yellow balls for each fixed position of the other balls.
The general rule for this type of scenario is that, given \(n\) objects in which there are \(n_{1}\) objects of one kind that are indistinguishable, \(n_{2}\) objects of another kind that are indistinguishable and so on, then number of distinguishable permutations will be:
\[
\begin{array}{c}
n ! \\
\frac{n}{n_{1} ! * n_{2} ! * n_{3} ! * \cdots * n_{k} !} \\
\text { with } n_{1}+n_{2}+n_{3}+\cdots+n_{k}=n
\end{array}
\]
Example
Find the number of ways of placing 12 balls in a row given that 5 are red, 3 are green and 4 are yellow.
This would be \(\frac{12 !}{5 ! 3 ! 4 !}=\frac{12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1}{5 * 4 * 3 * 2 * 3 * 2 * 4 * 3 * 2}\)
\[
\begin{array}{l}
=\frac{12 * 11 * 10 * 9 * 8 * 7 * 6}{3 * 2 * 4 * 3 * 2} \\
=27,720
\end{array}
\]
Another way to think about this problem is to choose five of the twelve spaces in which to place the red balls - since the order of selection is not important, there are \(_{12} C_{5}\) ways to do this. Then, from the remaining 7 spaces available, we need to choose three of them in which to place the green balls. There are \(_{7} C_{3}\) ways to do that. The four yellow balls are then placed in the remaining four spaces.
The result of this process is that there are \(_{12} C_{5}\) ways to choose the places for the red balls and \(_{7} C_{3}\) ways to choose the places for the green balls, which results in:
\[
_{12} C_{5} *_{7} C_{3}=\frac{12 !}{5 ! 7 !} * \frac{7 !}{3 ! 4 !}=\frac{12 !}{5 ! 3 ! 4 !}
\]
This results in the same answer as when we approached the problem as a permutation. Considering the problem in this way helps us to solve problems which involve the assigning of tasks to groups of individuals.
Example
Fourteen construction workers are to be assigned to three different tasks. Six workers are needed for mixing cement, five for laying bricks and three for carrying the bricks to the brick layers. In how many different ways can the workers be assigned to these tasks?
This is also a problem of distinguishable permutation. Although the order of the workers is not important here, the result is the same:
\[
\frac{14 !}{6 ! 5 ! 3 !}
\]
Another way to think about problems of this type is that they are combination problems, since the order in which the workers are assigned is not important. In that case, we need to select six of the fourteen workers to mix cement, five to lay bricks and three to carry bricks.
To select six workers to mix cement: \(\quad_{14} C_{6}=\frac{14 !}{6 ! 8 !}\)
To select five workers (from the remaining 8) to lay bricks: \(\quad_{8} C_{5}=\frac{8 !}{5 ! 3 !}\)
To select three workers (from the reamining three) to carry bricks: 1
If there are \(\frac{14 !}{6 ! 8 !}\) ways to choose the cement crew and \(\frac{8 !}{5 ! 3 !}\) ways to choose the bricklayers from the remaining eight workers, then there will be:
\[
\frac{14 !}{6 ! 8 !} * \frac{8 !}{5 ! 3 !}=\frac{14 !}{6 ! 5 ! 3 !}
\]
ways to assign the workers to these tasks.
Exercises 7.5
Find the number of distinguishable permutations of the given letters.
1) \(\quad A A A B B C\)
2) \(\quad A A A B B B C C C\)
3) \(\quad A A B C D\)
4) \(\quad A B C D D D E E\)
5) In how many ways can two blue marbles and four red marbles be arranged in a row?
6) In how many ways can five red balls, two white balls, and seven yellow balls be arranged in a row?
7) In how many different ways can four pennies, three nickels, two dimes and three quarters be arranged in a row?
8) In how many ways can the letters of the word ELEEMOSYNARY be arranged?
9) A man bought three vanilla ice-cream cones, two chocolate cones, four strawberry cones and five butterscotch cones for 14 children. In how many ways can he distribute the cones among the children.
10) When seven students take a trip, they find a hotel with three rooms available - a room for one person, a room for two poeple and a room for three people. In how many different ways can the students be assigned to these rooms? (one student will sleep in the car)
11) Eight workers are cleaning a large house. Five are needed to clean windows, two to clean carpets and one to clean the rest of the house. In how many different ways can these tasks be assigned to the eight workers?