Bijections and counting

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 $\Omega_0=\{1,2,3,...,n\}$ be a finite set and let $\Omega$ be unordered 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$ with 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 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 $\Omega'$ .

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

$1112235$

is represented by 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.

We set $S_0 = -x < 0$ , and define $Z'$ to be the set of trajectories that hit level $a$ at step $n$ . $Z'$ is a set of the same type as $Z$ , except that there are no constraints on it.

Now let us define the bijection that will map $Z$ to $Z'$ . 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',~~~ \omega'_i =\begin{cases} -\omega_i,&~ i \le k,\\ \omega_i,&~ i > k. \end{cases}$

The following figure shows the action of $R$ on a sample path.

It follows directly from its definition that $R$ is a bijection from $Z$ to $Z'$ .

One can count $Z'$ as follows. For any path $\omega' \in Z'$ let $p$ be the number of $+1$ steps and $r$ be the number of $-1$ steps in $\omega'$ . By $Z'$ 's definition $p$ and $r$ is the same for all paths in $Z'$ and they satisfy

$p+ r = n, ~~~ p -r = a+x.$

The number of paths in $Z'$ is then

$|Z'| = \binom{n}{(n+a+x)/2}$

if $n+a+x$ is even, and zero otherwise. Because $Z$ is bijectively mapped to $Z'$ with $R$ , the binomial coefficient in the last display also gives $|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.

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.

view commented text

Surely you are counting

Tue, 21/04/2009 - 15:42 — gowers

Surely you are counting unordered strings here?

ordered/unordered

Tue, 21/04/2009 - 16:01 — devin

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.