Recall from a previous section that
$\,{}_nC_k\,$ denotes the number of ways to choose $\,k\,$ items from $\,n\,$
(without replacement)
when the order doesn't matter;
it is the number of combinations that are possible when choosing
$\,k\,$ items from $\,n\,$ items.
Also,
$\,{}_nP_k\,$ denotes the number of ways to choose $\,k\,$ items from
$\,n\,$ (without replacement) when the order does matter;
it is the number of permutations that are possible when arranging
$\,k\,$ items that are chosen from $\,n\,$ items.
In this section, formulas are developed for both $\,{}_nC_k\,$ and $\,{}_nP_k\,$.
First, an example.
Suppose that five letters are in an urn:
$\,\text{A}\,$, $\,\text{B}\,$, $\,\text{C}\,$,
$\,\text{D}\,$, and $\,\text{E}\,$.
You must choose two, without replacement, where order matters.
There are five choices for the first letter.
You don't put this letter back in the urn (since we're choosing without replacement),
so now only four letters are left in the urn.
Thus, there are four choices for the second letter.
By the Multiplication Counting Principle,
the number of possible outcomes is
$\,5 \cdot 4 = 20\,$.
Here are lots of different names for this number:
$$
\cssId{s19}{ {}_5P_2}
\cssId{s20}{= 5\cdot 4}
\cssId{s21}{= 5\cdot 4\cdot \frac{3!}{3!}}
\cssId{s22}{= \frac{5\cdot 4\cdot 3!}{3!}}
\cssId{s23}{= \frac{5!}{3!}}
\cssId{s24}{= \frac{5!}{(5-2)!}}
$$
(Recall that $\,5! := 5\cdot 4\cdot 3\cdot 2\cdot 1\,$;
this is factorial notation.)
Generalizing this example, we see that:
$$
\cssId{s28}{ {}_nP_k
= \frac{n!}{(n-k)!}}
$$
Here are the $\,20\,$ possible arrangements of two letters chosen from five, where order matters.
Arrangements that use the same letters have the same background color.
(Blanks have been inserted along the diagonal, so you can see the symmetry about this diagonal.)
AB | AC | AD | AE | |
BA | BC | BD | BE | |
CA | CB | CD | CE | |
DA | DB | DC | DE | |
EA | EB | EC | ED |
Continuing with the example above, we can now ask the question:
How many ways are there to choose two letters from five letters (without replacement),
when the order doesn't matter?
For this question, choosing ‘$\,\text{A}\,$’ first and ‘$\,\text{B}\,$’ second
gives the same combination as choosing ‘$\,\text{B}\,$’ first and ‘$\,\text{A}\,$’ second.
That is, the outcomes ‘$\,\text{AB}\,$’ and ‘$\,\text{BA}\,$’ both correspond to the same combination,
$\,\{\text{A},\text{B}\}\,$.
If we pick letters out of the urn and throw them into a basket, in both of these cases, the same two letters end up in the basket.
When we separate the $\,20\,$ permutations above into piles of the same color, we get:
AB BA | AC CA | AD DA | AE EA | BC CB |
BD DB | BE EB | DC CD | CE EC | DE ED |
Each colored pile corresponds to a single combination.
Since there are only
$\,2\cdot 1 = 2\,$ ways to arrange two letters,
each colored pile contains $\,2\,$ members.
How many piles are there?
To answer this, take the total number of permutations and divide them into piles of size $\,2! = 2\,$:
$$
\cssId{s47}{\text{# of combinations}}
\cssId{s48}{= \frac{\text{total # of permutations}}{\text{# in each colored pile}}}
\cssId{s49}{= \frac{ {}_5P_2}{2!}}
\cssId{s50}{= \frac{20}{2!}}
\cssId{s51}{= \frac{20}{2}}
\cssId{s52}{= 10}
$$
But what if we had chosen three letters from the urn, instead of two?
Then, a typical permutation might look like ‘$\,\text{DBA}\,$’.
How many different arrangements are there of these three letters?
Using the Multiplication Counting Principle again, there are
$\,3!=3\cdot 2\cdot 1 = 6\,$ arrangements:
$$\,
\cssId{s57}{\text{DBA}\,,
\,\text{DAB}\,,
\,\text{BDA}\,,
\,\text{BAD}\,,
\,\text{ADB}\,,
\,\text{ABD}}
$$
Thus, in choosing $\,3\,$ letters from an urn, the total number of permutations would be broken up into piles
of size $\,3!\ $.
In this case:
$$
\cssId{s60}{\text{# of combinations}}
\cssId{s61}{= \,\frac{\text{total # of permutations
}}{\text{# in each colored pile}}}
\cssId{s62}{= \frac{ {}_5P_3}{3!}}
$$
You should see the pattern $\,\displaystyle\frac{ {}_nP_k}{k!}\,$ emerging as the formula
for the number of combinations!
Indeed, generalizing these observations gives the following formulas for permutations and combinations:
$\,{}_nP_k\,$ | $= \ \ n(n-1)(n-2)\cdot\ \ldots\ \cdot (n-(k-1))$ | ($\,k\,$ factors) |
$\displaystyle = \ \ \frac{n!}{(n-k)!}$ |
Note that it makes sense that
$\,{}_nP_0 := 1\,$
should equal one:
How many ways are there to choose no items from an urn?
Exactly one waychoose nothing!
If $\,k\,$ is small, then it's easiest to use the first formula to compute $\,{}_nP_k\,$:
just start with $\,n\,$ and write down $\,k\,$ factors.
For example:
$$
\cssId{s86}{ {}_5P_2
=
\overset{\text{2 factors
}}{\overbrace{
\underset{\underset{\displaystyle n}{\uparrow}}{5}\cdot 4} }
} \quad \quad \quad
\cssId{s87}{\text{ or } \quad \quad \quad
{}_5P_3
=
\overset{\text{3 factors}}{\overbrace{
\underset{\underset{\displaystyle n}{\uparrow}}{5}\cdot 4\cdot 3} }
} \quad \quad \quad
\cssId{s88}{\text{ or } \quad \quad \quad
{}_{11}P_3
=
\overset{\text{3 factors}}{\overbrace{
\underset{\underset{\displaystyle n}{\uparrow}}{11}\cdot 10\cdot 9}
} }
$$
As $\,k\,$ gets larger, it might be easier to use the second formula,
and use your calculator or wolframalpha.com:
e.g.,
$$
\cssId{s92}{ {}_{20}P_8 = \frac{20!}{(20-8)!}}
$$
At some point, however, the numbers involved will get sufficiently large that your
calculator will fail you,
and you'll have to do it this way:
$$
\begin{align}
\cssId{s95}{ {}_{98}P_{11}} &\cssId{s96}{= \frac{98!}{(98-11)!}} \cssId{s97}{= \frac{98!}{87!}} \cr\cr
&\cssId{s98}{= \frac{98\cdot 97\cdot 96\cdot 95\cdot 94\cdot 93\cdot 92\cdot 91\cdot 90\cdot 89\cdot 88\cdot 87!}{87!}}\cr\cr
&\cssId{s99}{= \overset{\text{11 factors}}{\overbrace{98\cdot 97\cdot 96\cdot 95\cdot 94\cdot 93\cdot 92\cdot 91\cdot 90\cdot 89\cdot 88}}}
\end{align}
$$
which brings you right back to the first formula again!
On this exercise, you will not key in your answer. However, you can check to see if your answer is correct. |
PROBLEM TYPES:
|