﻿ Combinations and Permutations
COMBINATIONS AND PERMUTATIONS
by Dr. Carol JVF Burns (website creator)
Follow along with the highlighted text while you listen!
• PRACTICE (online exercises and printable worksheets)
• This section relies on your understanding of these concepts:

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.

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.

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

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: $$\cssId{s86}{ {}_5P_2 = \overset{\text{2 factors }}{\overbrace{ \underset{\undersetn}{\uparrow}}{5}\cdot 4} } } \quad \quad \quad \cssId{s87}{\text{ or } \quad \quad \quad {}_5P_3 = \overset{\text{3 factors}}{\overbrace{ \underset{\undersetn}{\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{\undersetn}{\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!

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, $$\cssId{s109}{ {}_nC_k} \cssId{s110}{= \frac{ {}_nP_k}{k!}} \cssId{s111}{= \frac{n!}{k!(n-k)!}}$$ Recall that an alternate notation for $\,{}_nC_k\,$ is $\,\binom{n}{k}\,$.
Master the ideas from this section