Double Counting

Combinatorics · Axiom Academy

A powerful technique for proving identities and solving counting problems The double counting principle states: If you count the same collection of objects in two different ways, you must get the same answer. This seemingly obvious fact becomes a powerful tool for proving identities. Let's visualize this with a simple example of counting dots arranged in a grid. 2. Example: Counting Handshakes Consider a party with n people where everyone shakes hands with everyone else exactly once. How many handshakes occur? Method 1 (Combinations): We're choosing 2 people from n people, so there are C( n , 2) handshakes. Method 2 (Sum by person): Each person shakes hands with n -1 others. That's n ( n -1) total, but we've counted each handshake twice (once for each person involved), so we divide by 2. Both methods count the same handshakes, proving this fundamental identity! 3. Proving Combinatorial Identities Double counting can prove identities that would be tedious to verify algebraically. Consider: Combinatorial Proof: Count the ways to choose a committee of k people from n people and designate one as the chair. Method 1: Choose k people (C( n , k ) ways), then choose the chair from the k selected ( k ways). Total: k · C( n , k ) Method 2: First choose the chair from all n people ( n ways), then choose the remaining k -1 members from the remaining n -1 people (C( n -1, k -1) ways). Total: n · C( n -1, k -1) 4. Algebraic vs. Combinatorial Proofs

This is the written version of the interactive lesson above. See the full Combinatorics course.