Tutorial: Permutations and combinations

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

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.