a repository of mathematical know-how

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

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.


Basic mathematical notation.

Example 1

(William Feller, Probability Theory, Vol I, Third edition). Let \Omega_0=\{1,2,3,...,n\} be a finite set and let \Omega be ordered strings of length k from this alphabet. For a string s\in\Omega, let c_i be the number of times i \in \Omega_0 appears in s. We can represent s from \Omega by a distribution of k identical balls into n cells by putting c_i balls into cell i. Each of these distributions, in their turn, can be uniquely represented by a string of length n+k+1 from the alphabet \{|,*\} with n+1 |'s and k *'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 \Omega'.

Here is an example: for k=7 and n=5 the string


is represented with the string


It is clear that \Omega and \Omega' can be mapped bijectively. \Omega' is very simple to count using multiplication and partitioning:

 |\Omega'| = \binom{n+k -1}{k}.

Therefore, we have that

 |\Omega| = \binom{n+k -1}{k}.

Example 2

The reflection principle. Let \Omega = \{-1,1\}^n. Let  \Omega\rightarrow \{0,1\} be the coordinate maps. Define

 \Omega\rightarrow {\mathbb N},~~ S_k(\omega) = S_{k-1}(\omega) + X_k(\omega),

. for k \in {1,2,3..,n} and and S_0 = 0. For \omega \in \Omega, S_0(\omega), S_1(\omega),...,S_n(\omega) can be thought of as a trajectory of a process taking values in {\mathbb N}, which starts from 0, and at each discrete time step goes either up or down by 1. \Omega has 2^n 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 0?

Using several simple ideas (partitioning, and writing the set of interest as a disjoint union) this question can be reduced to the following:

Set S_0 = 1. Let Z be those trajectories such that S_n(\omega) = a  >0 and such that S_k(\omega) > 0 for all k \le n. What is |Z|?

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.


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

Surely you are counting unordered strings here?


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.

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

The image of each X_i ought to be {-1, 1}, I think.