A permutation^{1}^{2}^{3}^{4} is a set of elements is every possible ordered arrangement of those elements.

The cardinality of a permutation

The number of permutations in a set of n elements is n factorial, n!

Example 1

Given a set of three chairs placed in a row for Bob, Alice, and Cid, how many permutations are there?

Using the Rule of Product, there are three ways to choose the first chair. With the two people left over, there are two ways to choose the second chair. There is one person left for the third chair. The total number of permutations is 3 · 2 · 1, or 6. Or, using just applying n! mentioned above, 3! or 6.

Enumerated permutations, A for Alice, B for Bob, and C for Cid:

ABC

ACB

BAC

BCA

CAB

CBA

Example 2

How many permutations of the letters ABCDEF contain the substring BCD?

Here we have six letters, but we are constrained by the substring BCD. This leaves us with A, E, and F.

Therefore the total set has four elements: A, BCD, E, and F.

The answer is 4!, or 24.

Now, what if we want the permutations of a set of n elements, where the number of selected elements is less-than the total size of the set. These are called r-permutations^{2}^{3}^{4}, or sometimes k-permutations^{1}.

The cardinality of r-permutations

The ordered selection of r elements taken from a set of n elements is called an r-permutation. The notation for a number of r-permutations taken from a set of of n elements is **P( n, r )**. This is computed by

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

Example 3

What is the 2-permutation from the set of letters {a, b, c} ?

P(3, 2) = \frac{3!}{(3 -2)!} = \frac{3!}{1!} = \frac{3 \cdot 2 \cdot 1}{1} = 6

Enumerated permutations as proof:

ab

ac

ba

bc

ca

cb

Example 4

A swimming contest has 8 participants and will award a gold, silver, and bronze medal to the three winners. How many ways are there to award the swimmers?

P(8, 3) = \frac{8!}{(8 -3)!} = \frac{8!}{5!} = \frac{8 \cdot 7 \cdot 6 \cdot \cancel{5!}}{\cancel{5!}} = 336

*Wikipedia, The Free Encyclopedia*. Retrieved from https://en.wikipedia.org/w/index.php?title=Permutation&oldid=1073657907

*Discrete mathematics and its applications*(4th ed., pp.250). WCB/McGraw-Hill. ISBN 0-07-289905-0.

*Discrete mathematics with applications*.(5th ed., pp.580-582). Cengage. ISBN 978-1-337-69419-3.

*Discrete mathematics*. (8th ed., pp.269-271). Pearson. ISBN-13 978-0321964687.