🎲

Counting Principles

Multiplication principle, addition principle, inclusion-exclusion, and pigeonhole

Key Concepts
  • Addition principle (disjoint cases) and multiplication principle (independent choices)
  • Inclusion–exclusion handles overlapping sets
  • The pigeonhole principle proves existence
  • Counting the complement is often easier
Important Formulae
Inclusion–exclusion |A∪B| = |A| + |B| − |A∩B|
Pigeonhole n items in k boxes ⇒ some box has ≥ ⌈n/k⌉
Quick Tips
  • If direct counting is hard, count the complement and subtract.
  • Use the pigeonhole principle whenever a problem asks to prove something must exist.
Sample Practice Questions

  1. Out of 52 cards, the number of ways to choose 5 cards is:

    • 52 × 51 × 50 × 49 × 48
    • C(52,5) = 2598960
    • 52!/5
    • 52^5
    Show answer

    Answer: C(52,5) = 2598960

  2. The inclusion-exclusion principle for |A ∪ B| = ?

    • |A| + |B|
    • |A| - |B| + |A ∩ B|
    • |A| + |B| - |A ∩ B|
    • |A| × |B|
    Show answer

    Answer: |A| + |B| - |A ∩ B|

  3. Double counting: how many 1s in all binary strings of length n?

    • 2^n
    • n × 2^n
    • n × 2^(n-1)
    • 2^n/2
    Show answer

    Answer: n × 2^(n-1)

  4. How many arrangements of the letters in MISSISSIPPI are there?

    • 11!
    • 11!/4!
    • 11!/(4!4!2!)
    • 11!/4!4!
    Show answer

    Answer: 11!/(4!4!2!) = 34650

Practise more questions →
Practice Questions

Practise PRMO questions on Counting Principles. Answers are revealed after each question.

Start Practice →
Combinatorics