Counting Without Listing: Bijections, Double Counting and Inclusion–Exclusion
Combinatorics is not enumeration. It is finding a structure that turns a messy count into a clean product, a symmetry, or two counts of the same thing.
Olympiad Desk · Core Learning
What you will take away
- A bijection proves two sets are the same size without counting either one
- Double counting: count the same collection two ways and equate the totals
- Inclusion–exclusion handles "at least one" conditions
- Complementary counting is usually shorter than direct counting
Bijections
If you can pair every object of a hard set with an object of an easy set, the hard set has the same size. Subsets of an n-element set pair with binary strings of length n; compositions pair with arrangements of sticks and stars; monotone lattice paths pair with strings of steps.
Double counting
Count incidences (edge–vertex pairs, person–handshake pairs, flag–flag pairs) twice: once by grouping on one side, once on the other. Equating the two expressions often yields the identity the problem is asking for, with no algebra required.
Worked problems
- 1
How many subsets does a set with n elements have?
Show hint
Pair each subset with a string of n yes/no decisions.
Show solution
Each element is either in the subset or not: 2 independent choices per element, so there are 2ⁿ binary strings of length n, and pairing subset ↔ string is a bijection.
Answer: 2ⁿ subsets.
- 2
In a group of 40 people, prove that the number of people who know an odd number of other people in the group is even.
Show hint
Sum all degrees and count the edges twice.
Show solution
The sum of all degrees is 2 · #pairs, which is even. The sum of an even total of degrees splits into the odd-degree people and the even-degree people; the even-degree part contributes an even amount, so the odd-degree part must also sum to an even number — which means it contains an even number of people.
Answer: There is an even number of people with an odd number of acquaintances.
