Counting Ordered Selections Using Permutations

Hello! Last time, you used the multiplication principle to count outcomes assembled in stages. This lesson applies the same principle when each choice uses up an object: there are fewer options for the next position, but the number of options still depends only on how many positions have been filled.

We’ll count ordered selections of $r$ distinct objects from $n$, derive the permutation formula rather than memorize it, and check when it applies. This is a foundation for later probability calculations, where defining the outcomes correctly is as important as doing the arithmetic. Allow about 35–40 minutes, including the short video and reading.

An outcome is an ordered list

Imagine three distinct objects, $A$, $B$, and $C$, placed in three numbered positions. The arrangement $ABC$ differs from $ACB$: the same objects appear, but the second and third positions have different occupants. Each complete ordered list is a permutation.

The tree has three first-position branches. Within each branch there are two choices for the second position, followed by one forced final choice. Thus the number of complete arrangements is $3\cdot 2\cdot 1=6$. The available objects depend on the earlier choices, but the number available at each position is always the same. That is precisely the condition under which the multiplication principle works.

If you have five objects but only three numbered positions, you stop after filling the third position. There are five choices, then four, then three, for $5\cdot 4\cdot 3=60$ lists. You do not arrange the two unused objects: their order is not recorded in the outcome.

Watch Khan Academy’s Permutation formula for a visual derivation using five people and three seats. Concentrate on why the product stops after three factors, then on how the factorial notation represents that same product.

Deriving the general count

Suppose there are $n$ distinct objects and $r$ positions, with no object permitted in more than one position. Assume $0\le r\le n$. The first position has $n$ choices. Once it is filled, the second has $n-1$. By the time you reach position $r$, you have used $r-1$ objects, leaving $n-r+1$ choices.

Every valid partial list has the stated number of continuations, so multiplication gives a product of exactly $r$ factors:

The last factor is worth checking. For $n=8$ and $r=3$, it is $8-3+1=6$, giving $8\cdot 7\cdot 6$—not a product continuing down to $1$.

We can write the same count with factorials. For a nonnegative integer $n$, $n!$ is the product of the positive integers from $n$ down to $1$, and $0!=1$. Since

cancelling the unused tail gives

This is often written ${}_n{P}_r$, read “$n$ permute $r$.” The product form usually makes the counting logic clearer; the factorial form is compact.

There is also a direct counting explanation for the division. Take one ordered list of $r$ selected objects. It can be extended to a full ordering of all $n$ objects by arranging the $n-r$ unused objects in $(n-r)!$ ways. Every full ordering belongs to exactly one such initial $r$-object list. Therefore the $n!$ full orderings comprise groups of $(n-r)!$ extensions of each list, leaving $n!/(n-r)!$ distinct lists.

The boundary cases fit the reasoning. If $r=n$, all objects are arranged, so $P(n,n)=n!$. If $r=0$, there is exactly one ordered selection—the empty list—and $P(n,0)=n!/n!=1$. If $r>n$, filling the positions without reuse is impossible; the factorial formula above is not defined for that case.

For a concise formal account, read the indicated parts of MIT’s Counting and Sets. The examples and notation reinforce the derivation without requiring you to list every possible order.

Deciding whether a problem calls for permutations

Suppose eight distinct candidates can fill three different roles: lead, deputy, and reviewer. A complete outcome specifies who fills each role. Assigning the same three people to different roles changes the outcome, and nobody fills two roles. There are

assignments. Notice that this count is not $8!$: the five people without roles are not placed in any order.

Before using $P(n,r)$, check what a complete outcome records:

• Order or position matters. Swapping two selected objects produces a different outcome.
• The selected objects are distinct, with no reuse. Each selection reduces the available count by one.
• Every remaining object is eligible for the next position. If an extra restriction prevents some assignments, count the eligible choices for that position directly rather than applying the formula without adjustment.

For example, if a particular candidate must be the lead, the first role has one choice; the other two have seven and six. The count is $1\cdot 7\cdot 6=42$, not $P(8,3)$. Permutations are a convenient form of the multiplication principle, not a replacement for checking its conditions.

The word selection can conceal the first condition. If a result records “lead $A$, deputy $B$,” reversing those assignments changes it. If it records only “$A$ and $B$ were selected,” reversing them does not. Today’s formula counts the former kind of outcome; we will count unordered selections later.

Key takeaways

For $r$ ordered positions filled from $n$ distinct objects without reuse, count the choices position by position: $n$, then $n-1$, continuing for $r$ factors. This gives $P(n,r)=n!/(n-r)!$. The factorial denominator removes the unrecorded orderings of objects left unused—not the order of the selected objects.

Next, we’ll keep the positions ordered but permit repetition. The crucial change will be whether making one choice reduces the number available for the next.