EF Permutations of subsets

🔗

Section 21.4 Permutations of subsets

🔗

Sometimes we want to create an ordered list of a certain length from a larger pool of candidates.

permutation of size $k$: 🔗
an ordered list of $k$ elements from a given set $A,$ with $| A | \geq k$
$P (n, k)$: 🔗
the number of permutations of size $k$ taken from a set of size $n$
$P_{k}^{n},$ ${_{n} P}_{k}$: 🔗
alternative notation choices for $P (n, k)$

🔗

Example 21.4.1. Visualizing $P (4, 2)$ .

🔗

Consider

A = {1, 2, 3, 4},

so that

n = | A | = 4 .

There are

4! = 24

permutations of

A .

$x$	$1$	$2$	$3$	$4$
${id}_{A} (x)$	$1$	$2$	$3$	$4$
$p_{1} (x)$	$1$	$2$	$4$	$3$
$p_{2} (x)$	$1$	$3$	$2$	$4$
$p_{3} (x)$	$1$	$3$	$4$	$2$
$p_{4} (x)$	$1$	$4$	$2$	$3$
$p_{5} (x)$	$1$	$4$	$3$	$2$
$p_{6} (x)$	$2$	$1$	$3$	$4$
$p_{7} (x)$	$2$	$1$	$4$	$3$
$p_{8} (x)$	$2$	$3$	$1$	$4$
$p_{9} (x)$	$2$	$3$	$4$	$1$
$p_{10} (x)$	$2$	$4$	$1$	$3$
$p_{11} (x)$	$2$	$4$	$3$	$1$

$x$	$1$	$2$	$3$	$4$
$p_{12} (x)$	$3$	$1$	$2$	$4$
$p_{13} (x)$	$3$	$1$	$4$	$2$
$p_{14} (x)$	$3$	$2$	$1$	$4$
$p_{15} (x)$	$3$	$2$	$4$	$1$
$p_{16} (x)$	$3$	$4$	$1$	$2$
$p_{17} (x)$	$3$	$4$	$2$	$1$
$p_{18} (x)$	$4$	$1$	$2$	$3$
$p_{19} (x)$	$4$	$1$	$3$	$2$
$p_{20} (x)$	$4$	$2$	$1$	$3$
$p_{21} (x)$	$4$	$2$	$3$	$1$
$p_{22} (x)$	$4$	$3$	$1$	$2$
$p_{23} (x)$	$4$	$3$	$2$	$1$

Figure 21.4.2. Permutations of a set of size

4 .

🔗

Notice that the permutations above have been grouped into pairs, where the two permutations in a given pair have the same two first elements in the same order. From this, we can conclude that there are only

24 / 2 = 12

permutations of size

k = 2

from

A .

🔗

Theorem 21.4.3. Computing $P (n, k)$ .

🔗

We have

P (n, k) = \frac{n!}{(n - k)!} = n (n - 1) (n - 2) \dots (n - k + 1) .

🔗

Proof.

One way to construct an ordered list of

k

elements from a set

A,

where

| A | = n,

is as in Example 21.4.1. Form an ordered list of all the elements of

A

(

n!

ways), and then take the first

k

elements from that list. But we get the same ordered list of length

k

no matter how the last

n - k

elements are ordered. That is, we consider any two orderings of all

n

elements to be equivalent if the first

k

elements in the list are the same between the two. As there are

(n - k)!

different ways the last

n - k

elements could be ordered while keeping the first

k

elements the same, each equivalence class has size

(n - k)! .

Applying the Division Rule, we obtain the desired formula

P (n, k) = \frac{# {orderings of all n elements}}{# {reorderings of the last n - k elements}} = \frac{n!}{(n - k)!} .

🔗

Remark 21.4.4.

🔗

The number

P (n, n)

represents the number of ways to construct an ordered list of

n

elements chosen from a set of

n

elements, so

P (n, n) = n! .

The convention

0! = 1

ensures that our formula for

P (n, k)

expressed in Theorem 21.4.3 remains valid in the case

k = n .

🔗

Worked Example 21.4.5. Elections.

🔗

A class of twenty discrete mathematics students decides to elect a class president and vice-president. How many possible outcomes to the election process are there?

Solution.

An arbitrary way to elect students to these offices would be to line all the students up and choose the first two students in line to be the president and vice-president, respectively. Therefore, there are

P (20, 2) = \frac{20!}{(20 - 2)!} = 20 \cdot 19 = 380

possible outcomes to the election.

🔗

Worked Example 21.4.6. Ranking choices.

🔗

You go to the horsetrack to bet on a race. From a field of nine horses, how many ways are there to make a “Trifecta” bet (i.e. specify the first three finishers in order)?

Solution.

There are

P (9, 3) = \frac{9!}{(9 - 3)!} = 9 \cdot 8 \cdot 7 = 504

possible such bets.

🔗

Worked Example 21.4.7. Words with no repeated letters.

🔗

For alphabet

Σ = {a, b, c, \dots, y, z},

how many four-letter words made up of distinct letters are there in

Σ^{*} ?

Solution.

A four-letter word with no repeated letters is the same as a permutation of size

4,

so the number of such words is

P (26, 4) = \frac{26!}{(26 - 4)!} = 26 \cdot 25 \cdot 24 \cdot 23 = 358, 800 .

🔗

Worked Example 21.4.8.

🔗

| A | = k

and

| B | = n,

with

k \leq n,

how many injective functions

f : A \to B

exist?

Solution.

Fix an ordering

a_{1}, a_{2}, \dots, a_{k}

of the elements of

A .

Then from any ordering

b_{1}, b_{2}, \dots, b_{k}

of size

k

from

B,

we get an injective function

f : A ↪ B

by the following table of values.

$x$	$a_{1}$	$a_{2}$	$\dots$	$a_{k}$
$f (x)$	$b_{1}$	$b_{2}$	$\dots$	$b_{k}$

That is, every permutation of

B

of size

k

corresponds to an injection

f : A ↪ B,

and so the number of such injections is

P (n, k) .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 21.4 Permutations of subsets

Example 21.4.1. Visualizing $P (4, 2)$ .

Theorem 21.4.3. Computing $P (n, k)$ .

Proof.

Remark 21.4.4.

Worked Example 21.4.5. Elections.

Worked Example 21.4.6. Ranking choices.

Worked Example 21.4.7. Words with no repeated letters.

Worked Example 21.4.8.

Section 21.4 Permutations of subsets

Example 21.4.1. Visualizing P(4,2).

Theorem 21.4.3. Computing P(n,k).

Proof.

Remark 21.4.4.

Worked Example 21.4.5. Elections.

Worked Example 21.4.6. Ranking choices.

Worked Example 21.4.7. Words with no repeated letters.

Worked Example 21.4.8.

Example 21.4.1. Visualizing $P (4, 2)$ .

Theorem 21.4.3. Computing $P (n, k)$ .