Algebra 2

Probability with counting formulas

A committee of 5 is picked at random from 8 seniors and 7 juniors. There are thousands of possible committees, so how do you find the chance that exactly 3 of the 5 are seniors without listing them?

You need

Dependent events and drawing without replacementMath 7

Where you are 10 in Counting

Probability4

Counting10

▴ 2 above Combinations with repetition: stars and bars Inclusion-exclusion for three or more sets, and derangements

Probability with counting formulas

The fundamental counting principle Pascal's triangle ▾ Show all 10 (3 more)

Why this exists

Drawing without replacement already has a method: follow the draws one at a time, and multiply each chance by the next one worked out from what is left. That works well for two or three draws. A committee of 5 chosen from 15 people is five draws, and the question “exactly 3 seniors” does not say which three of the five places the seniors fill. A tree for it has 32 paths, and ten of them end in the outcome you want.

Very often the order of the draws does not matter at all. A committee is a group, a hand of cards is a group, a sample of apples pulled from a basket for inspection is a group. When the outcome is a group, there is a shorter road: count groups. Combinations count how many groups of a given size there are, and the fundamental counting principle counts the groups that have the right make-up. The probability is one count divided by the other.

This lesson builds that count, uses it for “exactly”, “at least” and “at most” questions, checks it against drawing in order, and carries it to collections with three or more kinds of item.

Definition

A collection of N different items is split into two kinds: K items of the kind you are interested in, and the other N - K. A group of n items is taken at random without replacement, which means every group of n items has the same chance of being the one taken. This is the same as drawing the items one at a time without putting any back and then forgetting the order they came in.

The probability that the group contains exactly k items of the first kind is

P(\text{exactly } k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}

The bottom counts every group that could be taken. The top counts the groups with the right make-up: k items from the K of the first kind, and the remaining n - k from the N - K of the other kind. Statistics books call this a hypergeometric probability, and the number of first-kind items in the group a hypergeometric count.

Intuition

Lay the committee question out as two rows of people, as in Figure 1. The 8 seniors stand on one side and the 7 juniors on the other. A committee with exactly 3 seniors is made by doing two separate things: picking 3 of the seniors, and picking 2 of the juniors to fill the other two places.

Figure 1A committee with exactly 3 seniors is a choice of 3 seniors together with a choice of 2 juniors, so the two counts multiply.

There are \binom{8}{3} = 56 ways to pick the seniors and \binom{7}{2} = 21 ways to pick the juniors, and any choice of seniors goes with any choice of juniors. So there are 56 \times 21 committees of the kind you want. The question was never about who was drawn first; it was about what the finished group looks like, and the count reads the finished group directly.

Results

Exactly k of one kind. For a group of n taken at random from K items of one kind and N - K of the other,

P(\text{exactly } k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}

More than two kinds. If the collection has K_1 items of the first kind, K_2 of the second, and so on up to K_m, with K_1 + K_2 + \cdots + K_m = N, then the probability that a random group of n has exactly k_1 of the first kind, k_2 of the second, and so on, with k_1 + k_2 + \cdots + k_m = n, is

\frac{\binom{K_1}{k_1}\binom{K_2}{k_2}\cdots\binom{K_m}{k_m}}{\binom{N}{n}}

“At least” and “at most”. Different values of k cannot happen together, so the probability of a range of values is the sum of the probabilities of the values in it. When the range is long, its complement is usually short:

\begin{aligned} P(\text{at least } 1) &= 1 - P(\text{exactly } 0) \\ &= 1 - \frac{\binom{N-K}{n}}{\binom{N}{n}} \end{aligned}

Order does not change the answer. Drawing the n items one at a time without replacement and using the general multiplication rule on every order gives the same probability as counting groups.

Why it is true

Why groups are equally likely. “At random” means each of the \binom{N}{n} groups has the same chance. When outcomes are equally likely, the probability of an event is the number of outcomes in it divided by the number of outcomes in all, so

P(\text{exactly } k) = \frac{\text{favorable groups}}{\binom{N}{n}}

where the favorable groups are those with exactly k items of the first kind.

Why the top is a product. A group with exactly k of the first kind splits in one way only into its first-kind part, which is k of the K, and its other part, which is n - k of the N - K. Every choice of the first part combined with every choice of the second gives a different group of the right make-up, and every such group arises from exactly one pair of choices. By the fundamental counting principle the number of such groups is \binom{K}{k}\binom{N-K}{n-k}. The same argument with m parts gives the product of m combination counts.

Why order does not matter. Count ordered draws instead. There are N(N-1)\cdots(N-n+1) ordered draws of n items, and each group can be drawn in n! orders, so this total is n!\binom{N}{n}. Each favorable group can also be drawn in n! orders, so the number of favorable ordered draws is n!\binom{K}{k}\binom{N-K}{n-k}. The ratio of favorable to total is the same with or without the factor n!, which cancels:

\begin{aligned} \frac{n!\binom{K}{k}\binom{N-K}{n-k}}{n!\binom{N}{n}} &= \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}} \end{aligned}

Why the probabilities over all k add to 1. Every group of n has some number of first-kind items, and only one. Sorting all \binom{N}{n} groups by that number gives

\sum_{k} \binom{K}{k}\binom{N-K}{n-k} = \binom{N}{n}

so the probabilities add to 1, as the probabilities of all the outcomes of one experiment must.

Worked examples

Example 1

Exactly three seniors

A committee of 5 is chosen at random from 8 seniors and 7 juniors. Find the probability that exactly 3 of the committee are seniors.

Solution

The order in which members are named does not matter, so the outcomes are groups of 5 taken from 15 people, and choosing at random makes every group equally likely. The number of groups is

\begin{aligned} \binom{15}{5} &= \frac{15 \times 14 \times 13 \times 12 \times 11}{5 \times 4 \times 3 \times 2 \times 1} \\ &= 3003 \end{aligned}

A committee with exactly 3 seniors has 3 of the 8 seniors and, to make 5, exactly 2 of the 7 juniors. Those two choices are made independently of each other, so by the fundamental counting principle the number of such committees is

\binom{8}{3}\binom{7}{2} = 56 \times 21 = 1176

The probability is

P(\text{exactly 3 seniors}) = \frac{1176}{3003} = \frac{56}{143} \approx 0.392

dividing top and bottom by 21.

Example 2

Every possible number of seniors

For the same committee, find the probability of each possible number of seniors, from 0 to 5, and check that they add to 1.

Solution

With k seniors the committee has 5 - k juniors, so the count is \binom{8}{k}\binom{7}{5-k} each time, over the same 3003:

Seniors k	Count of committees	Probability
0	\binom{8}{0}\binom{7}{5} = 1 \times 21 = 21	\displaystyle \frac{3}{429}
1	\binom{8}{1}\binom{7}{4} = 8 \times 35 = 280	\displaystyle \frac{40}{429}
2	\binom{8}{2}\binom{7}{3} = 28 \times 35 = 980	\displaystyle \frac{140}{429}
3	\binom{8}{3}\binom{7}{2} = 56 \times 21 = 1176	\displaystyle \frac{168}{429}
4	\binom{8}{4}\binom{7}{1} = 70 \times 7 = 490	\displaystyle \frac{70}{429}
5	\binom{8}{5}\binom{7}{0} = 56 \times 1 = 56	\displaystyle \frac{8}{429}

Each probability has been divided top and bottom by 7, since 3003 = 7 \times 429. The counts add up to every committee, each once,

\begin{aligned} 21 + 280 + 980 &+ 1176 + 490 + 56 \\ &= 3003 \end{aligned}

so the probabilities add to 1. Figure 2 draws them.

Figure 2Every possible number of seniors, with its probability. The six bars add to 1.

The most likely make-up is 3 seniors, which fits: seniors are \displaystyle \frac{8}{15} of the people, and \displaystyle \frac{8}{15} of 5 is about 2.7. The table is a whole probability distribution, and its mean is exactly \displaystyle 5 \times \frac{8}{15}:

\begin{aligned} &\frac{0(3) + 1(40) + 2(140)}{429} + \frac{3(168) + 4(70) + 5(8)}{429} \\ &\quad = \frac{1144}{429} = \frac{8}{3} \end{aligned}

Example 3

At least, by adding and by the complement

For the same committee, find (a) the probability of at least 4 seniors, and (b) the probability of at least 1 senior.

Solution

(a) “At least 4” means 4 or 5. A committee cannot have both, so the two probabilities add:

P(\text{at least 4}) = \frac{490 + 56}{3003} = \frac{546}{3003} = \frac{2}{11}

(b) “At least 1” means 1, 2, 3, 4 or 5: five cases to add. Its complement is a single case, no seniors at all, which is a committee taken entirely from the 7 juniors:

\begin{aligned} P(\text{at least 1}) &= 1 - P(\text{no seniors}) \\ &= 1 - \frac{\binom{7}{5}}{\binom{15}{5}} \\ &= 1 - \frac{21}{3003} = 1 - \frac{1}{143} = \frac{142}{143} \end{aligned}

Adding the five cases from the table gives the same answer with more work:

\frac{40 + 140 + 168 + 70 + 8}{429} = \frac{426}{429} = \frac{142}{143}

The complement is the shorter road whenever the event leaves out only one or two values.

Example 4

The same committee, drawn in order

Find the probability of exactly 3 seniors again, this time by naming the committee one member at a time and using the general multiplication rule.

Solution

Take one particular order first: three seniors, then two juniors. After each name is drawn there is one person fewer to choose from, and one fewer of that kind:

\begin{aligned} P(\text{SSSJJ}) &= \frac{8}{15} \cdot \frac{7}{14} \cdot \frac{6}{13} \cdot \frac{7}{12} \cdot \frac{6}{11} \\ &= \frac{14112}{360360} \end{aligned}

Now take another order, say SJSJS. Its fractions are \displaystyle \frac{8}{15} \cdot \frac{7}{14} \cdot \frac{7}{13} \cdot \frac{6}{12} \cdot \frac{6}{11}. The bottoms are again 15, 14, 13, 12, 11, because one person goes each time, and the tops are again 8, 7, 6 for the seniors and 7, 6 for the juniors, in a different arrangement. Multiplication is commutative, so every order with three S and two J has the same probability.

The number of such orders is the number of ways to choose which 3 of the 5 places are seniors, \binom{5}{3} = 10. The orders are separate outcomes, so their probabilities add:

\begin{aligned} P(\text{exactly 3 seniors}) &= 10 \times \frac{14112}{360360} \\ &= \frac{141120}{360360} = \frac{56}{143} \end{aligned}

This agrees with Example 1, as the argument under “Why it is true” says it must. The group count did in one line what the ordered method did in three: the \binom{5}{3} orders and the falling products are both folded into the combination counts.

Example 5

Three kinds at once

A drawer holds 15 pens: 6 blue, 5 black and 4 red. Four pens are taken without looking. Find the probability of getting exactly 2 blue, 1 black and 1 red.

Solution

The outcomes are groups of 4 from 15, all equally likely, and there are \binom{15}{4} = 1365 of them. A favorable group is made in three independent stages: 2 of the 6 blue, 1 of the 5 black, 1 of the 4 red. The counting principle multiplies the stages:

\binom{6}{2}\binom{5}{1}\binom{4}{1} = 15 \times 5 \times 4 = 300

P = \frac{300}{1365} = \frac{20}{91} \approx 0.220

The tops (6, 5, 4) add to the whole drawer, 15, and the choices (2, 1, 1) add to the number taken, 4. Checking both sums is a quick way to see that no kind has been missed.

Example 6

A number game

In a game, 5 different numbers are drawn at random from 1 to 25. Before the draw a player picks 5 numbers of their own. Find the probability that exactly 3 of the player’s numbers are drawn, and the probability that at least 4 are.

Solution

This does not look like a committee, but it has the same shape. Split the 25 numbers into two kinds: the player’s 5 and the other 20. The draw is a random group of 5, and “matching exactly 3” means the group holds 3 of the player’s numbers and 2 of the others.

\binom{25}{5} = 53130 \qquad \binom{5}{3}\binom{20}{2} = 10 \times 190 = 1900

P(\text{exactly 3 match}) = \frac{1900}{53130} = \frac{190}{5313} \approx 0.036

At least 4 means 4 matches or 5. Four matches leave 1 number from the other 20, and five matches is the player’s own group:

\begin{aligned} P(\text{at least 4}) &= \frac{\binom{5}{4}\binom{20}{1} + \binom{5}{5}\binom{20}{0}}{53130} \\ &= \frac{100 + 1}{53130} = \frac{101}{53130} \end{aligned}

That is about 1 chance in 526.

Example 7

Working back to the contents

A pot holds 9 pencils, and some of them are sharpened. Two pencils are taken at random, and the probability that both are sharpened is \displaystyle \frac{5}{12}. How many sharpened pencils are in the pot?

Solution

Call the number of sharpened pencils c. Both sharpened means 2 of the c sharpened ones and none of the others, out of \binom{9}{2} = 36 pairs:

\frac{\binom{c}{2}}{36} = \frac{5}{12} \qquad\text{so}\qquad \binom{c}{2} = 15

Since \displaystyle \binom{c}{2} = \frac{c(c-1)}{2}, this is c(c-1) = 30, a quadratic equation, solved by factoring and the zero product property:

\begin{aligned} c^2 - c - 30 &= 0 \\ (c - 6)(c + 5) &= 0 \end{aligned}

A count of pencils cannot be negative, so c = 6.

Check. \binom{6}{2} = 15 and \displaystyle \frac{15}{36} = \frac{5}{12}.

Boundaries

The group must be random. The formula rests on every group of n being equally likely. If the members are chosen by vote, or the first five to volunteer, the counts are still right but they are no longer probabilities.
Without replacement only. If each item is put back before the next draw, the same item can come up twice, the draws become independent, and the chance of the first kind stays \displaystyle \frac{K}{N} on every draw. That situation is the binomial probability formula, not this one.
The kinds must not overlap, and must cover everything. Every item belongs to exactly one kind, so the K_i add to N. If some seniors are also on the debate team and the question is about seniors and debaters, the two kinds overlap and the groups have to be counted with inclusion and exclusion instead.
Impossible make-ups count as zero. If k > K or n - k > N - K there is no way to make the group. Reading \binom{a}{b} as 0 when b > a keeps the formula correct in those cases: it gives probability 0.
The group size is fixed in advance. The formula answers questions about a group of a known size n. “Keep drawing until the first junior appears” is a different experiment with a different count.

Where this goes next

Example 2 turned one experiment into a whole table of values of a random variable, the number of seniors on the committee. That table is a probability distribution, the hypergeometric distribution, and its mean came out as \displaystyle n \cdot \frac{K}{N}. The same mean belongs to the binomial distribution, which describes the matching experiment with replacement. When the collection is very large compared with the sample, taking one item out barely changes the others’ chances, and the two distributions come out almost the same; that is why a random sample from a large population is usually treated as binomial even though nobody is sampled twice.

The counting idea itself carries further. Testing a sample from a delivery and deciding whether to accept the whole delivery is a hypergeometric question. So is counting the possible hands in a card game, or estimating how many fish live in a lake by tagging some and seeing how many tagged fish turn up in a later catch.

Exercises

Exactly so many of one kind

A pouch holds 6 red beads and 4 blue beads. Three beads are taken at random. Find the probability that exactly 2 are red.
A basket of 20 apples contains 4 that are bruised. Three apples are taken at random. Find the probability that none of them is bruised.
A market box holds 9 ripe and 6 unripe avocados. Four are taken at random. Find the probability that exactly 2 are ripe.
Two cards are dealt from a standard deck of 52, which has 13 hearts. Find the probability that exactly one of the two is a heart.
Five cards are dealt from a standard deck, which has 4 kings. Find the probability that the hand holds exactly 3 kings.

At least and at most

For the apples in Exercise 2, find the probability that at least one of the three is bruised.
For the beads in Exercise 1, find the probability that at least 2 of the three are red.
For the committee of 5 from 8 seniors and 7 juniors, find the probability that the committee has at most 1 senior.
For the avocados in Exercise 3, find the probability that at least one of the four is unripe.
A panel of 4 is chosen at random from 6 residents of the north village and 5 of the south village. Find the probability that both villages are on the panel.

Drawing in order

Find the probability in Exercise 1 again by drawing the beads one at a time and using the general multiplication rule on every order.
The avocados of Exercise 3 are taken one at a time. (a) Find the probability that the first two are ripe and the last two unripe. (b) Use your answer, and the number of orders, to recover the answer to Exercise 3.
The apples of Exercise 2 are inspected one at a time. Find the probability that the first two are sound and the third is bruised.

More than two kinds

A bag holds 16 sweets: 7 lemon, 5 lime and 4 orange. Three are taken at random. Find the probability of one of each flavor.
For the same bag, find the probability that all three sweets are the same flavor.
A cupboard holds 5 board games, 4 card games and 3 puzzles. Four are taken at random for a holiday. Find the probability of 2 board games, 1 card game and 1 puzzle.

Working backwards

A bag holds 12 counters, some of them green. Two are taken at random, and the probability that both are green is \displaystyle \frac{1}{11}. How many green counters are in the bag?
A box holds 8 cards, some of them winners. Two cards are taken at random, and the probability that neither is a winner is \displaystyle \frac{15}{28}. How many winning cards are in the box?

Reasoning

Explain why \binom{8}{3}\binom{7}{2} counts every committee with exactly 3 seniors once, and no committee twice.
Explain, by sorting committees, why \sum_{k=0}^{5}\binom{8}{k}\binom{7}{5-k} = \binom{15}{5}.
Someone works out the committee question as \displaystyle 10\left(\frac{8}{15}\right)^3\left(\frac{7}{15}\right)^2. Describe the experiment that number belongs to, and explain why it is not the committee.
Explain why counting ordered draws and counting groups must give the same probability.
A committee of 5 is chosen from 3 seniors and 12 juniors. What does the formula give for the probability of exactly 4 seniors, and why is that right?

Answers

\displaystyle \frac{1}{2}. \binom{6}{2}\binom{4}{1} = 15 \times 4 = 60 groups out of \binom{10}{3} = 120, and \displaystyle \frac{60}{120} = \frac{1}{2}.
\displaystyle \frac{28}{57}. All three come from the 16 sound apples: \displaystyle \frac{\binom{16}{3}}{\binom{20}{3}} = \frac{560}{1140} = \frac{28}{57}.
\displaystyle \frac{36}{91}. \binom{9}{2}\binom{6}{2} = 36 \times 15 = 540 out of \binom{15}{4} = 1365, and \displaystyle \frac{540}{1365} = \frac{36}{91}.
\displaystyle \frac{13}{34}. One heart and one of the 39 others: \displaystyle \frac{13 \times 39}{\binom{52}{2}} = \frac{507}{1326} = \frac{13}{34}.
\displaystyle \frac{94}{54145}. \binom{4}{3}\binom{48}{2} = 4 \times 1128 = 4512 out of \binom{52}{5} = 2598960, and \displaystyle \frac{4512}{2598960} = \frac{94}{54145} \approx 0.0017.
\displaystyle \frac{29}{57}. The complement of “at least one bruised” is “none bruised”, so \displaystyle 1 - \frac{28}{57} = \frac{29}{57}. Adding the cases agrees: \displaystyle \frac{4 \times 120 + 6 \times 16 + 4}{1140} = \frac{580}{1140}.
\displaystyle \frac{2}{3}. Exactly 2 red gives 60 groups and exactly 3 red gives \binom{6}{3} = 20, so \displaystyle \frac{60 + 20}{120} = \frac{80}{120} = \frac{2}{3}.
\displaystyle \frac{43}{429}. From the table in Example 2, \displaystyle \frac{21 + 280}{3003} = \frac{301}{3003} = \frac{43}{429}.
\displaystyle \frac{59}{65}. None unripe means all four ripe: \displaystyle \frac{\binom{9}{4}}{\binom{15}{4}} = \frac{126}{1365} = \frac{6}{65}, so \displaystyle 1 - \frac{6}{65} = \frac{59}{65}.
\displaystyle \frac{31}{33}. The complement is a panel from one village only: \binom{6}{4} + \binom{5}{4} = 15 + 5 = 20 panels out of \binom{11}{4} = 330, so \displaystyle 1 - \frac{20}{330} = 1 - \frac{2}{33} = \frac{31}{33}.
\displaystyle \frac{1}{2}. Each of the orders RRB, RBR, BRR has probability \displaystyle \frac{6 \times 5 \times 4}{10 \times 9 \times 8} = \frac{120}{720} = \frac{1}{6}, and there are \binom{3}{2} = 3 orders, so \displaystyle 3 \times \frac{1}{6} = \frac{1}{2}.
(a) \displaystyle \frac{6}{91}: \displaystyle \frac{9}{15} \cdot \frac{8}{14} \cdot \frac{6}{13} \cdot \frac{5}{12} = \frac{2160}{32760} = \frac{6}{91}. (b) Every order of two ripe and two unripe has this same probability, and there are \binom{4}{2} = 6 orders, so \displaystyle 6 \times \frac{6}{91} = \frac{36}{91}, as in Exercise 3.
\displaystyle \frac{8}{57}. \displaystyle \frac{16}{20} \cdot \frac{15}{19} \cdot \frac{4}{18} = \frac{960}{6840} = \frac{8}{57}.
\displaystyle \frac{1}{4}. \binom{7}{1}\binom{5}{1}\binom{4}{1} = 140 out of \binom{16}{3} = 560.
\displaystyle \frac{7}{80}. All lemon, all lime or all orange: \binom{7}{3} + \binom{5}{3} + \binom{4}{3} = 35 + 10 + 4 = 49, and \displaystyle \frac{49}{560} = \frac{7}{80}.
\displaystyle \frac{8}{33}. \binom{5}{2}\binom{4}{1}\binom{3}{1} = 10 \times 4 \times 3 = 120 out of \binom{12}{4} = 495, and \displaystyle \frac{120}{495} = \frac{8}{33}.
4. \displaystyle \frac{\binom{g}{2}}{66} = \frac{1}{11} gives \binom{g}{2} = 6, so g(g-1) = 12 and g = 4 (the other root, -3, is not a count).
2. With w winners, \displaystyle \frac{\binom{8-w}{2}}{28} = \frac{15}{28} gives \binom{8-w}{2} = 15, so 8 - w = 6 and w = 2.
A committee with exactly 3 seniors is one choice of 3 seniors joined to one choice of 2 juniors. Different pairs of choices give different committees, because two committees with the same members have the same seniors and the same juniors. So the product of the two counts lists each such committee once.
Every committee of 5 has some number k of seniors, from 0 to 5, and only one such number. Sorting all \binom{15}{5} committees by k puts each in exactly one pile, and the pile for k holds \binom{8}{k}\binom{7}{5-k} committees. The pile sizes add to the whole.
It belongs to choosing 5 times with replacement, where the same person may be picked again and the chance of a senior is \displaystyle \frac{8}{15} on every pick: the binomial setting. A committee cannot repeat a person, so after each pick the chances change, and the binomial number is not the committee probability.
Each group of n can be drawn in exactly n! orders, favorable or not. So the favorable ordered draws and all the ordered draws are both n! times the matching group counts, and the factor n! cancels in the ratio.
0. The top is \binom{3}{4}\binom{12}{1}, and \binom{3}{4} = 0 because 4 seniors cannot be chosen from 3. A committee with 4 seniors is impossible, so probability 0 is correct.