Tutorial: Permutations and combinations

Adaptive game version

(This topic is also in Section 6.4 in Finite Mathematics or Section 7.4 in Finite Mathematics and Applied Calculus)

What is an adaptive game tutorial? ▶

I don't like this new tutorial. Take me back to the old version of this tutorial!

#[Resources][Recursos]#

Pop-up factorials, permutations and combinations calculator

%%Note Several concepts in this tutorial are based on decision algorithms, so you might want to go to the %%prevsectut to review those concepts.

Permutations

Let's start with a warmup based on the %%prevsectut:

We call an ordered list of items (such as those we are arranging in order in the warmup) a permutation of those items.

%%Q In general if we have $n$ items, how many permutations of those items are possible?
%%A We can use a decision algorithm similar to the one we used above to make a permutation:

Step 1: Select the first item; $n$ choices.
Step 2: Select the second item; $n - 1$ choices.
Step 3: Select the third item; $n - 2$ choices.
...
Step $n - 1$: Select the next-to-last item; 2 choices.
Step $n$: Select the last item; 1 choice.

Thus, by the multiplication principle, there are $n \times (n - 1) \times (n - 2) \times ... \times 2 \times 1$ possible permutations. We call this number $n$ factorial, which we write as $n!$.

Permutations of n items
A permutation of $n$ items is an ordered list of all of those items. The number of possible permutations of $n$ items is given by $n$ factorial, given by

$n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$

for $n$ a positive integer. We also take, by convention

$0! = 1.$

%%Examples

1. $\ 1!$ \t ${}= 1$ \\ $2!$ \t ${}= 2 \times 1 = 2$ \\ $3!$ \t ${}= 3 \times 2 \times 1 = 6$ \\ $10!$ \t ${}= 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$ \\ \t ${}= 3,628,800$

2. #[The number ways of ordering the digits 1, 2, 3 is $3! = 3 \times 2 \times 1 = 6.$ \t Here are the 6 orderings:][El número de ordenamientos de los dígitos 1, 2, 3 son $3! = 3 \times 2 \times 1 = 6.$ \t Aquí están los 6 ordenamientos:]#

\\ $123,132,213,231,312,321$

#[Some for you][Algunas para ti]#

%%Q What if we want to make an ordered list of only some of the items (as in the warmup quiz above)?
%%A We can use the following decision algorthm to make a permutation using only $r$ of the $n$ items available:

Step 1: Select the first item; $n$ choices.
Step 2: Select the second item; $n - 1$ choices.
Step 3: Select the third item; $n - 2$ choices.
...
Step $r$: Select the $r$th item; $n - r + 1$ choices.

Thus, by the multiplication principle, there are $n \times (n - 1) \times (n - 2) \times ... \times (n-r+1)$ possible permutations using $r$ of the $n$ items.

Permutations of n items taken r at a time
A permutation of $n$ items taken $r$ at a time is an ordered list of $r$ items chosen from a set of $n$ items. The number of permutations of $n$ items taken $r$ at a time is given by

$P(n, r) = n \times (n - 1) \times (n - 2) \times ... \times (n - r + 1)$ \t #[Product of $r$ terms starting with $n$][Producto de $r$ términos que comienzan con $n$]#

Here is an alternative formula that is often used to calculate the same quantity:

$P(n, r) = \dfrac{n!}{(n - r)!}$

%%Examples

1. $P(4, 2) = 4 \times 3 = 12$

\t #[Product of 2 terms starting with 4][Producto de 2 términos comenzando con 4]# \\

$\quad P(10, 3) = 10 \times 9 \times 8 = 720$

\t #[Product of 3 terms starting with 10][Producto de 3 términos comenzando con 10]# \\

$\quad P(12, 1) = 12$

\t #[Product of 1 term starting with 12][Producto de 1 término comenzando con 12]# \\

$\quad P(5, 5) = 5 \times 4 \times 3 \times 2 \times 1 = 5!$

\t #[Product of 5 terms starting with 5][Producto de 5 términos comenzando con 5]#

2. #[The number of possible sequences of three of the digits 1, 2, 3, ..., 9 is $P(9,3) = 9 \times 8 \times 7 = 504$

This is the number of three-digit sequences that exclude 0.

][El número de secuencias posibles de tres de los dígitos 1, 2, 3, ..., 9 es $P(9,3) = 9 \times 8 \times 7 = 504$ \t Este es el número de secuenciass de tres dígitos que excluyen 0.]#

#[Some for you][Algunas para ti]#

Combinations

%%Q What if order is not important? For instance, if I choose a group of 3 of my 5 friends to accompany me to the movies, the order in which I choose them is not important. So, the number of possible outcomes cannot be $P(5,3)$ because that would be the number of ordered lists of 3 friends. What, then is the correct number?
%%A To see the correct answer, think about why $P(5, 3)$ is the wrong answer: The same three friends will occur on many different lists—in fact, on 3! = 6 lists (the number of ways of arranging the 3 friends). Thus, the reason $P(5,3)$ is wrong is that it is 6 times too big, so the correct answer should be 1/6 of that.

$\dfrac{P(5, 3)}{3!} = \dfrac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10.$

Combinations of n items taken r at a time
A combination of $n$ items taken $r$ at a time is an unordered collection, or set of $r$ items chosen from $n$ items. The number of combinations of $n$ items taken $r$ at a time is given by

$C(n, r) = \dfrac{n \times (n - 1) \times ... \times (n - r + 1)}{r \times (r - 1) \times ... \times 1} = \dfrac{P(n,r)}{r!} \quad$ \t #[Compare with the formula for $P(n, r)$ above][Compara con la fórmula para $P(n, r)$ anterior]#

The alternative formula for $P(n,r)$ we saw above gives us the following alternative formula for $C(n,r):$

$C(n, r) = \dfrac{n!}{r!(n - r)!}$

%%Examples

$\quad C(4, 2) = \dfrac{4 \times 3}{2 \times 1} = 6$

\t 2 terms in both the numerator and denominator \\

$\quad C(10, 3) = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

\t 3 terms in both the numerator and denominator \\

$\quad C(12, 1) = \dfrac{12}{1} = 12$

\t 1 term in both the numerator and denominator \\

$\quad C(5, 5) = \dfrac{5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = 1!$

\t In general, $C(n,n) = 1$ \\

$\quad C(7, 5) = \dfrac{7 \times 6 \times {} \color{red}{5 \times 4 \times 3}}{\color{red}{5 \times 4 \times 3} \times 2 \times 1} = \dfrac{7 \times 6}{2 \times 1}$
$\qquad = C(7,2) = 21 \qquad$

\t In general, $C(n,r) = C(n,n-r)$ \\

$\quad C(10, 7) = C(10,3) = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

\t See preceding comment. \\

$\quad C(10, 0) = C(10,10) = 1$

\t In general, $C(n,0) = 1$

#[Some for you][Algunas para ti]#

Now try some of the exercises in Section 6.4 in Finite Mathematics or Section 7.4 in Finite Mathematics and Applied Calculus.