Unit 2, lesson 15

Choosing a Counting Method

How to choose between ordered selections, subsets and multisets from what one outcome records, how the multiplicity of a record decides whether erasing order keeps outcomes equally likely, and when to count by complement.

  • Video 15
  • Choosing a Counting Method

Five tools, labeled A through E, lie on a bench, and two selections are to be made. Is the number of possible outcomes 20, 10, 25 or 15? Each of these answers is right for some experiment, and the question cannot be settled until we know what one outcome records, whether order is part of it and whether the same label may be chosen twice. This lesson sorts the counting methods by those questions and shows how to check that the counted outcomes are equally likely before a ratio of counts is used as a probability.

Key terms

Ordered selection

Definition An ordered selection of kk items from nn distinct objects records which object fills each of kk labeled positions, such as first and second or primary and backup. An outcome is a sequence (x1,…,xk)(x_1, \dots, x_k), and two sequences that hold the same objects in different positions are different outcomes. Without replacement, so that no object is used twice, the product rule gives

n(n−1)⋯(n−k+1)=n!(n−k)!\begin{aligned} &n(n-1)\cdots(n-k+1) \\[0.4em] &\quad = \frac{n!}{(n-k)!} \end{aligned}

sequences for 1≤k≤n1 \le k \le n. With replacement, so that an object or label may fill several positions, each position has nn choices and there are nkn^k sequences. A restriction applies only to the positions it names, so a rule that the first and third entries differ leaves the middle entry free. The product rule applies when the number of choices at each position, given the positions already filled, is the same whichever earlier choices were made.

In plain words The positions or roles are part of the outcome, so swapping two different chosen objects produces a new outcome. Without other restrictions, whether repetition is allowed decides whether the number of choices shrinks from one position to the next.

Example Choosing a primary tool and a backup tool from the five distinct tools A to E gives 5⋅4=205 \cdot 4 = 20 ordered selections, and (A, B) differs from (B, A). If instead each of two stations requests one of five tool types and both may request the same type, there are 52=255^2 = 25 ordered requests. That second count describes types, not one physical tool sent to two places at once. For three-letter codes from A, B and C in which only the first and third letters must differ, the positions give 3⋅3⋅2=183 \cdot 3 \cdot 2 = 18 codes, and AAB is allowed. Requiring all three letters to differ gives 3⋅2⋅1=63 \cdot 2 \cdot 1 = 6 codes.

Unordered selection

Definition An unordered selection of kk objects from nn distinct objects without replacement records only which objects are chosen. An outcome is a subset of size kk, and for 0≤k≤n0 \le k \le n the number of such subsets is

(nk)=n!k! (n−k)!.\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.

Each subset of size kk arises from exactly k!k! ordered selections without replacement, one for each order of its members, so dividing the ordered count n!/(n−k)!n!/(n-k)! by k!k! gives the same number.

In plain words Only membership matters. Listing the same objects in another order describes the same outcome, so each subset appears exactly k!k! times among the ordered selections.

Example An unranked two-tool kit from A to E can be chosen in 20/2!=1020/2! = 10 ways, which is (52)\binom{5}{2}. The kit {A, B} is one outcome, and it comes from the two ordered selections (A, B) and (B, A).

Unordered selection with repetition

Definition When labels are chosen with repetition allowed and only the labels chosen and their numbers of copies are recorded, an outcome is a multiset of size kk from the nn labels. Two multisets are the same exactly when every label appears the same number of times in both. For k=2k = 2 an outcome is either a double such as {A, A} or two different labels such as {A, B}, so for n≥1n \ge 1 labels there are

n+(n2)=n(n+1)2n + \binom{n}{2} = \frac{n(n+1)}{2}

multisets of size two. Larger sizes can be counted by cases on the pattern of repeated labels.

In plain words The record lists what was chosen and how many times, with no first or second. It differs from a subset, because a label may appear more than once, and from a sequence, because there is no order.

Example Two labels chosen from A to E with repetition allowed, with the order erased, give 5 doubles and 10 mixed pairs, so there are 5⋅6/2=155 \cdot 6/2 = 15 multisets. A count of records is not yet a probability. The next two cards show why these 15 records are not equally likely when each label is chosen independently and uniformly.

Multiplicity of a record

Definition Let Ω\Omega be a finite sample space, and suppose each outcome ω\omega produces a record r(ω)r(\omega), the part of the outcome that is written down. The multiplicity of a possible record RR is the number of outcomes that produce it,

m(R)=∣{ω∈Ω∣r(ω)=R}∣.\begin{aligned} &m(R) \\[0.4em] &\quad = \bigl\lvert \{\omega \in \Omega \mid r(\omega) = R\} \bigr\rvert. \end{aligned}

The multiplicities of all possible records add up to ∣Ω∣\lvert \Omega \rvert. When the outcomes of Ω\Omega are equally likely, the record RR occurs with probability

P(record R)=m(R)∣Ω∣.P(\text{record } R) = \frac{m(R)}{\lvert \Omega \rvert}.

In plain words Multiplicity says how many detailed outcomes collapse onto one record. Dividing the detailed count by a number mm counts the records correctly when every record hides exactly mm outcomes.

Example Among the 25 ordered pairs of labels from A to E, the record {A, A} comes only from (A, A), so its multiplicity is 1, while {A, B} comes from (A, B) and (B, A) and has multiplicity 2. The total 5⋅1+10⋅2=255 \cdot 1 + 10 \cdot 2 = 25 accounts for every pair. Repeated letters in a row work the same way. Tag the two R’s of RRB as R1\text{R}_1 and R2\text{R}_2. The 3!=63! = 6 arrangements of R1\text{R}_1, R2\text{R}_2 and B collapse onto the visible strings RRB, RBR and BRR, each with multiplicity 2!2! from swapping the tags, so there are 6/2!=36/2! = 3 strings. This division forgets only which R is which, and the positions keep their order. Dividing by 3!3! instead would erase the order of the whole row, as a combination does.

Equal likelihood after erasing order

Definition Suppose the outcomes of a finite sample space Ω\Omega are equally likely and each outcome produces a record. The possible records all have the same probability exactly when they all have the same multiplicity mm. In that case there are ∣Ω∣/m\lvert \Omega \rvert / m possible records, and the probability that the record falls in a set H\mathcal{H} of possible records is the number of records in H\mathcal{H} divided by ∣Ω∣/m\lvert \Omega \rvert / m. In every case

P(record in H)=1∣Ω∣∑R∈Hm(R),\begin{aligned} &P(\text{record in } \mathcal{H}) \\[0.4em] &\quad = \frac{1}{\lvert \Omega \rvert} \sum_{R \in \mathcal{H}} m(R), \end{aligned}

and when the multiplicities differ the ratio of record counts need not equal this probability. Whether the detailed outcomes are equally likely is a property of the selection procedure, not of the way the result is written down.

In plain words When the ordered outcomes are equally likely, erasing order keeps equal likelihood exactly when every record hides the same number of them. Without replacement each unordered pair hides exactly two orders, so the pairs stay equally likely. With replacement a double hides one order and a mixed pair hides two, so the records do not.

Example Choose two labels from A to E independently and uniformly, so the 25 ordered pairs are equally likely. Each double then has probability 1/251/25 and each mixed pair 2/252/25, so

P(double)=5⋅125=15.P(\text{double}) = \frac{5 \cdot 1}{25} = \frac{1}{5}.

Counting 5 favorable records out of 15 would give 1/31/3, which is wrong for this procedure. That ratio would be correct for a different procedure, one that picks one of the 15 records uniformly at random. If instead two tools are drawn at random without replacement, each of the 10 unordered pairs has probability 2/20=1/102/20 = 1/10.

Counting by complement

Definition For an event AA in a finite sample space Ω\Omega,

∣A∣=∣Ω∣−∣Ac∣,\lvert A \rvert = \lvert \Omega \rvert - \lvert A^{c} \rvert,

and when the outcomes of Ω\Omega are equally likely, P(A)=1−∣Ac∣/∣Ω∣P(A) = 1 - \lvert A^{c} \rvert / \lvert \Omega \rvert. Both counts must describe outcomes of the same sample space, ordered in both or unordered in both. The method helps when an event such as “at least one” splits into several cases while its complement is a single simple case.

In plain words Count everything, subtract what you do not want, and keep one outcome definition throughout.

Example A kit of two tools is chosen from two fragile and four sturdy tools, and order is not recorded. Of the (62)=15\binom{6}{2} = 15 kits, (42)=6\binom{4}{2} = 6 contain no fragile tool, so 15−6=915 - 6 = 9 contain at least one. Direct cases agree, with 2⋅4=82 \cdot 4 = 8 kits holding exactly one fragile tool and (22)=1\binom{2}{2} = 1 kit holding both. Subtracting the unordered 6 from the ordered total 6⋅5=306 \cdot 5 = 30 would give 24, which counts neither the ordered nor the unordered selections with a fragile tool. In the ordered space the complement has 4⋅3=124 \cdot 3 = 12 selections, which leaves 30−12=1830 - 12 = 18. When the two tools are drawn at random without replacement, both models give the probability 9/15=18/30=3/59/15 = 18/30 = 3/5.

Check yourself

  1. A code has three positions, each filled with one of the letters A, B, C and D, and adjacent letters must differ. How many codes are there? Is ABA allowed, and is AAB? How many codes use three different letters?
Show the answer

Fill the positions from left to right. The first letter has 4 choices, the second must differ from the first and has 3, and the third must differ only from the second and has 3, whatever the earlier letters were. That gives 4⋅3⋅3=364 \cdot 3 \cdot 3 = 36 codes.

The code ABA is allowed, because the restriction never compares the first and third letters, while AAB is forbidden because its first two letters are adjacent and equal. Requiring three different letters gives 4⋅3⋅2=244 \cdot 3 \cdot 2 = 24 codes. The other 36−24=1236 - 24 = 12 codes have equal first and third letters, such as ABA, and indeed there are 4⋅3=124 \cdot 3 = 12 of those.

  1. Two tools are drawn at random without replacement from two fragile and four sturdy tools. Find the probability that exactly one is fragile by counting unordered kits. Then find it again by counting ordered draws, a first tool and a second tool. Why do the two answers agree?
Show the answer

There are 15 equally likely kits, and a kit with exactly one fragile tool needs one of the 2 fragile tools and one of the 4 sturdy tools, so

P(exactly one fragile)=2⋅4(62)=815.\begin{aligned} &P(\text{exactly one fragile}) \\[0.4em] &\quad = \frac{2 \cdot 4}{\binom{6}{2}} = \frac{8}{15}. \end{aligned}

In the ordered model there are 6⋅5=306 \cdot 5 = 30 equally likely draws. Choose which draw is fragile in 2 ways, the fragile tool in 2 ways and the sturdy tool in 4 ways, which gives 16 favorable draws and

2⋅2⋅46⋅5=1630=815.\frac{2 \cdot 2 \cdot 4}{6 \cdot 5} = \frac{16}{30} = \frac{8}{15}.

The answers agree because every kit corresponds to exactly two ordered draws, so each kit has probability 2/30=1/152/30 = 1/15 in the ordered model too, and the event depends only on which tools are drawn, not on their order.

  1. A machine fills a cup with three scoops, choosing the flavor of each scoop independently and uniformly from vanilla, chocolate and strawberry. A cup is described only by how many scoops of each flavor it holds. How many different cups are possible? What is the probability that the three scoops have three different flavors, and why is the answer not 1/101/10?
Show the answer

Count cups by the pattern of repeats. Three scoops of one flavor give 3 cups, two of one flavor and one of another give 3⋅2=63 \cdot 2 = 6 cups, and three different flavors give 1 cup, so there are 10 cups.

The equally likely outcomes are the 33=273^3 = 27 ordered flavor sequences. The cup with three different flavors comes from 3!=63! = 6 of them, so its probability is 6/27=2/96/27 = 2/9. The answer 1/101/10 treats the 10 cups as equally likely, but their multiplicities differ. A cup of three vanilla scoops comes from 1 sequence, a cup of two vanilla and one chocolate from 3, since the chocolate scoop can be first, second or third, and the cup with one scoop of each flavor from 6. The total 3⋅1+6⋅3+1⋅6=273 \cdot 1 + 6 \cdot 3 + 1 \cdot 6 = 27 confirms the count. The ratio 1/101/10 would be correct for a different machine, one that picks one of the 10 cups uniformly at random.

How this lesson connects