Why Removing Order Requires Division
Suppose a group of people is selected for a committee, and the committee has no chair or assigned roles. A list naming the same people in a different order does not describe a different committee. Counting ordered lists would therefore count each committee multiple times. To count the committees, we can first count the ordered lists and then remove the repeated counts.
The key question is how many times each unordered selection appears in the ordered count. If a selection contains \(r\) distinct objects, it can be arranged in \(r!\) different orders. This number is the same for every selection of size \(r\), so dividing the total number of ordered selections by \(r!\) gives the number of unordered selections.
Throughout the derivation, assume that \(n\) and \(r\) are integers with \(0 \leq r \leq n\), and that the \(n\) objects are distinct. Objects are not repeated within a selection. These conditions ensure that every selection has exactly \(r\) objects and that the same number of orders corresponds to each selection.
From Ordered Selections to the Formula
First count the ordered selections. For the first position, any of the \(n\) objects can be chosen. For the second position, \(n-1\) remain, because the first object cannot be selected again. The available choices continue to decrease by one at each position. Thus, the number of ordered selections is
Using the factorial notation established earlier in the course, this product can be written as \(n!/(n-r)!\). The numerator \(n!\) contains the factors \(n(n-1)\cdots(n-r+1)\), followed by \((n-r)!\); dividing by \((n-r)!\) cancels those final factors. The ordered count is therefore
Now group these ordered sequences according to which \(r\) objects they contain. For any one fixed group of \(r\) distinct objects, the number of possible orders is \(r!\): there are \(r\) choices for the first position, \(r-1\) for the second, and so on. Consequently, each unordered selection appears \(r!\) times in the ordered count. Dividing the ordered count by \(r!\) leaves one count for each unordered selection.
There are \(n!/(n-r)!\) ways to choose and arrange \(r\) distinct objects from \(n\).
Each fixed group of \(r\) objects has \(r!\) different orders.
Divide the ordered total by \(r!\) to obtain \(n!/[r!(n-r)!]\) unordered selections.
Why the Division Works
The division is justified because the ordered sequences can be separated into groups: each group contains exactly the sequences made from one particular set of \(r\) objects. For example, if the objects are A, B, and C, the sequences ABC, ACB, BAC, BCA, CAB, and CBA all belong to the same group because they contain the same three objects. That group has \(3!=6\) sequences.
More generally, every group has \(r!\) sequences, regardless of which objects were selected. The ordered sequences are therefore divided into equal-sized groups of \(r!\). The number of groups is the total number of ordered sequences divided by the size of each group:
This argument depends on the objects being distinct and on order being irrelevant to the selection being counted. If the task assigns different roles, such as president and secretary, switching two people between the roles creates a different outcome. In that situation, removing order would not match the question.
Worked Examples
Worked Example: Selecting a Committee
Imagine that a fictional student group has 8 distinct volunteers and wants a committee of 5 with no separate roles. How many different committees are possible?
A committee is an unordered selection: listing the same five volunteers in another order does not create a new committee. First count ordered selections. There are 8 choices for the first position, then 7, 6, 5, and 4 choices for the remaining positions:
Each committee of 5 distinct volunteers can be listed in \(5!=120\) orders. Thus each committee is counted 120 times in the ordered total. Dividing gives
Equivalently, the combination formula gives
There are 56 possible committees. The calculation counts the groups of five, not different arrangements of the same five volunteers.
Worked Example: Choosing Two Labels
Suppose a fictional display has 7 distinct labels available, and two are chosen to appear without assigned positions. How many pairs of labels can be chosen?
If the two positions were temporarily treated as first and second, there would be \(7\) choices for the first label and \(6\) for the second, for \(7\cdot6=42\) ordered selections. Each unordered pair can be listed in \(2!=2\) orders. Therefore,
Checking by the factorial form,
So there are 21 distinct pairs. For instance, choosing labels A and B is the same pair as choosing B and A; the two orders are not separate outcomes for this task.
Worked Example: Selecting No Objects
A fictional set contains 6 distinct objects. How many ways are there to select none of them?
There is exactly one such selection: the empty selection. There is also one ordered sequence of length zero, the empty sequence. The general formula agrees, using \(0!=1\):
This boundary case fits the same counting logic: the empty selection has \(0!=1\) order, so the ordered count is divided by one. The other boundary case also works. Selecting all \(n\) objects gives just one group, since there is only one way to include every object:
Common Mistake: Dividing by the Wrong Number of Orders
A frequent error is to divide by \(n!\), the number of ways to arrange all \(n\) objects. But the repeated orders are only the orders of the \(r\) selected objects. The unselected \(n-r\) objects do not appear in an ordered selection of size \(r\), so they do not contribute to the number of repeated listings.
For example, when selecting 5 of 8 volunteers, each committee is counted \(5!\) times, not \(8!\) times. The ordered count is \(8!/3!\), so the correct division is
Dividing by \(8!\) would incorrectly treat arrangements of all eight volunteers as repetitions of the same committee. The reliable question is: How many orders can the selected objects themselves take? For a selection of \(r\) distinct objects, the answer is \(r!\).
Why This Derivation Matters
The formula is not a separate counting rule to memorize without explanation. It follows from two counts of the same basic process: counting ordered selections directly, and grouping those sequences by the unordered selection they represent. The factor \(r!\) is the precise correction for counting each group repeatedly.
This also provides a useful check when deciding whether the formula fits a problem. If the outcome changes when the selected objects switch order, the outcomes are ordered and the division by \(r!\) is not appropriate. If order makes no difference, and the selection consists of \(r\) distinct objects from \(n\) distinct objects, the derivation applies. The formula therefore depends on the structure of the outcomes, not just on the numbers \(n\) and \(r\).
Check Your Understanding
Answer each question by referring to the counting argument, not only by quoting the formula.
- In a selection of \(r\) distinct objects, why does each unordered selection correspond to \(r!\) ordered selections?
- A fictional club selects 3 of 6 members for a group with no assigned roles. Write the ordered count, identify the number of repeated orders, and set up the combination calculation.
- Why would dividing the ordered count by \(n!\) generally be incorrect when selecting \(r\) objects from \(n\)?
- Use the combination formula to verify that \(\binom{5}{5}=1\). Explain what the single selection represents.
- A task assigns one selected person as chair and another as secretary. Explain why treating the two people as an unordered selection would not count the task's outcomes correctly.