Quick description
There is a bijection between two finite sets if and only if they have the same number of elements. Many [seemingly] difficult to count sets can easily be counted by mapping them bijectively to sets which are [seemingly] simpler to count.
A bijection can also be referred to as a change of variable.
This is a very general idea and the main problem solving technique it suggests is this: if a set appears difficult to count, try to find a representation of it that is easier to count.
Prerequisites
Basic mathematical notation.
Example 1
(William Feller, Probability Theory, Vol I, Third edition).
Let be a finite set and let
be unordered strings of length
from this alphabet.♦ For a string
, let
be the number of times
appears in
. We can represent
with a distribution of
identical balls into
cells by putting
balls into cell
. Each of these distributions, in their turn, can be uniquely represented by a string of length
from the alphabet
with
's and
's and which start and end with
. The
's represent the identical balls and the
's the walls of cells. Let's denote the set of all strings of this form with
.
Here is an example: for and
the string

is represented by the string

It is clear that and
can be mapped bijectively.
is very simple to count using multiplication and partitioning:

Therefore, we have that

Example 2
The reflection principle. (William Feller, Probability Theory, Third Edition, Chapter III). Let . Let
be the coordinate maps.◊ Define

for and
and
. For
,
can be thought
of as a trajectory of a process taking values in
, which starts
from
, and at each discrete time step goes either up or down by
.
Let us fix and consider the set
of trajectories that end up at position
at their
step which also visit the origin in their excursion. In other words

Knowing the size of this set allows one to compute, among other things, the distribution of the first hitting time to a state as well as the last exit from a state of a symmetric random walk. The weak limits of these distributions under proper scaling gives the distributions of the same random variables for the Brownian motion. These in turn can be used to compute distributions of analogous quantities for more complicated processes derived from these simpler ones. Thus knowing the size of the set is useful and interesting. However, defined as is, the set is not simple to count because it involves a complicated constraint (at least to the human mind), i.e., that each trajectory being counted has to hit the origin. We will now map
bijectively to a simpler set
with no constraints and which is simple to count.
We set , and define
to be the set of trajectories that hit level
at step
.
is a set of the same type as
, except that there are no constraints on it.
Now let us define the bijection that will map to
. Let
be the map that reflects
along the time axis upto the first time it hits the origin. That is, for
let
be the first time
and define
as

The following figure shows the action of on a sample path.
It follows directly from its definition that is a bijection from
to
.
One can count as follows. For any path
let
be the number of
steps and
be the number of
steps in
. By
's definition
and
is the same for all paths in
and they satisfy

The number of paths in is then

if is even, and zero otherwise.
Because
is bijectively mapped to
with
, the binomial coefficient in the last display also gives
.
General discussion
Using a change of variable to simplify a counting problem is a special case of the general idea of using a change of variable to translate one problem to another.
Comments
Inline comments
The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.
Surely you are counting
Tue, 21/04/2009 - 15:42 — gowersSurely you are counting unordered strings here?
ordered/unordered
Tue, 21/04/2009 - 16:01 — devinThanks for the comment and sorry for the confusion. What I meant was "sorted". We can use `unordered', if "sorted" is confusing/ not standard. Thanks again.
Inline comments
The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.
Incorrect Image
Fri, 08/05/2015 - 16:41 — arrowThe image of each X_i ought to be {-1, 1}, I think.