Tricki
a repository of mathematical know-how

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

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}.

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.