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

### 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 - 16:42 — gowersSurely you are counting

unordered strings here?## ordered/unordered

Tue, 21/04/2009 - 17: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 - 17:41 — arrowThe image of each X_i ought to be {-1, 1}, I think.