Tricki

## Revision of Bijections and counting from Tue, 21/04/2009 - 15:56

### 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 with [seemingly] simpler structures.

The 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. Each string in can be represented as a string of length from the alphabet with '|''s and '*'s and which start and with '|'. Let's denote this set of strings by . For example, for and the string

is represented with the string

The '*'s in the latter string can be thought of as identical balls and the '|'s as walls of cells. It is clear that and can be mapped bijectively. is very simple to count using multiplication and partitioning:

|\Omega'| = \binom{n+k -1}{n}.
Therefore, we have that
|\Omega| = \binom{n+k -1}{n}.

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