Discrete Mathematics and Combinatorics
Discrete Mathematics and Combinatorics tests counting, arrangements, selections and recurrence-style reasoning. Expect permutations with restrictions, combinations, inclusion-exclusion and pigeonhole arguments.
Core rules
- Permutations order; combinations do not. nPr=n!/(n-r)!, nCr=n!/(r!(n-r)!).
- Identical objects: divide by the factorial of each repeat count.
- 'At least one' often equals total minus none. Inclusion-exclusion: |A∪B|=|A|+|B|-|A∩B|.
- Circular arrangements of n distinct objects: (n-1)!; reflections reduce further only if the question identifies mirror images.
- Pigeonhole: if n items go into m boxes and n>m, some box has at least two.
Worked example
Arrange the letters of MISSISSIPPI. The counts are M1, I4, S4, P2, with 11 letters total. The number of distinct arrangements is 11!/(4!4!2!) = 34650. Dividing removes overcounting from identical I, S and P letters.
Traps
Counting identical letters as distinct; using permutations when choosing a committee; forgetting overcount in circular cases; missing the complement for 'at least one'; applying pigeonhole without defining the boxes.