Tricki
a repository of mathematical know-how

Revision of Bijections and counting from Tue, 21/04/2009 - 17:15

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 = 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 elementary ideas (partitioning, writing the set of interest as a disjoint union and counting the complement) this question can be reduced to the following problem. Set S_0 = 1.

Let Z be those trajectories such that S_n(\omega) = a  >0 and such that there is a k < n such that S_k(\omega) = 0. What is |Z|?

Z is a complicated set and counting it directly is not simple. We now describe a much simpler set of trajectories to which we will map Z bijectively. Set S_0 = -1. Z' is the set of trajectories such that S_n(\omega) = a. Using partitioning and multiplication one sees that the number of such trajectories is

 \binom{n}{p}

where p is the solution to p-r = a+1 and p+r = n.

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.