On this page
Loading guide controls…
Continue lessonNew guided lessons are not available yet.
Guided lesson options
You stopped at:
ContinueRevision Mode is on. Questions and activities are hidden.
The linked question or activity is hidden by Revision Mode.
Some counting problems are hard only because they are posed in an awkward form. The bijection principle replaces a set you cannot count directly with another set of the same size that you can. The inclusion–exclusion principle counts a union of overlapping sets without counting any element twice. This lesson uses both, separately and together, for problems such as sharing identical objects between boxes, choosing numbers with no two consecutive, and counting arrangements in which nothing is in its original place.
Count one set by matching it with another
Bijection principle. If the elements of two finite sets can be paired one-to-one, with every element of each set used exactly once, the sets have the same size. To count a hard set, describe a pairing with an easy set and check that it can be reversed.
Worked example 1
Identical sweets in different jars
Worked example 1
Identical sweets in different jars
In how many ways can 10 identical sweets be placed in 4 different jars, if jars may be empty?
Show full solutionHide solution
Build the bijection
Method
Represent a distribution as a row of 10 stars (sweets) and 3 bars (dividers between jars).Reason
Reading the stars between bars recovers each jar’s count, so distributions and rows correspond one-to-one.Working
Answer
For example, starstar ∣ starstarstarstarstar ∣ ∣ starstarstar means 2,5,0,3.
Count the rows
Method
Choose which 3 of the 13 positions hold bars.Reason
Every choice gives a different valid row.Working
Answer
(13 choose 3) = 286 ways. In general, r identical objects into n distinguishable boxes can be placed in ((r + n-1) choose (n-1)) ways.
Quick check
Small check: 2 sweets in 2 jars gives (3 choose 1) = 3 ways, (2,0),(1,1),(0,2). Treating the sweets as different would give 2² = 4, counting (1,1) twice.
The stars-and-bars count is worth recording as a result. The number of ways to put r identical objects into n distinguishable boxes is
It is also the number of solutions of x₁ + x₂ + … + xₙ = r in non-negative integers.
Check your understanding 1
No empty jar
Check your understanding 1
No empty jar
In how many ways can the 10 identical sweets be placed in the 4 jars if no jar is empty? Explain the bijection you use.
Show answerHide answer
Put one sweet in each jar first. Removing those four sweets pairs each distribution with no empty jar with a distribution of the remaining 6 sweets with empty jars allowed, and adding them back reverses it. So there are ((6 + 3) choose 3) = (9 choose 3) = 84 ways.
Worked example 2
No two numbers next to each other
Worked example 2
No two numbers next to each other
In how many ways can three numbers be chosen from 1,2,…,10 so that no two of the chosen numbers are consecutive?
Show full solutionHide solution
Close up the gaps
Method
Write a choice as a < b < c and map it to (a, b-1, c-2).Reason
Because b ≥ a + 2 and c ≥ b + 2, the new numbers satisfy a < b-1 < c-2, and c-2 ≤ 8. The restriction disappears.Working
Answer
For example, {2,5,9}↦{2,4,7}. The map reverses by adding 0, 1 and 2 back, so it pairs the restricted choices with all three-element subsets of {1,…,8}.
Count the easy set
Working
Answer
(8 choose 3) = 56.
Quick check
To prove a bijection, show that the map lands in the target set and that it can be undone. A map that is not reversible can make two different choices look the same, and then the counts differ.
Inclusion–exclusion corrects overcounting
Adding the sizes of overlapping sets counts each overlap more than once. Subtract the pairwise overlaps, then add back the elements removed too often:
How often |A| + |B| + |C| counts each region
Three overlapping sets, with each region labelled by the number of the sets that contain it.
Scroll across to read every label.
Figure data
This table is included in print while it is open.
| Region | Sets containing it | Times counted |
|---|---|---|
| In one set only | 1 | 1 |
| In exactly two sets | 2 | 2 |
| In all three sets | 3 | 3 |
An element in exactly two of the sets is counted 2-1 = 1 time, and one in all three is counted 3-3 + 1 = 1 time. With n sets, the signs continue to alternate over the intersections of 1,2,3,…,n sets at a time.
Check your understanding 2
Divisible by 2, 3 or 5
Check your understanding 2
Divisible by 2, 3 or 5
- How many of the integers 1,2,…,100 are divisible by 2, 3 or 5?
- A derangement of four letters in four labelled envelopes puts no letter in its own envelope. Use inclusion–exclusion to count them.
Show answerHide answer
- 50 + 33 + 20-16-10-6 + 3 = 74, using ⌊100/6⌋ = 16, ⌊100/10⌋ = 10, ⌊100/15⌋ = 6 and ⌊100/30⌋ = 3.
- Arrangements with at least one letter in its own envelope: (4 choose 1) 3!-(4 choose 2) 2! + (4 choose 3) 1!-(4 choose 4) 0! = 24-12 + 4-1 = 15. So there are 24-15 = 9 derangements.
Combine the two principles
An upper limit on each box breaks the stars-and-bars bijection. Count without the limit, then use inclusion–exclusion to remove the distributions that break it.
Worked example 3
Boxes that hold at most four
Worked example 3
Boxes that hold at most four
Find the number of solutions of x₁ + x₂ + x₃ = 10 in integers with 0 ≤ xᵢ ≤ 4 for each i.
Show full solutionHide solution
Count without the upper limit
Method
Stars and bars with 10 objects and 3 boxes.Reason
This is the total from which the bad cases are removed.Working
Answer
(12 choose 2) = 66.Count the overfull cases
Method
Let Aᵢ be the set of solutions with xᵢ ≥ 5.Reason
Putting 5 in box i first and sharing the rest is a bijection, so each Aᵢ is a stars-and-bars count.Working
Answer
|Aᵢ| = ((5 + 2) choose 2) = 21. Two boxes with at least 5 each use all 10, so |Aᵢ∩ Aⱼ| = 1, and three overfull boxes are impossible.
Apply inclusion–exclusion
Working
Answer
66-|A₁∪ A₂∪ A₃| = 66-(3 × 21-3 × 1 + 0); = 66-60 = 6.
Quick check
Listing confirms it: the solutions are the arrangements of (4,4,2) and of (4,3,3), three of each. With larger numbers listing is impractical, but the method is unchanged.
Common mistakes
- Using stars and bars for distinguishable objects. Ten different books in four boxes give 4¹⁰ arrangements, not (13 choose 3).
- Forgetting to shift a lower limit: “at least one in each box” first removes one object per box.
- Describing a pairing without checking that it is reversible, so that two objects may be matched with the same image.
- Stopping inclusion–exclusion after the subtraction, which leaves elements in all three sets uncounted.
- Treating |Aᵢ∩ Aⱼ| as |Aᵢ| |Aⱼ|. Intersections must be counted directly.
Before you move on
Check your understanding 3
Four dice adding to twelve
Check your understanding 3
Four dice adding to twelve
Find the number of solutions of a + b + c + d = 12 in integers with 0 ≤ a,b,c,d ≤ 5.
Show answerHide answer
Without limits there are (15 choose 3) = 455 solutions. A variable at least 6 leaves 6 to share: (9 choose 3) = 84 for each of the 4 variables. Two variables at least 6 use all 12: 1 way for each of the (4 choose 2) = 6 pairs. Three cannot exceed 5 together. So
This also counts the ways four dice, each showing 1 to 6, can total 16, since a = score-1 and so on.
Loading reading progress…
Lesson done
- Monday
- Tuesday
- Wednesday
- Thursday
- Friday
- Saturday
- Sunday
Checking learning on this device…
Change goal
Progress options
Loading questions…