Tricki

## Revision of Bijections and counting from Tue, 21/04/2009 - 16:42

### Quick description

If there is a bijection between two finite sets then 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: when trying to count a set that seems complicated check if it has a simpler representation that makes counting easier.

### Prerequisites

Basic mathematical notation.

### Example 1

(William Feller, Probability Theory, Vol I, Third edition). Let be a finite set and let be ordered strings of length from this alphabet. For a string , let be the number of times appears in . We can represent from by 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 with |. The '*'s in 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 with 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. Let . Let be the coordinate maps. Define

. 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 . has elements, each of which can be thought of as a trajectory as just described. A basic question is the following: how many of these trajectories never come back to ?

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