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

### Example 2

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

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