Bijections and counting

a repository of mathematical know-how

Bijections and counting

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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]
(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.<comment thread="191" /> 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
[maths]
1112235
[/maths]
is represented by the string
[maths]
|***|**|*||*|
[/maths]

It is clear that $\Omega$ and $\Omega'$ can be mapped bijectively. $\Omega'$ is very simple to count using multiplication and partitioning:
[maths]
|\Omega'| = \binom{n+k -1}{k}.
[/maths]
Therefore, we have that
[maths]
|\Omega| = \binom{n+k -1}{k}.
[/maths]

[EXAMPLE]
The reflection principle. (William Feller, Probability Theory, Third Edition, Chapter III). Let $\Omega = \{-1,1\}^n$. Let $X_i : \Omega\rightarrow \{0,1\}$ be the coordinate maps.<comment thread="1270" /> Define
[maths]
S_k: \Omega\rightarrow {\mathbb N},~~ S_k(\omega) = S_{k-1}(\omega) + X_k(\omega), 
[/maths]
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 
[maths]
Z = \{\omega \in \Omega: S_n(\omega) = a, S_k(\omega) = 0 \text{ for some } k < n\}.
[/maths]
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
[maths]
R(\omega) = \omega',~~~
\omega'_i =\begin{cases} -\omega_i,&~ i \le k,\\
                          \omega_i,&~  i > k.
\end{cases}
[/maths]
The following figure shows  the action of $R$ on a sample path.

<br />
[image rw_reflection_hr.jpg]
<br />

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
[maths]
p+ r = n, ~~~ p -r = a+x.
[/maths]
The number of paths in $Z'$ is then
[maths]
|Z'| = \binom{n}{(n+a+x)/2}
[/maths]
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.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

	Delete	List	Description	Weight	Size
			/images/rw_reflection_hr.jpg		22.42 KB

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Bijections and counting

Recent articles

Active forum topics

Recent comments