Tricki
a repository of mathematical know-how

Revision of Bijections and counting from Tue, 21/04/2009 - 23:13

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

 1112235

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. (William Feller, Probability Theory, Third Edition, Chapter III). 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 = x \in {\mathbb N}. 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 x, and at each discrete time step goes either up or down by 1.

Let us fix x >0 and consider the set Z of trajectories that end up at position a>0 at their n^{th} step which also visit the origin in their excursion. In other words

 S_n(\omega) = a, S_k(\omega) = 0 \text{ for some } k < n\}.

Knowing the size of this set allows one to compute, among other things, the distribution of the first hitting time to a state as well as the last exit from a state of a symmetric random walk. The weak limits of these distributions under proper scaling gives the distributions of the same random variables for the Brownian motion. These in turn can be used to compute distributions of analogous quantities for more complicated processes derived from these simpler ones. Thus knowing the size of the set Z is useful and interesting. However, defined as is, the set is not simple to count because it involves a complicated constraint (at least to the human mind), i.e., that each trajectory being counted has to hit the origin. We will now map Z bijectively to a simpler set Z' with no constraints and which is simple to count.

If we set S_0 = -x < 0 , define Z' to be the set of trajectories that hit level a at step n. Note that Z' is a set of the same type as Z, except that there are no constraints on it. Define  Z \rightarrow Z' as follows. For \omega \in Z we know that there is a k < n with

Let R be the map that reflects \omega along the time axis upto the first time it hits the origin. That is, for \omega \in Z let k be the first time x + \sum_{i=1}^k X_i(\omega) = 0 and define R as

 R(\omega) = \omega'

where

 \omega'_i =\begin{cases} -\omega_i,&~ i \le k,\\                           \omega'_i,&~  i > k$. \end{cases}
It follows directly from its definition that </div><p><span class=R" /> is a bijection from Z to Z'. The following figure shows visually the action of R on a sample path. The reflection principle

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

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.

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.