Counting, Combinatorics, and Discrete Probability

Many probability questions become manageable when we count outcomes systematically instead of listing them at random. This lesson develops the tools for counting ordered and unordered selections, then uses those counts to find probabilities and conditional probabilities. Comfort with fractions and algebra is helpful; related lessons on Algebra and introductory probability vocabulary are useful preparation.

Counting Outcomes Systematically

The fundamental counting principle says that if a process has a choices at one stage and each first-stage choice is followed by b choices at the second stage, then it has ab outcomes. The stages need not be independent; multiplication only requires the same number of continuations for each first-stage choice. If the number of second-stage choices depends on the branch, count the outcomes on each branch and add them instead—for example, if the branches have 2, 3, and 5 continuations, the total is 2 + 3 + 5, not 3 times one common number.

Worked example: a product of choices

A lunch menu has 3 sandwich choices, 4 drink choices, and 2 fruit choices. How many different lunches can a student make by choosing one of each?

sandwiches × drinks × fruits
= 3 × 4 × 2
= 24

There are 24 possible lunches.

If choices cannot repeat, the number of choices usually decreases at each stage. A password made from three distinct letters chosen from 26 letters has 26 · 25 · 24 possibilities, not 26³.

Worked example: addition versus multiplication

A club will select either one of 5 science workshops or one of 4 arts workshops, but not both. There are 5 + 4 = 9 possible selections. Use addition for mutually exclusive alternatives (“this or that”) and multiplication for consecutive choices (“this and then that”).

Factorials and Permutations

The factorial n! is the product of the positive integers from n down to 1:

n! = n(n − 1)(n − 2) ... 2 · 1. By definition, 0! = 1. For example, 5! = 5 · 4 · 3 · 2 · 1 = 120.

A permutation is an arrangement in which order matters. The number of ways to choose and arrange r distinct objects from n distinct objects is

P(n, r) = nPr = n!/(n − r)!.

Worked example: assigning ranked positions

Eight finalists compete for gold, silver, and bronze. How many possible medal outcomes are there?

Gold:   8 choices
Silver: 7 remaining choices
Bronze: 6 remaining choices

8P3 = 8 × 7 × 6 = 336

The outcome “Ava, Ben, Chen” differs from “Ben, Ava, Chen,” because gold and silver are different positions.

Combinations and Binomial Coefficients

A combination is a selection in which order does not matter. The number of ways to select r objects from n distinct objects is

C(n, r) = ( n over r ) = n!/[r!(n − r)!].

The factor r! removes the repeated orderings of each group. Thus C(n, r) = C(n, n − r): choosing 3 people to include from 10 is equivalent to choosing 7 people to leave out.

Worked example: choosing a committee

Choose a 3-person committee from 10 students.

10C3 = 10! / [3!(10 − 3)!]
     = (10 × 9 × 8) / (3 × 2 × 1)
     = 120

There are 120 committees.

Do not use 10P3 = 720: each committee of three was counted 3! = 6 times, once for every ordering of its members.

Binomial coefficients

The values ( n over r ) are called binomial coefficients because they are the coefficients in the expansion of (a + b)ⁿ. The binomial theorem is

(a + b)ⁿ = ∑_r=0ⁿ ( n over r )a^n−rb^r.

For a particular term, choose which factors contribute b; that explains why the coefficient is a combination.

Worked example: one coefficient

Find the coefficient of x³ in (2 + x)⁵.

Choose x from 3 of the 5 factors:
coefficient = 5C3 · 2^(5 − 3)
            = 10 · 4
            = 40

The term is 40x³.

Probability from Equally Likely Outcomes

For a finite sample space with equally likely elementary outcomes, the probability of event A is

P(A) = number of outcomes in A / total number of outcomes.

Probabilities lie from 0 to 1. The complement A^c means “not A,” so P(A^c) = 1 − P(A).

Worked example: a five-card hand

What is the probability that a randomly dealt 5-card hand from a standard 52-card deck contains exactly 2 aces?

Total hands:       52C5
Favourable hands:    4C2 · 48C3
                     choose 2 of 4 aces and 3 non-aces

P(exactly 2 aces) = [4C2 · 48C3] / 52C5
                   = 103,776 / 2,598,960
                   ≈ 0.0399, or 3.99%

Conditional Probability: Restrict the Sample Space

A conditional probability asks for the probability of A given that event B has occurred. The condition changes the sample space to B:

P(A | B) = P(A ∩ B)/P(B), provided P(B) > 0.

Read A | B as “A given B.” The intersection A ∩ B means both events occur.

Worked example: reading a two-way table

In a survey of 100 students, the following table records whether each student takes music and plays a sport.

	Plays a sport	No sport	Total
Takes music	24	16	40
No music	36	24	60
Total	60	40	100

Find the probability that a randomly selected music student plays a sport.

P(sport | music) = number who take music and play a sport
                   / number who take music
                  = 24/40
                  = 3/5

The denominator is 40, not 100, because “takes music” is already known. In contrast, P(music | sport) = 24/60 = 2/5; reversing a condition usually changes the answer.

Tree Reasoning and Dependence

A probability tree represents successive stages. Multiply probabilities along one complete path; add the probabilities of mutually exclusive paths that satisfy the event. When an item is selected without replacement, the second-stage probabilities depend on the first selection.

Worked example: without replacement

A bag contains 3 red and 2 blue counters. Two counters are drawn without replacement. Find the probability of one red and one blue, in either order.

red then blue:  3/5 · 2/4 = 6/20
blue then red: 2/5 · 3/4 = 6/20

P(one of each) = 6/20 + 6/20
               = 12/20
               = 3/5

With replacement, the second denominator would remain 5. Replacing an item restores the original composition and makes the draws independent.

Applications

• Security: counting possible passwords estimates resistance to guessing. Rules such as “no repeated character” change the multiplication factors.
• Quality control: combinations count possible samples drawn from a production batch; conditional probabilities help interpret test results.
• Genetics and reliability: trees model sequences of inherited traits or components that work or fail.
• Data analysis: two-way tables distinguish an overall rate from a rate within a specified group.

Common Mistakes

• Using a permutation when a group has no positions. Ask: would rearranging the selected people create a new outcome?
• Using n^r when repetition is prohibited. That expression allows the same choice at every stage.
• Adding paths that are not mutually exclusive, or failing to add distinct successful paths in a tree.
• Keeping the original total as the denominator after a condition is given. Conditional probability restricts the denominator to the condition.
• Assuming equal likelihood without justification. “Favourable over total” requires equally likely elementary outcomes.

Practice Set

1. A code has two letters followed by three digits. Letters and digits may repeat. How many codes are possible?
2. How many ways can 7 different books be arranged on a shelf?
3. From 12 volunteers, how many 4-person teams can be chosen?
4. How many distinct arrangements of the letters in LEVEL are there?
5. Find the coefficient of x² in (3 + x)⁴.
6. A fair six-sided die is rolled twice. What is the probability that the sum is 8?
7. From a standard deck, what is the probability that a card is a heart given that it is red?
8. A jar has 4 green and 6 yellow marbles. Two are drawn without replacement. Find the probability that both are green.
9. In a group, 18 of 30 students study French, and 12 of those 18 also study Spanish. Find P(Spanish | French).
10. A committee of 3 is chosen from 5 seniors and 4 juniors. What is the probability that it contains exactly 2 seniors?

Answers

1. 26 · 26 · 10 · 10 · 10 = 676,000 codes.
2. 7! = 5,040 arrangements.
3. ( 12 over 4 ) = 12!/(4!8!) = 495 teams.
4. There are 5! arrangements if all letters were different. Divide by 2! for the two Ls and 2! for the two Es: 5!/(2!2!) = 30.
5. Choose x from two factors: ( 4 over 2 )3² = 6 · 9 = 54. The term is 54x².
6. There are 36 ordered outcomes. Sum 8 occurs for (2, 6), (3, 5), (4, 4), (5, 3), and (6, 2), so the probability is 5/36.
7. There are 26 red cards, of which 13 are hearts. Thus P(heart | red) = 13/26 = 1/2.
8. (4/10)(3/9) = 12/90 = 2/15.
9. Within the 18 French students, 12 study Spanish: P(Spanish | French) = 12/18 = 2/3.
10. Favourable committees: ( 5 over 2 )( 4 over 1 ) = 40. Total committees: ( 9 over 3 ) = 84. The probability is 40/84 = 10/21.