siddhartha-gadgil/leanaide/counting-pigeonhole

Skill: Counting, Double Counting, and Pigeonhole

Pre-condition: Apply this skill when a proof concerns finite sets, cardinalities, incidence structures, arrangements, or existence forced by more objects than containers.

Goal: Convert the claim into a finite counting identity, inequality, or pigeonhole conclusion.

Instructions:

1. Identify the Counted Set: Define the finite set, pairs, triples, incidences, paths, colorings, or assignments being counted.
2. Choose Counting Methods:

• Double counting: count the same set in two ways.
• Pigeonhole: define objects, boxes, and the capacity bound.
• Exhaustive count: enumerate finite cases when feasible.

1. Prove Finiteness and Bijections: Justify that the counted objects match the expressions used.
2. Derive the Identity or Inequality: Translate the count into the desired conclusion.
3. For Existence: Explain why a positive count or pigeonhole surplus gives an actual object.

Common Failure Modes:

• Counting ordered objects when the desired expression counts unordered objects.
• Ignoring multiplicity.
• Applying pigeonhole without proving the capacity bound for every box.