1.5 Counting Techniques

To use the classical definition \(P(E) = \frac {n(E)}{N}\) we must count outcomes. When there are too many to list, we use counting techniques.

1.5.1 The multiplication principle

If one operation can be done in \(n_1\) ways and, for each of these, a second can be done in \(n_2\) ways, then the two together can be done in \(n_1n_2\) ways. More generally, \(k\) successive operations can be done in \(n_1n_2\cdots n_k\) ways.

Example 1.5.1. A die is rolled and then a coin is tossed. How many outcomes are there?

Solution. \(n_1 = 6\) and \(n_2 = 2\), so there are \(6\times 2 = 12\) outcomes, shown in the tree of figure 1.1.

S1H1T12H2T23H3T34H4T45H5T56H6T6TTtHTHTHTHTHTHTooassssrt — Figure 1.1: Tree Diagram for Rolling a Die and Tossing a Coin

Example 1.5.2. How many vehicle number plates are possible if each has three letters followed by two digits?

Solution. \(26^3\times 10^2 = 1\,757\,600\).

1.5.2 Permutations

A permutation is an arrangement of objects in a definite order.

Definition 1.5.3. The number of permutations of \(n\) distinct objects taken \(k\) at a time is \[{}_nP_k = n(n - 1)\cdots (n - k + 1) = \frac {n!}{(n - k)!},\] where \(n! = n(n - 1)\cdots 2\cdot 1\) and \(0! = 1\).

The formula is the multiplication principle: there are \(n\) choices for the first position, \(n - 1\) for the second, and so on down to \(n - k + 1\) for the \(k\)th.

Example 1.5.4. List the arrangements of three of the four letters \(p, q, r, s\).

Solution. \({}_4P_3 = \frac {4!}{1!} = 24\). Each column of table 1.4 holds the \(3! = 6\) orderings of one choice of three letters.

Table 1.4: The \(24\) permutations of three of \(p, q, r, s\).

\(pqr\)	\(pqs\)	\(prs\)	\(qrs\)
\(prq\)	\(psq\)	\(psr\)	\(qsr\)
\(qrp\)	\(qsp\)	\(rsp\)	\(rsq\)
\(qpr\)	\(qps\)	\(rps\)	\(rqs\)
\(rqp\)	\(sqp\)	\(srp\)	\(srq\)
\(rpq\)	\(spq\)	\(spr\)	\(sqr\)

Definition 1.5.5. If \(n\) objects consist of \(k_1\) of one kind, \(k_2\) of a second kind, …, \(k_m\) of an \(m\)th kind, with \(k_1 + \dots + k_m = n\) and objects of the same kind indistinguishable, the number of distinct arrangements is \[\binom {n}{k_1, k_2, \dots , k_m} = \frac {n!}{k_1!\,k_2!\cdots k_m!} .\]

The \(n!\) arrangements of the objects treated as distinct fall into groups of \(k_1!\,k_2!\cdots k_m!\) that look the same, since objects of each kind can be permuted among themselves.

Example 1.5.6.

(a): In how many ways can \(3\) red, \(4\) yellow and \(2\) blue bulbs be arranged in a string of nine sockets?
(b): In how many ways can seven students be assigned to one triple room and two double rooms?

Solution.

(a): \(\frac {9!}{3!\,4!\,2!} = \frac {362\,880}{6\cdot 24\cdot 2} = 1260\).
(b): The students are split into groups of sizes \(3\), \(2\), \(2\) assigned to distinct rooms, so the count is \(\frac {7!}{3!\,2!\,2!} = \frac {5040}{24} = 210\).

1.5.3 Combinations

A combination is a selection in which order does not matter.

Definition 1.5.7. The number of combinations of \(n\) distinct objects taken \(k\) at a time is \[\binom {n}{k} = \frac {n!}{k!\,(n - k)!} .\]

Each combination of \(k\) objects can be ordered in \(k!\) ways, so \({}_nP_k = k!\binom nk\).

Theorem 1.5.8.

(i): \(\binom nk = \binom {n}{n - k}\) for \(k = 0, 1, \dots , n\).
(ii): \(\binom nk = \binom {n - 1}{k} + \binom {n - 1}{k - 1}\) for \(k = 1, \dots , n\) (Pascal’s rule).
(iii): \(\sum _{r=0}^k\binom mr\binom {n}{k - r} = \binom {m + n}{k}\) (Vandermonde’s identity).

Proof. Each identity counts one set in two ways.

(i): Choosing the \(k\) objects to take is the same as choosing the \(n - k\) to leave.
(ii): Fix one object. A \(k\)-subset either omits it, and is one of the \(\binom {n - 1}{k}\) subsets of the other objects, or contains it, together with one of the \(\binom {n - 1}{k - 1}\) choices of the remaining \(k - 1\).
(iii): Choose \(k\) people from \(m\) men and \(n\) women. If \(r\) of them are men, there are \(\binom mr\binom {n}{k - r}\) choices; summing over \(r\) gives all \(\binom {m + n}{k}\).

□

Example 1.5.9. A lot of \(100\) items contains \(5\) defectives. A random sample of \(10\) is drawn without replacement. Find the probability that the sample contains (A) exactly \(2\) defectives, (B) no defectives, (C) at most \(2\) defectives, (D) at least \(2\) defectives.

Solution. Every one of the \(\binom {100}{10}\) samples is equally likely. A sample with exactly \(r\) defectives is formed by choosing \(r\) of the \(5\) defectives and \(10 - r\) of the \(95\) good items (figure 1.5.3), so \[P(r\text { defectives}) = \frac {\binom 5r\binom {95}{10 - r}}{\binom {100}{10}} .\]

(A): \(P(A) = \frac {\binom 52\binom {95}{8}}{\binom {100}{10}} = 0.0702\).
(B): \(P(B) = \frac {\binom {95}{10}}{\binom {100}{10}} = 0.5838\).
(C): With \(P(1) = \frac {5\binom {95}{9}}{\binom {100}{10}} = 0.3394\), \(P(C) = 0.5838 + 0.3394 + 0.0702 = 0.9934\).
(D): \(P(D) = 1 - P(0) - P(1) = 1 - 0.5838 - 0.3394 = 0.0769\).

This is the hypergeometric distribution, studied in chapter 2.

Example 1.5.10. Find the probability that among \(n\) people at least two share a birthday, ignoring leap years and assuming all \(365\) days are equally likely. For which \(n\) does it first exceed \(\frac 12\)?

Solution. The sample space of birthday lists has \(365^n\) equally likely outcomes. The number in which all birthdays differ is \({}_{365}P_n = 365\cdot 364\cdots (365 - n + 1)\). So \[P(\text {some shared birthday}) = 1 - \frac {365\cdot 364\cdots (366 - n)}{365^n} .\] For \(n = 22\) this is \(0.476\) and for \(n = 23\) it is \(0.507\), so \(23\) people suffice. The answer is surprisingly small because there are \(\binom {23}{2} = 253\) pairs of people, each of which might share a birthday.

1.5.4 Practice Problems

Problems on counting. Try each one before opening the solution.

Problem 1.5.1. In how many ways can the letters of the word FACETIOUS be arranged in a line? What is the probability that an arrangement begins with F and ends with S?

Show solution

Solution. The nine letters of FACETIOUS are all different, so the number of arrangements is \[9! = 362\,880.\] If the arrangement must begin with F and end with S, those two positions are fixed and the remaining seven letters may be arranged freely in the seven middle positions, giving \(7!\) arrangements. Hence \[P(\text {begins with F and ends with S}) = \frac {7!}{9!} = \frac {5040}{362\,880} = \frac {1}{72}.\]

Problem 1.5.2. The letters of the word EXCELLENT are arranged in a random order. Find the probability that

(a).: the same letter occurs at each end;
(b).: X, C and N occur together in any order;
(c).: the letters occur in alphabetical order.

Show solution

Solution. EXCELLENT has nine letters, of which E occurs three times and L twice. The number of distinct arrangements is \[\frac {9!}{3!\,2!} = \frac {362\,880}{12} = 30\,240.\]

(a). Only E and L are repeated, so only those can occupy both ends. If both ends are E, the remaining seven letters are E, X, C, L, L, N, T with L twice, giving \(7!/2! = 2520\) arrangements. If both ends are L, the remaining seven are E, E, E, X, C, N, T with E three times, giving \(7!/3! = 840\). Therefore \[P = \frac {2520 + 840}{30\,240} = \frac {3360}{30\,240} = \frac {1}{9}.\]

(b). Treat XCN as a single block. There are then seven units to arrange – the block together with E, E, E, L, L, T – which can be done in \(7!/(3!\,2!) = 420\) ways, and the three letters inside the block can be ordered in \(3! = 6\) ways. Therefore \[P = \frac {420 \times 6}{30\,240} = \frac {2520}{30\,240} = \frac {1}{12}.\]

(c). Alphabetical order is a single arrangement, C E E E L L N T X, so \[P = \frac {1}{30\,240}.\]

Problem 1.5.3. If all the letters of the word BIOLOGY are to be arranged in a line, find the

(a).: number of distinct letter arrangements possible;
(b).: probability that the arrangement starts and ends with the letter O;
(c).: probability that the two O’s are together.

Show solution

Solution. (a). BIOLOGY has seven letters with O repeated twice, so the number of distinct arrangements is \[\frac {7!}{2!} = \frac {5040}{2} = 2520.\]

(b). Both O’s are used at the two ends, and the remaining five distinct letters B, I, L, G, Y fill the middle in \(5! = 120\) ways. \[P = \frac {120}{2520} = \frac {1}{21}.\]

(c). Treat OO as a single block. There are then six units, all different, giving \(6! = 720\) arrangements. (The two O’s are identical, so the block is not counted twice.) \[P = \frac {720}{2520} = \frac {2}{7}.\]

Problem 1.5.4.

(a).: A drug for the relief of asthma can be purchased from five different manufacturers in liquid, tablet or capsule form, all of which come in regular and extra strength. In how many different ways can a doctor prescribe the drug for a patient suffering from asthma?
(b).: A witness to a hit-and-run accident told the police that the licence plate number has letters ABF followed by four digits, the first of which was a six. If the witness cannot recall the last three digits, but is sure that all four digits are different, find the maximum number of vehicle registrations the police have to check.
(c).: A football team plays 10 games during the season. In how many ways can the team end the season with six wins, three losses and one draw?

Show solution

Solution. (a). The three choices – manufacturer, form and strength – are made independently, so by the multiplication principle \[5 \times 3 \times 2 = 30 \text { ways}.\]

(b). The first digit is known to be 6. The remaining three digits must all differ from 6 and from one another, so there are 9 choices for the second, 8 for the third and 7 for the fourth: \[9 \times 8 \times 7 = 504 \text { registrations}.\]

(c). The season is a sequence of 10 results made up of six Ws, three Ls and one D. This is a permutation with repetition: \[P^{10}_{6,3,1} = \frac {10!}{6!\,3!\,1!} = \frac {3\,628\,800}{4320} = 840 \text { ways}.\]

Problem 1.5.5. The integers \(1, 2, 3, \ldots , 9\) are arranged in a row, resulting in a nine-digit number. Find the probability that

(a).: the resulting number is even;
(b).: the resulting number is divisible by 5;
(c).: the digits 4 and 6 are next to each other.

Show solution

Solution. The nine digits are all different, so there are \(9! = 362\,880\) equally likely arrangements.

(a). The number is even exactly when the last digit is one of \(2, 4, 6, 8\). There are 4 choices for that digit and \(8!\) arrangements of the rest: \[P = \frac {4 \times 8!}{9!} = \frac {4}{9}.\]

(b). The number is divisible by 5 exactly when it ends in 5 (there is no 0 among the digits). That fixes one position and leaves \(8!\): \[P = \frac {8!}{9!} = \frac {1}{9}.\]

(c). Treat 4 and 6 as a single block, giving eight units to arrange in \(8!\) ways, and the two digits can be ordered within the block in \(2!\) ways: \[P = \frac {2 \times 8!}{9!} = \frac {2}{9}.\]

Problem 1.5.6. Four women and two men go to a show and sit together in a row. Suppose they sit in a random order.

(a).: List a sample space for the seating arrangement (assume only gender is important).
(b).: Find the probability that there will be \(x\) women between the 2 men, for \(x = 0, 1, 2, 3\) and \(4\).

Show solution

Solution. (a). Since only gender matters, an outcome is an arrangement of the letters WWWWMM. There are \[\frac {6!}{4!\,2!} = 15\] such arrangements, and they are equally likely.

(b). An arrangement is determined by the two positions \(i<j\) holding the men; the women fill the rest. The number of women between them is \(j-i-1\). So \(x\) women sit between the men exactly when \(j-i = x+1\), and the number of such position pairs within six seats is \(6-(x+1) = 5-x\): \[P(x\text { women between the men}) = \frac {5-x}{15}, \qquad x = 0,1,2,3,4.\] Explicitly \(\tfrac {5}{15}=\tfrac 13\), \(\tfrac {4}{15}\), \(\tfrac {3}{15}=\tfrac 15\), \(\tfrac {2}{15}\), \(\tfrac {1}{15}\). As a check these sum to \(\tfrac {15}{15}=1\), as they must, since the men always have some number of women between them.

Problem 1.5.7. Four people are chosen at random from a group of ten people consisting of four men and six women. Three of the women are sisters. Find the probability that the group chosen

(a).: consists of four women;
(b).: consists of two women and two men;
(c).: includes the three sisters;
(d).: has more men than women.

Show solution

Solution. Order does not matter, so there are \(\binom {10}{4} = 210\) equally likely groups.

(a). Choose all four from the six women: \(\binom {6}{4} = 15\), so \[P = \frac {15}{210} = \frac {1}{14}.\]

(b). Choose 2 of the 6 women and 2 of the 4 men: \(\binom {6}{2}\binom {4}{2} = 15\times 6 = 90\), so \[P = \frac {90}{210} = \frac {3}{7}.\]

(c). The three sisters are fixed, and the fourth member is any of the remaining 7 people: \(\binom {7}{1} = 7\), so \[P = \frac {7}{210} = \frac {1}{30}.\]

(d). More men than women, out of four people, means 3 men and 1 woman, or 4 men: \[\binom {4}{3}\binom {6}{1} + \binom {4}{4} = 24 + 1 = 25, \qquad P = \frac {25}{210} = \frac {5}{42}.\]

Problem 1.5.8. Three letters are selected at random from the word BIOLOGY. Find the probability that the selection

(a).: does not contain the letter O;
(b).: contains the two O letters.

Show solution

Solution. BIOLOGY has seven letters, two of which are O. Selecting three of the seven letters can be done in \(\binom {7}{3} = 35\) ways.

(a). Avoiding O means choosing all three from the five letters B, I, L, G, Y: \(\binom {5}{3} = 10\), so \[P = \frac {10}{35} = \frac {2}{7}.\]

(b). Both O’s are taken, and the third letter is any of the other five: \(\binom {5}{1} = 5\), so \[P = \frac {5}{35} = \frac {1}{7}.\]

Problem 1.5.9. In a class of 24 girls, 7 have black hair.

(a).: If two girls are chosen at random from the class, find the probability that (i) they both have black hair; (ii) neither has black hair.
(b).: If three girls are chosen at random, find the probability that more than one will have black hair.

Show solution

Solution. There are 7 girls with black hair and \(24-7 = 17\) without.

(a). Two girls can be chosen in \(\binom {24}{2} = 276\) ways. \begin {align*} \text {(i)}\quad P(\text {both black}) &= \frac {\binom {7}{2}}{\binom {24}{2}} = \frac {21}{276} = \frac {7}{92} \approx 0.076.\\ \text {(ii)}\quad P(\text {neither black}) &= \frac {\binom {17}{2}}{\binom {24}{2}} = \frac {136}{276} = \frac {34}{69} \approx 0.493. \end {align*}

(b). Three girls can be chosen in \(\binom {24}{3} = 2024\) ways. “More than one” means exactly two or exactly three have black hair: \[P = \frac {\binom {7}{2}\binom {17}{1}+\binom {7}{3}}{\binom {24}{3}} = \frac {357+35}{2024} = \frac {392}{2024} = \frac {49}{253} \approx 0.194.\]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.