3.2: The Multinomial
- Page ID
- 130489
\( \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}}} \)
With the topic of combinations under our belt, we will now consider the following question.
In a hospital, 14 nurses are to be divided so that 5 nurses are in Unit 1 (Cardiac Unit), 4 nurses are in Unit 2 (Emergency Room), 3 nurses are in Unit 3 (Medical Surgery) and 2 nurses are in Unit 4 (Labor and Delivery). How many different ways are there to divide the 14 nurses?
Answer
We can think of an outcome as having the following structure: \( ( \underbrace{\_, \_, \_, \_, \_}_{Cardiac.} , \underbrace{\_, \_, \_, \_ }_{ER} , \underbrace{\_, \_, \_ }_{MedSurg.} , \underbrace{\_, \_, }_{Labor} ) \). We now proceed in steps:
1. We first choose 5 nurses to be assigned to the Cardiac unit. There are \( \binom{14}{5} \) ways to do this.
2. We now select 4 nurses to be assigned to the Emergency Room. There are \( \binom{9}{4} \) ways to do this.
3. We then select 3 nurses to be assigned to the Medical Surgery unit. There are \( \binom{5}{3} \) ways to do this.
4. We then select 2 nurses to be assigned to the Labor and Delivery unit. There are \( \binom{2}{2} \) ways to do this.
By The Generalized Principle of Counting, there are \( \binom{14}{5} \times \binom{9}{4} \times \binom{5}{3} \times \binom{2}{2} = 2,522,520\) different divisions.
While this answers the question, notice the following:
\[ \binom{14}{5} \times \binom{9}{4} \times \binom{5}{3} \times \binom{2}{2} = \frac{14!}{5! ~ 9!} \times \frac{9!}{4! ~ 5!} \times \frac{5!}{3! ~ 2!} \times \frac{2!}{2! ~0!} = \frac{14!}{5! ~ 4! ~ 3! ~ 2!} \nonumber\ \]
Does the term \( \dfrac{14!}{5! ~ 4! ~ 3! ~ 2!} \) seem familiar?
This resembles the number of ways to arrange 14 elements when 5 objects are of Type 1, 4 objects are of Type 2, 3 objects are of Type 3 and 2 objects are of Type 4.
We will now generalize the above result.
If \(n\) distinct elements are to be divided among \(k\) distinct groups such that:
- Group 1 has \(n_1\) elements,
- Group 2 has \(n_2\) elements,
- \( \ldots \)
- Group k has \(n_k\) elements,
and \( n_1 + n_2 + \ldots + n_k = n \), then the number of different divisions is given by
\[ \frac{n!}{n_1 ! n_2 ! \ldots n_k !} \nonumber\ \]
Proof: We proceed in steps:
1. We first choose \(n_1\) elements to be assigned to Group 1. There are \( \binom{n}{n_1} \) ways to do this.
2. We first choose \(n_2\) elements to be assigned to Group 2. There are \( \binom{n-n_1}{n_2} \) ways to do this.
3. We first choose \(n_3\) elements to be assigned to Group 3. There are \( \binom{n - n_1 - n_2}{n_3} \) ways to do this.
...
k. We first choose \(n_k\) elements to be assigned to Group k. There are \( \binom{n - n_1 - n_2 - \ldots - n_{k-1}}{n_k} \) ways to do this.
By The Generalized Principle of Counting, there are \( \binom{n}{n_1} \times \binom{n-n_1}{n_2} \times \binom{n - n_1 - n_2}{n_3} \times \ldots \times \binom{n - n_1 - n_2 - \ldots - n_{k-1}}{n_k} = \frac{n!}{n_1! (n-n_1)!} \times \frac{(n-n_1)!}{n_2!(n-n_1-n_2)!} \times \frac{n_2!(n-n_1-n_2)!}{n_3! (n-n_1-n_2-n_3)!} \times \ldots \frac{(n - n_1 - n_2 - \ldots - n_{k-1})!}{n_k! (n - n_1 - n_2 - \ldots - n_{k-1} - n_k)!} = \frac{n!}{n_1 ! n_2 ! \ldots n_k !} \) different divisions.