Tricki

## Bijections and counting

### 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.

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

Surely you are counting unordered strings here?

### ordered/unordered

Thanks 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.