Why Count Outcomes?
Finite probability models often describe experiments whose outcomes are sequences, arrangements, or selections. A direct list may work when there are only a few possibilities, but it quickly becomes impractical as the number of stages or objects grows. Counting rules let us determine the size of a sample space, or of an event within it, without writing every outcome down.
The key decision is structural: does the experiment distinguish different orders, and can an object be selected more than once? A password is usually an ordered sequence, while a committee is an unordered group. These are different sample spaces, so they require different counts. Counting itself does not assign probabilities; it supplies the sizes needed for probability calculations under an appropriate model.
The Multiplication Principle
This is a rule for counting, not an assumption of probabilistic independence. For example, when selecting distinct objects without replacement, the number of choices decreases from stage to stage. The multiplication principle still applies because the number of choices at each stage is fixed across all valid histories of that length.
Proof. For one set, the number of one-entry tuples is \(|A_1|\). Suppose the result holds for \(k-1\) sets. There are \(|A_1|\cdots|A_{k-1}|\) possible prefixes \((a_1,\ldots,a_{k-1})\). Each prefix can be extended in exactly \(|A_k|\) ways, one for each choice of \(a_k\in A_k\). Thus the number of full tuples is \((|A_1|\cdots|A_{k-1}|)|A_k|=|A_1|\cdots|A_k|\). Induction proves the result for every positive integer \(k\). \(\square\)
Worked Example: Counting Fixed-Length Codes
A code consists of four digits, each chosen from \(0,1,\ldots,9\). Digits may repeat, and a code may begin with zero. How many codes are possible?
There are 10 choices for the first digit. After any first digit, there are still 10 choices for the second; the same is true at the third and fourth stages. The multiplication principle gives
The count treats \(0047\) as a valid four-digit code, distinct from \(47\). If the question instead concerned four-digit numbers, the first digit could not be zero; there would then be \(9\cdot10^3=9{,}000\) possibilities. The sample-space definition determines which count is appropriate.
Ordered Selections and Permutations
An ordered selection records which object was chosen at each position. Suppose \(r\) objects are selected in order from \(n\) distinct objects, with no object selected twice. There are \(n\) choices for the first position, \(n-1\) for the second, and so on, ending with \(n-r+1\) choices for the \(r\)th position.
Indeed, the stage-by-stage count is \(n(n-1)\cdots(n-r+1)\), and multiplying and dividing by \((n-r)!\) expresses this product as \(n!/(n-r)!\). When \(r=0\), there is one empty selection, consistent with \(P(n,0)=n!/n!=1\).
Worked Example: Assigning Distinct Roles
Eight researchers are eligible for two distinct roles, chair and recorder. One person must fill each role, and no one may fill both. How many assignments are possible?
There are 8 choices for chair. For each chair assignment, 7 researchers remain available for recorder. Because the roles are distinct, swapping the people changes the assignment. Therefore,
For a check, each of the eight possible chairs occurs in exactly seven assignments, giving \(8\cdot7=56\) in total.
Unordered Selections and Combinations
An unordered selection records which objects were chosen, but not their order. A group of three people, for example, is the same group regardless of the order in which its members are named. Counting every ordering would count that group repeatedly.
Why the formula works. First count ordered selections of \(r\) distinct objects: there are \(P(n,r)=n!/(n-r)!\). Each unordered group of \(r\) objects appears exactly \(r!\) times in this count, once for each ordering of its \(r\) distinct members. These orderings are all different, and every ordering of those members represents the same group. Dividing the ordered count by \(r!\) therefore gives the number of groups:
This argument requires distinct objects and selection without replacement. It also shows why the unordered count is generally smaller than the ordered count: each selected group has \(r!\) orderings.
Worked Example: Selecting a Committee
A laboratory has 10 distinct specimens and will select 3 of them for a review. The order of selection does not matter. How many possible selections are there?
The count is a combination, not a permutation:
As a verification, the ordered selections number \(10\cdot9\cdot8=720\). Each group of three specimens appears in \(3!=6\) orders, so \(720/6=120\) distinct groups.
Choosing the Count That Matches the Model
Before using a formula, describe one outcome precisely. Then check whether changing the order creates a new outcome, whether repeated choices are allowed, and whether the objects are distinct. These choices define the sample space; they are not details to decide after counting.
| Experiment structure | Does order matter? | Can an object repeat? | Count |
|---|---|---|---|
| Choose an \(r\)-digit code from \(n\) symbols | Yes | Yes | \(n^r\) |
| Select \(r\) distinct objects in sequence from \(n\) | Yes | No | \(P(n,r)=n!/(n-r)!\) |
| Select a group of \(r\) distinct objects from \(n\) | No | No | \(\binom{n}{r}=n!/[r!(n-r)!]\) |
The first row is another application of the multiplication principle: each of the \(r\) positions has \(n\) choices. It is different from selecting \(r\) distinct objects in sequence, where earlier choices are unavailable later. If choices are constrained in some other way, such as a rule forbidding certain pairs, the displayed formula may not apply; count the valid choices by stages or divide the possibilities into cases that can be counted separately.
Worked Example: Uniformly Choosing an Unordered Pair
A device selects two distinct digits from \(\{0,1,2,3,4,5\}\), with every unordered pair equally likely. What is the probability that the two digits have the same parity?
There are \(\binom{6}{2}=15\) unordered pairs in the sample space. The even digits are \(\{0,2,4\}\), and the odd digits are \(\{1,3,5\}\). A pair has the same parity exactly when both digits are even or both are odd. There are
such pairs. Since the model assigns equal probability to all 15 outcomes, the desired probability is
This calculation uses uniformity as well as counting. If the pairs did not have equal probabilities, the ratio of counts would not, by itself, give the event probability.
Common Pitfall: Counting Order Twice
A common error is to use \(P(n,r)\) for a group when the order of selection does not matter. For instance, \(10\cdot9\cdot8=720\) is the number of ordered ways to select three specimens from 10, not the number of three-specimen groups. Each group is counted \(3!=6\) times, so the correct count is \(720/6=120\).
The reverse error is also possible: using \(\binom{n}{r}\) when positions or roles are distinct. Choosing a chair and a recorder is not merely choosing a two-person group; the assignment with A as chair and B as recorder differs from the assignment with B as chair and A as recorder. A useful check is to write two outcomes that differ only by swapping the chosen objects. If that swap changes the outcome, order matters.
Check Your Understanding
For each situation, identify whether the outcomes are ordered or unordered and find the requested count.
- A six-character code uses letters A through Z, allows repetition, and may begin with any letter. How many codes are possible?
- How many ways can gold, silver, and bronze be awarded to three different people from a group of 12?
- How many distinct four-person committees can be chosen from 12 people?
- Explain why counting ordered selections and dividing by \(r!\) gives the number of unordered groups of size \(r\), when the objects are distinct.
- There are 8 equally likely unordered pairs formed from a particular set of objects, and 3 pairs have a specified property. What additional model condition makes the probability of that property \(3/8\)?