## 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*) I don't like this new tutorial. Take me back to the old version of this tutorial!

### #[Resources][Recursos]#

**%%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.

**$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.

**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$

$\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)$
\\ $\qquad = C(7,2) = 21 \qquad$

$\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*.
Last Updated:

Copyright © 2023 Stefan Waner and Steven R. Costenoble

*August 2023*Copyright © 2023 Stefan Waner and Steven R. Costenoble