# Combinations and Permutations

This section relies on your understanding of these concepts:

- Basic Probability Concepts
- More Probability Concepts
- Choosing Things: Does Order Matter?
- Factorial Notation

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:

$$ \begin{align} \cssId{s19}{ {}_5P_2}\ &\cssId{s20}{= 5\cdot 4}\cr & \cssId{s21}{= 5\cdot 4\cdot \frac{3!}{3!}} \cssId{s22}{= \frac{5\cdot 4\cdot 3!}{3!}}\cr &\cssId{s23}{= \frac{5!}{3!}} \cssId{s24}{= \frac{5!}{(5-2)!}} \end{align} $$(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 |

## 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:

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\,$: $$ \begin{align} &\cssId{s47}{\text{# of combinations}}\cr\cr &\qquad \cssId{s48}{= \frac{\text{total # of permutations}}{\text{# in each colored pile}}}\cr\cr &\qquad \cssId{s49}{= \frac{ {}_5P_2}{2!}}\cr\cr &\qquad \cssId{s50}{= \frac{20}{2!}} \cssId{s51}{= \frac{20}{2}} \cssId{s52}{= 10} \end{align} $$

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:

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:

$$ \begin{align} &\cssId{s60}{\text{# of combinations}}\cr\cr &\qquad \cssId{s61}{= \,\frac{\text{total # of permutations }}{\text{# in each colored pile}}}\cr\cr &\qquad \cssId{s62}{= \frac{ {}_5P_3}{3!}} \end{align} $$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:

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:

$$ \begin{align} &\cssId{s73}{ {\,}_nP_k }\cr\cr &\quad \cssId{s74}{= \ n(n-1)(n-2)\cdot\ \ldots\ \cdot (n-(k-1))}\cr &\quad\ \ \ \ \ \cssId{s75}{\text{($\,k\,$ factors)}}\cr\cr &\quad \cssId{s76}{= \ \frac{n!}{(n-k)!}} \end{align} $$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{\underset{\displaystyle n}{\uparrow}}{5}\cdot 4} } } $$or

$$ \cssId{s87}{ {}_5P_3 = \overset{\text{3 factors}}{\overbrace{ \underset{\underset{\displaystyle n}{\uparrow}}{5}\cdot 4\cdot 3} } } $$or

$$ \cssId{s88}{ {}_{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}}\cr &\quad \cssId{s96}{= \frac{98!}{(98-11)!}} \cssId{s97}{= \frac{98!}{87!}} \cr\cr &\quad \cssId{s98}{= {\textstyle\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 &\quad \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!

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 alternative notation for $\,{}_nC_k\,$ is $\,\displaystyle\binom{n}{k}\,.$