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:

(Recall that $\,5! := 5\cdot 4\cdot 3\cdot 2\cdot 1\,$; this is factorial notation.)

Generalizing this example, we see that:

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.)

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:

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:

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:

or

or

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:

which brings you right back to the first formula again!