Combinatorics - IOQM Study Guide
Combinatorics on IOQM tests counting with structure: arrangements, selections, inclusion–exclusion, pigeonhole, bijections, and simple recurrences. The answer is an exact count, and because IOQM answers are two-digit integers 00–99, a correct count must be converted carefully.
Core rules and concepts
- Decide first whether order matters and whether repetition is allowed.
- Stars and bars: positive solutions of x1+...+xk=n number C(n−1,k−1); nonnegative solutions number C(n+k−1,k−1).
- Inclusion–exclusion: count unions by adding singles, subtracting pairs, adding the triple intersection.
- Count the complement for “at least one” conditions.
- Pigeonhole: n+1 objects in n boxes forces a collision; identify the boxes, not the objects.
- A bijection can replace a hard count by a standard one.
Worked example
How many integers from 1 to 100 are divisible by neither 2 nor 3? Multiples of 2: ⌊100/2⌋=50. Multiples of 3: ⌊100/3⌋=33. Multiples of both, i.e. of 6: ⌊100/6⌋=16. By inclusion–exclusion, the number divisible by 2 or 3 is 50+33−16=67. Therefore the number divisible by neither is 100−67=33. Enter 33.
Traps that cost marks
- Counting ordered arrangements when the problem asks for subsets.
- Treating identical objects as distinct.
- Forgetting to add back the triple intersection in inclusion–exclusion.
- Using pigeonhole without the worst-case arrangement.
- For circular arrangements, forgetting the (n−1)! reduction.