Permutations: ordered selection

In the previous section we discussed choosing where the order of selection does not matter. However, there are situations where the order of selection does matter.

For example, instead of just choosing two letters out of $A, B$ and $C,$ we want to form codewords. For our example, that will be $A B, B A, A C, C A, B C, C B .$

These can be done by combining combinations and factorials with the multiplication principle. Using that for our example gives us $(\binom{3}{2}) \times 2! = 6.$

Technique: ordered selection

For an ordered selection of $r$ out of $n$ distinct objects, we have $(\binom{n}{r}) \times r!$ ways.

This is also denoted by $^{n} P_{r} .$

We now revisit an earlier example, where using ordered selection simplifies our working.

Example: forming a number by rearranging

Question

How many ways are there to form a five-digit number satisfying the following conditions using only the numbers from 1,2,3,4,5,6,7. Repetitions are not allowed.

No restrictions.
The number must be greater than 30,000.
The number must be odd.
The number must be greater than 30,000 and odd.

Solution

Step 1: choose 5 digits to be used.
Step 2: rearrange the 5 digits.

$= (\binom{7}{5}) \times 5! = 2,520 ∎$

Step 1: there are 5 ways to fill the first digit (3,4,5,6,7).
Step 2: choose and rearrange for the remaining 4 digits.

Required number of ways $= 5 \times (\binom{6}{4}) \times 4! = 1,800 ∎$

Step 1: there are 4 ways to fill the last digit (1,3,5,7).
Step 2: choose and rearrange for the remaining 4 digits.

Required number of ways $= 4 \times (\binom{6}{4}) \times 4! = 1,440 ∎$

Case 1: Start with an odd number (3,5 or 7).
We then have 3 ways to fill in the last digit.
Number of ways $= 3 \times 3 \times (\binom{5}{3}) \times 3! = 540.$

Case 2: Start with an even number (4 or 6).
We then have 4 ways to fill in the last digit.
Number of ways $= 2 \times 4 \times (\binom{5}{3}) \times 3! = 480.$

Required number of ways $= 540 + 480 = 1,020 ∎$