COMBINATIONS AND PERMUTATIONS

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\,$.

GETTING THE FORMULA FOR $\,{}_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: $${}_5P_2 = 5\cdot 4 = 5\cdot 4\cdot \frac{3!}{3!} = \frac{5\cdot 4 \cdot 3!}{3!} = \frac{5!}{3!} = \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: $${}_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
GETTING THE FORMULA FOR $\,{}_nC_k\,$

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\,$: $$\text{# of combinations} = \frac{\text{total # of permutations}}{\text{# in each colored pile}} = \frac{{}_5P_2}{2!} = \frac{20}{2!} = \frac{20}{2} = 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: $$\,\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: $$\text{# of combinations} = \,\frac{\text{total # of permutations}}{\text{# in each colored pile}} = \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:

FORMULAS FOR $\,{}_nP_k\,$
The notation $\,{}_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.

Let $\,n\,$ and $\,k\,$ be integers with $\ n\ge 1\$, $\ k\ge 1\$, and $\ k\le n\$.

Then, either of the following formulas can be used:
 $\,{}_nP_k\,$ $= \ \ n(n-1)(n-2)\cdot\ \ldots\ \cdot (n-(k-1))$ ($\,k\,$ factors) $\displaystyle = \ \ \frac{n!}{(n-k)!}$
For $\,k=0\,$, we define $\,{}_nP_0 := 1\,$.

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 way—choose 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: $${}_5P_2 = \overset{\text{2 factors}}{\overbrace{ \underset{\underset{\displaystyle n}{\uparrow}}{5}\cdot 4} } \quad \quad \quad \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 \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., $${}_{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} {}_{98}P_{11} &= \frac{98!}{(98-11)!} = \frac{98!}{87!} \cr\cr &= \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 &= \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!

FORMULAS FOR $\,{}_nC_k\,$
The notation $\,{}_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.

Let $\,n\,$ and $\,k\,$ be integers with $\ n\ge 1\$, $\ k\ge 0\$, and $\ k\le n\$.

Then, $${}_nC_k = \frac{{}_nP_k}{k!} = \frac{n!}{k!(n-k)!}$$ Recall that an alternate notation for $\,{}_nC_k\,$ is $\,\binom{n}{k}\,$.
Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Summation Notation

On this exercise, you will not key in your answer.
However, you can check to see if your answer is correct.
PROBLEM TYPES:
 1 2 3 4 5 6 7 8 9 10 11
AVAILABLE MASTERED IN PROGRESS
 (MAX is 11; there are 11 different problem types.)