1.5 Counting Techniques
In the classical definition of probability, \(P(E) = \frac {n(E)}{N}\), we must be able to count the number of outcomes in the event space and the sample space. When the number of outcomes is too large to list manually, we use counting techniques or combinatorial analysis.
1.5.1 Multiplication Principle
If an operation can be performed in \(n_1\) ways, and for each of these a second operation can be performed in \(n_2\) ways, then the two operations can be performed together in \(n_1 \times n_2\) ways.
If there are \(k\) operations, the total number of ways is \(n_1\times n_2 \times \cdots \times n_k\).
Example 1.5.1. Find the number of possible outcomes of the rolling of a die and then a tossing a coin.
Solution. Here \(n_1= 6\) and \(n_2 = 2\). By the multiplication principle, the number of possible outcomes is \(6 \times 2 = 12\).
Example 1.5.2. How many different license plates are possible if Lusaka uses three letters followed by two digits.
Solution. \[(26)^3(10)^2 = 1,757,600\] □
1.5.2 Permutations
A permutation is an arrangement of all or part of a set of objects in a specific order. The order of selection matters and one permutation differs from another permutation.
Definition 1.5.3. The number of permutations of \(n\) distinct objects taken \(k\) at a time is denoted by \(_nP_k\) or \(P(n,k)\) or \(P^n_k\) and is given by: \[ _nP_k = \frac {n!}{(n-k)!} \] where \(n!\) (n-factorial) is \(n \times (n-1) \times \cdots \times 1\). By definition, \(0! = 1\).
Example 1.5.4. Suppose that there are 4 objects: \(p,q,r,s\) \(-\) then the possible arrangements of these objects if 3 are taken at a time are: \(n = 4\) and \(k = 3\) \[_nP_k = \frac {n!}{(n - k)!}=\frac {4!}{(4-3)!} = \frac {4\times 3\times 2\times 1!}{1!}=24.\] There are 24 arrangements; permutations of four things taken three at a time.
| \(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. Suppose there are \(n\) objects, where \(k_1\) are of one type, \(k_2\) are of another type, \(\cdots \) , \(k_m\) are the \(m^{\text {th}}\) type, where \(k_1+k_2+\cdots +k_m=n\).
The number of distinct permutations of \(n\) objects is denoted by \(\, P^n_{k_1,k_2,\cdots ,k_m}\,\) and is given by \[P^n_{k_1,k_2,\cdots ,k_m}=\frac {n!}{k_1!k_2!\cdots k_m!}.\]
- (a).
- How many different ways can 3 red, 4 yellow and 2 blue light bulbs be arranged on a string of
tree lights with nine sockets.
Solution. We have \(\, k_1 = 3, \quad k_2 = 4, \quad k_3 = 2\,\) and \(\, n = 3+ 4 + 2\) \[P^n_{k_1,k_2,k_3}=\frac {n!}{k_1!\,k_2!\,k_3!}\] \[P^9_{3,4,2}=\frac {9!}{3!4!2!}=\frac {9\times 8\times 7\times 6\times 5\times 4!}{3\times 2\times 1\times 2\times 1\times 4!}=1260.\] □
- (b).
- How many different ways can seven female students on a field trip course be assigned to one
triple room and two double rooms at a guest house.
Solution. The seven students are being partitioned into three distinct groups: one group of 3 (the triple room) and two groups of 2 (the double rooms). We have \(k_1 = 3, \quad k_2 = 2,\, \quad k_3 = 2\) and \(\, n = 7\) \[P^n_{k_1,\,k_2,\, k_3} = \frac {n!}{k_1!\, k_2!\, k_3!}\] \[P^7_{3,2,2} = \frac {7!}{3!\, 2!\, 2!}=\frac {7\times 6\times 5\times 4\times 3!}{3!\times 2\times 2}=210.\] □
1.5.3 Combinations
A combination is a selection of objects where the order does not matter. We are only interested in which objects are chosen, not the sequence in which they are picked.
Definition 1.5.7. The number of combinations of \(n\) distinct objects taken \(k\) at a time is denoted by \(^nC_k\), \(\binom {n}{k}\), or \(C(n,k)\) and is given by: \[ \binom {n}{k} = \frac {n!}{k!(n-k)!}.\]
- 1.
- Express the permutation as a combination \[P^n_k = k!\, \binom {n}{k}.\]
- 2.
- Let \(n\in \mathbb {N}\) and \(k = 0, 1, 2, \cdots , n\). Then \[\binom {n}{k} = \binom {n}{n-k}.\]
- 3.
- For any positive integer \(n\) and \(k = 1, 2, 3 , \cdots , n\), we have \[\binom {n}{k} = \binom {n - 1}{k} + \binom {n - 1}{k - 1}.\]
- 4.
- Let \(m\) and \(n\) be positive integers. Then \[\sum ^k_{r = 0}\binom {m}{r}\binom {n}{k-r} = \binom {m+n}{k}.\]
Example 1.5.9. A production lot of size 100 has \(5\%\) defective items. A random sample of size 10 is selected (without replacement). Let \(A\) be the event that there are exactly 2 defective, \(B\) be the event that there are no defectives and \(C\) be the event that there are at most 2 defectives. \(D\) event that there is at least 2 defectives. Find the probabilities of \(A, B\) and \(C, D\).
Solution. Let \(N = 100\), with \(D= 5\) defectives and \(n-D = 95\) non-defectives. We select \(n=10\).
Possible ways of the samples \(\binom {100}{10}\).
\(A\): Exactly 2 defectives
Ways to pick 2 defectives from 5 \[\binom {5}{2} = \frac {5!}{2!\, (5-2)!}=\frac {5\times 4\times 3!}{2\times 1\times 3!}=10.\] Event space \(n(A)\) \[n(A) = \binom {5}{2}\binom {95}{8}.\] The probability \[P(A) = \frac {\binom {5}{2}\, \binom {95}{8}}{\binom {100}{10}}= \frac {1335}{19012}\approx 0.07022\]
\(B\): No defectives
Ways to pick 0 defectives from 5 \[\binom {5}{0} = \frac {5!}{0!\, (5-0)!} = 1.\] Event space \(n(B)\) \[n(B) = \binom {5}{0}\binom {95}{10}.\] The probability \[P(B) = \frac {\binom {5}{0}\, \binom {95}{10}}{\binom {100}{10}} \approx 0.584 \]
\(C\): At most 2 defectives
Ways to pick at most 2 defectives \[\binom {5}{0}+ \binom {5}{1} + \binom {5}{2}\] Event space \[n(C) = \binom {5}{0}\binom {95}{10} + \binom {5}{1}\binom {95}{9} + \binom {5}{2}\binom {95}{8}.\] The probability \[P(C) = \frac {\binom {5}{0}\binom {95}{10}}{\binom {100}{10}} + \frac {\binom {5}{1}\binom {95}{9}}{\binom {100}{10}} + \frac {\binom {5}{2}\binom {95}{8}}{\binom {100}{10}}\approx 0.9934\]
\(D\): At least 2 defectives
\(P(D) = 1 - P(X < 2)\) \[P(D) = 1 -\left [\frac {\binom {5}{0}\binom {95}{10}}{\binom {100}{10}} + \frac {\binom {5}{1}\binom {95}{9}}{\binom {100}{10}}\right ] = 0.0769\] □
1.5.4 Practice problems
These are past assignment, quiz and examination questions on counting. Each one says where it came from. Try it before opening the solution.
Problem 1.5.1. [Assignment] 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. [Assignment] 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. [Examination] 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}.\]
- (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).
- The UNZA 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. [Examination] 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. [Tutorial Sheet 1] 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. [Tutorial Sheet 1] 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. [Tutorial Sheet 1] 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. [Tutorial Sheet 1] 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.