A. Counting and Probability · Permutations and CombinationsThe Additive Counting Principle and Indirect Counting
A2.3About 65 minutes
Learning goals- I can tell when to add and when to multiply in a counting problem.
- I can use the additive counting principle for mutually exclusive cases.
- I can use the principle of inclusion and exclusion when cases overlap.
- I can count indirectly by subtracting the unwanted outcomes from the total.
Words to know
additive counting principle
If one task can be done in m ways and a different task in n ways, and the two cannot both happen, then one task OR the other can be done in m + n ways. Also called the rule of sum.
mutually exclusive
Describes two events or cases that cannot happen at the same time, such as drawing a heart and drawing a spade with one card.
principle of inclusion and exclusion
For overlapping sets: n(A or B) = n(A) + n(B) − n(A and B).
complement
Everything in the sample space that is NOT in a set A. Written A′ (read "A prime").
indirect counting
Counting the outcomes you do not want and subtracting from the total.
case
One of several non-overlapping situations that a problem is split into, so each can be counted separately.
AND or OR?
A student council needs volunteers for the Remembrance Day assembly. The club has 4 boys and 5 girls. The teacher asks for 2 boys or 2 girls to carry the wreath. How many different pairs are possible? Then she asks for 2 boys and 2 girls to read. How many groups of four are possible?
These two questions sound almost the same, but one is answered by adding and the other by multiplying. Today you will learn exactly when to do which.
The additive counting principle
If one task can be done in m ways and a different task in n ways, and the two tasks cannot both be done (they are mutually exclusive), then one task OR the other can be done in m + n ways.
Example: a cafeteria has 4 hot dishes and 3 salads, and you may take one item. You can take a hot dish or a salad: 4 + 3 = 7 choices.
Compare: if you take a hot dish and a salad, the multiplicative principle gives 4 × 3 = 12 meals.
- OR between mutually exclusive cases → add.
- AND between stages → multiply.
Worked exampleExample 1: 2 boys or 2 girls, 2 boys and 2 girls
A club has 4 boys (B1 to B4) and 5 girls (G1 to G5). (a) How many ways can 2 boys or 2 girls be chosen? (b) How many ways can 2 boys and 2 girls be chosen? (Order does not matter: choosing B1 and B2 is the same pair as B2 and B1.)
- List the pairs of boys systematically: B1B2, B1B3, B1B4, B2B3, B2B4, B3B4. That is 3 + 2 + 1 = 6 pairs.
- Pairs of girls: G1 can pair with 4 others, G2 with 3 new ones, G3 with 2, G4 with 1: 4 + 3 + 2 + 1 = 10 pairs.
- (a) A pair is either two boys or two girls, never both, so the cases are mutually exclusive. Add: 6 + 10 = 16.
- (b) Choose a pair of boys and a pair of girls. Multiply: 6 × 10 = 60.
(a) 16 ways; (b) 60 ways. In lesson 7 you will get these pair counts instantly with combinations.
Every line joins one pair. The 4 boys give 6 lines and the 5 girls give 10. OR adds the counts; AND multiplies them.When cases overlap: inclusion and exclusion
You draw one card from a standard 52-card deck (4 suits of 13 cards; the face cards are the jack, queen and king of each suit, so 12 face cards). In how many ways can you draw a heart or a face card?
It is tempting to add 13 + 12 = 25. But the jack, queen and king of hearts are both hearts and face cards. They were counted twice, so subtract them once:
n(A or B) = n(A) + n(B) − n(A and B)
13 + 12 − 3 = 22.
This is the principle of inclusion and exclusion. When the sets are mutually exclusive, n(A and B) = 0 and it becomes the plain additive principle. (You saw this with probabilities and Venn diagrams in the unit Probability; here we use it for counts.)
Worked exampleExample 2: Divisible by 3 or 5
How many whole numbers from 1 to 100 are divisible by 3 or by 5?
- Divisible by 3: 3, 6, …, 99. There are 100 ÷ 3 = 33.3…, so 33 of them (round down).
- Divisible by 5: 100 ÷ 5 = 20.
- Divisible by both means divisible by 15: 100 ÷ 15 = 6.6…, so 6.
- Inclusion and exclusion: 33 + 20 − 6 = 47.
Indirect counting: count what you don't want
Some conditions are awkward to count directly. Phrases like "at least one" usually mean many cases (exactly one, exactly two, …). It is often easier to count the complement, the outcomes that fail the condition, and subtract:
n(A) = n(total) − n(A′)
The complement of "at least one vowel" is "no vowels at all", which is a single, easy case.
Worked exampleExample 3: At least one vowel
How many three-letter codes (such as KXT or AAB; repetition allowed) contain at least one vowel? Use A, E, I, O and U as the vowels.
- Total codes: 26 × 26 × 26 = 17 576.
- Codes with no vowels use only the 21 consonants: 21 × 21 × 21 = 9261.
- Subtract: 17 576 − 9261 = 8315.
8315 codes. (Counting directly would need three cases: exactly one, two or three vowels. Try it in the challenge set and check that you get the same total.)
Indirect counting: the whole rectangle is every code. Remove the no vowels part and what is left is at least one vowel.Add or multiply? A quick test
Read the problem and ask: is one outcome built from several parts? (a code built from characters, a meal built from a main and a drink) → multiply the parts. Is the problem split into separate, non-overlapping kinds of outcome? (2 boys or 2 girls) → add the kinds. Do the kinds overlap? → add, then subtract the overlap. Does it say "at least"? → consider the complement.
Just for funInclusion and exclusion is the only party where, if you sneak in twice, the host makes you leave once.
Hands-on activityA Venn diagram on the kitchen table
You need: a standard deck of 52 playing cards (jokers removed) and two pieces of string or yarn, each about 1 m long.
- Make two overlapping loops with the string on a table. Label one loop "clubs" and the other "aces or kings" (use sticky notes or scraps of paper).
- Deal through the whole deck. Put each card in the right region: only clubs, only aces or kings, both, or outside both loops.
- Count each region. Check that the four counts add to 52.
- Use inclusion and exclusion to predict the number of cards that are a club or an ace or king, before you count. Then count to check.
- Make up your own pair of overlapping categories (for example "red" and "even number") and repeat.
What to look for: clubs only 11, aces or kings only 6, both 2 (ace and king of clubs), outside 33. Then 13 + 8 − 2 = 19 cards are a club or an ace or king, and 11 + 2 + 6 + 33 = 52. For red and even-numbered (2, 4, 6, 8, 10): red 26, even-numbered 20, both 10, so 26 + 20 − 10 = 36.
Your turn
1A student must take one elective: there are 5 arts courses and 3 technology courses, and no course is both. How many choices are there?
The cases do not overlap, so add: 5 + 3 = 8.
2How many whole numbers from 1 to 100 are divisible by 2 or by 7?
By 2: 50. By 7: 14. By 14: 7. 50 + 14 − 7 = 57.
3One card is drawn from a standard deck. In how many ways can it be a king or a club?
4 kings + 13 clubs − 1 (king of clubs) = 16.
4In a class of 30, 18 students play hockey, 12 play basketball and 5 play both. How many play at least one of these sports? How many play neither?
18 + 12 − 5 = 25 play at least one. 30 − 25 = 5 play neither.
5How many 4-digit PINs (0000 to 9999) contain at least one 7?
Total 10⁴ = 10 000. With no 7: 9⁴ = 6561. 10 000 − 6561 = 3439.
6A club has 3 Grade 11 and 4 Grade 12 members. How many ways can you choose (a) one member, (b) one Grade 11 and one Grade 12 member?
(a) 3 + 4 = 7. (b) 3 × 4 = 12.
7Locker tags are either 2 letters or 3 digits (repetition allowed). How many tags are possible?
Letter tags: 26² = 676. Digit tags: 10³ = 1000. The kinds cannot overlap: 676 + 1000 = 1676.
More practice: warm-up
1You may borrow one book: there are 6 novels and 4 biographies. How many choices?
2Now you may borrow one novel and one biography. How many choices?
3n(A) = 12, n(B) = 9 and n(A and B) = 4. Find n(A or B).
4A sample space has 50 outcomes, and 18 of them are in set A. How many are in the complement A′?
5Are "draw a heart" and "draw a spade" mutually exclusive when you draw one card? Explain.
Yes. One card cannot be both a heart and a spade.
More practice: on your own
1How many three-digit numbers (100 to 999) contain at least one 0?
Total 900. With no 0: 9 × 9 × 9 = 729. 900 − 729 = 171.
2How many whole numbers from 1 to 500 are divisible by 4 or by 6?
By 4: 125. By 6: 83. By both means by 12 (the lowest common multiple, not 24): 41. 125 + 83 − 41 = 167.
3A team has 3 boys and 6 girls. How many ways can 2 boys or 2 girls be chosen?
Boy pairs: 2 + 1 = 3. Girl pairs: 5 + 4 + 3 + 2 + 1 = 15. 3 + 15 = 18.
4A 3-character password uses letters and digits (36 symbols, repetition allowed) and must contain at least one digit. How many passwords are possible?
Total 36³ = 46 656. No digits: 26³ = 17 576. 46 656 − 17 576 = 29 080.
5Two dice are rolled. In how many outcomes is the roll a double or a sum of 8?
Doubles: 6. Sum of 8: (2,6), (3,5), (4,4), (5,3), (6,2) = 5. Both: (4,4) = 1. 6 + 5 − 1 = 10.
Challenge
1How many whole numbers from 1 to 1000 are divisible by 2, 3 or 5? (For three sets, n(A or B or C) = n(A) + n(B) + n(C) − n(A and B) − n(A and C) − n(B and C) + n(A and B and C).)
Singles: 500 + 333 + 200 = 1033. Pairs: by 6: 166, by 10: 100, by 15: 66, total 332. All three (by 30): 33. 1033 − 332 + 33 = 734.
2How many 4-digit PINs contain at least one 7 and at least one 3?
Use complements. Total 10 000. No 7: 9⁴ = 6561. No 3: 6561. Neither 7 nor 3: 8⁴ = 4096 (subtracted twice, so add it back). 10 000 − 6561 − 6561 + 4096 = 974.
3Check Example 3 directly: count three-letter codes with exactly one, exactly two and exactly three vowels, and add.
Exactly one: 3 positions for the vowel × 5 × 21 × 21 = 6615. Exactly two: 3 positions for the consonant × 21 × 5 × 5 = 1575. Exactly three: 5³ = 125. Total 6615 + 1575 + 125 = 8315 ✓, the same as 17 576 − 9261.
Quiz
1. When are the counts for two cases simply added?
2. One card is drawn from a standard deck. How many cards are a heart or a face card?
3. n(A) = 20, n(B) = 15 and n(A and B) = 6. What is n(A or B)?
4. How many three-letter codes (repetition allowed) contain at least one vowel (A, E, I, O, U)?
5. In inclusion and exclusion, why is n(A and B) subtracted?
6. A club has 4 boys and 5 girls. How many ways can 2 boys and 2 girls be chosen?
Big idea (A2.3): use addition for "or" when the cases cannot overlap, multiplication for "and" when an outcome is built in stages, and subtract the overlap when cases do overlap. Counting the complement ("total minus what we don't want") is often the fastest way to handle "at least one".
How to help: Ask your teen to explain, before calculating, whether a problem is "and" or "or", and whether the cases can overlap. A deck of cards and two loops of string make overlapping sets very concrete.
Common difficulties:
- Adding overlapping cases and counting some outcomes twice.
- Using the product of the two divisors instead of the lowest common multiple (divisible by 4 and 6 means divisible by 12, not 24).
- Trying to count "at least one" directly and missing cases. Suggest the complement.
- Forgetting that the jack, queen and king are the only face cards (12 in a deck); aces are not face cards.