(last updated: 3:53:38 PM, October 20, 2020)
If a process takes 2 steps with the first step having \(N_1\) options and the second step having \(N_2\) options, and the number of options for one step does not depend on how the other step is completed, then the total number of ways the 2 step process can be done is \(N_1\times N_2\).
This also generalizes to any number of steps: \(N_1\times N_2 \times \cdots N_k\).
We say the steps are independent when the number of options for any step of a multi-step process does not depend on how the other steps are completed.
Example: A menu has 3 options for appetizer, 2 options for drink, 5 options for main course, and 2 options for dessert. A meal is created by choosing one item for each course on the menu. How many meals are possible?
Solution: There are \(3\cdot 2\cdot 5\cdot 2=60\) different ways a complete meal can be constructed.
Example: A committee people of 3 is to be formed out of 10 people. The committee memebrs will have roles assigned: chair, vice chair, and secretary. How many distinct committees are there?
Solution: There are \(10\cdot 9\cdot 8=720\) distinct committees possible.
Note that a committee is distinct from another if at least one person is different or if it is the same 3 people, if at least one of those is assigned a different role.
Example: 100 people run a race and the top 3 times will be awarded 1st, 2nd, and 3rd place. How many distinct outcomes fo rthe race are possible? (I.e. how many distnct ways are there to award the places?)
Solution: There are \(100\cdot 99\cdot 98\) distinct committees possible.
\[n!=n\cdot (n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1\] This gives the number of ways to arrange \(n\) distinct objects in order.
\[0!=1\] \[1!=1\]
\[_n P_k =\frac{n!}{(n-k)!}\]
\[_n C_k ={ n \choose k}=\frac{n!}{k!(n-k)!}\]
\[{ n \choose k_1,k_2,\ldots,k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}\]
Example:
How many distinct ways are there to rearrange the letters of the word “MAMMAL”?
Solution: Notice there are 3 M’s, 2 A’s and 1 L. One possible rearranging is “LAMMMA”. Now if we were to shuffle the M’s that wouldn’t change it. We assume that the M’s are indistinguishable from one another.
Let’s color them to to illustrate: “LAMMMA” is the same as “LAMMMA” (note that the 1st and 2nd M’s were swapped). The M’s are only colored to illustrate the fact that they were swapped. We are not concerned about the color of the letters in this problem; we just want to know which letter of the alphabet is in each position.
So we have 6 total spaces to fill with a letter, and we will choose 3 spaces for the M’s, 2 spaces for the A’s, and one space for the L. This is “6 choose 3,2,1” given by \[ {6 \choose 3,2,1}=\frac{6!}{3!2!1!} =\frac{6\times5\times4\times3\times2\times1}{(3\times2\times1) \cdot (2\times1)\cdot 1}=5\times4\times3=60 \]
\[ \diamond \S \diamond \]