Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 36 ยท Getting Started

Bijections and Double Counting

Learn two core proof ideas of counting: matching sets one-to-one with a bijection, and counting the same set in two ways, with handshake and binary string examples.

Two ideas show up in almost every combinatorial argument. The first is the bijection: to count a hard set, match it perfectly with an easy set of the same size. The second is double counting: count one collection in two different ways, and conclude the two answers are equal. This lesson explains both with small examples you can check in Python.

Bijections

A function f from set A to set B is a bijection if every element of B is hit by exactly one element of A. If such a function exists, |A| = |B|. You do not need to count A directly: count B instead.

Example: how many subsets does {1, 2, 3} have? Match each subset with a 3-bit binary string, where bit i is 1 when element i is inside. The subset {1, 3} becomes 101. Each subset gives exactly one string, and each string gives exactly one subset. So the number of subsets equals the number of 3-bit strings, which is 2^3 = 8.

Python Subsets and binary strings are in bijection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The round trip check (subset_to_bits(bits_to_subset(b)) == b) is precisely what "bijection" means: you can go back and forth without losing anything.

Another bijection: paths on a grid

How many routes go from the corner (0, 0) to (3, 2) moving only right (R) or up (U)? Every route is a word with three R's and two U's, such as RRUUR. That word is a choice of which 2 of 5 positions hold the U's. We will count it as "5 choose 2" later, but the idea is the bijection: routes correspond to such words.

Python Grid routes as words

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Double counting

To double count, pick a set of pairs and count it by summing along rows and then along columns. Both totals are the same set of pairs, so they agree.

The classic example is the handshake lemma. In a group of people, add up how many hands each person shakes. Every handshake involves two people, so it is counted twice: the sum of everyone's handshake counts equals 2 times the number of handshakes. Therefore that sum is always even, which means the number of people who shake an odd number of hands is even.

Python The handshake lemma

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second printed number is always twice the first, whatever the random seed.

Double counting to find a formula

Double counting also derives formulas. How many handshakes if everyone shakes everyone else's hand once, among n people? Each person shakes n - 1 hands. The degree sum is n(n - 1), and every handshake is counted twice, so the number of handshakes is n(n - 1) / 2. This is the number of 2-subsets, "n choose 2".

flowchart TD
    Q["Count handshakes<br/>among n people"] --> A["Sum each person's hands<br/>n x (n-1)"]
    A --> B["Each handshake appears twice"]
    B --> R["Answer: n(n-1)/2"]

One count of the pairs gives a sum, the other tells you the factor of two.

Python Handshake formula versus listing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a formula feels like it has "too many" objects by a constant factor, ask what each real object is counted as. Dividing by that factor is called the division rule; see Counting Functions and Subsets and Permutations with Repeated Items.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. If there is a bijection from A to B, what follows?

    A perfect one-to-one matching means both sets have the same number of elements.
  2. 2. How many right/up routes go from (0,0) to (2,2)?

    Words with two R's and two U's: choose which 2 of 4 positions are U, which is 6.
  3. 3. In a party of 5 where everyone shakes everyone's hand once, how many handshakes occur?

    5 x 4 / 2 = 10.
  4. 4. Why must the number of people with an odd number of handshakes be even?

    The total is even. A sum of numbers is even only if an even number of the terms are odd.

Summary

  • A bijection between two sets proves they have the same size, so count the easier one.
  • Double counting totals one collection in two ways and equates the results.
  • The handshake lemma: degrees sum to twice the number of handshakes.
  • Always verify the matching in both directions.

Next: The Sum Rule