Skip to content
Technique

Showing two sets are the same size by pairing

Algebra • Permutations and Combinations

Statement

Let a rule send each member of a finite set to a member of a finite set , and let the same kind of rule send each member of back to the member of it came from. Then the members of and are matched in pairs, one to one, so and have the same number of members. The count itself need not be known.

How to use it

  1. 1To compare two counts without finding either, look for a simple change that turns one kind of object into the other.
  2. 2Check that undoing the change takes you back, so no two objects go to the same place and none is left out.
  3. 3Then the counts are equal; any option saying one is larger, or that one set is empty while the other is not, is wrong.

Worked example

From a group of people, are there more ways to choose people or to choose ?

Step-by-step

  1. 1
    Pair each choice of people with the people left out.

    Why: Leaving out is a simple change that turns one kind of choice into the other.

  2. 2
    Taking the people left out of a choice of gives back the original .

    Why: The change undoes itself, so the pairing is one to one.

  3. 3
    So the two counts are equal: .

Answer

The counts are equal.

Watch out

The rule must work for every member and be reversible. A rule that sends two members to the same place, or misses some, proves nothing about the counts.

Also known as

bijection counting, one-to-one correspondence, pairing argument

Appears in past papers

2017 (I)