Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having trouble with understanding bijective proofs. I searched a lot, but I could not find a simple and well-explained resource.

Can you give a simple example of a bijective proof with explanation?

Thanks in advance.

share|improve this question
    
Wikipedia Article: en.wikipedia.org/wiki/Bijective_proof –  user21436 Dec 22 '11 at 6:14
2  
Problems to help understanding: www-math.mit.edu/~rstan/bij.pdf –  user21436 Dec 22 '11 at 6:15
add comment

2 Answers

up vote 3 down vote accepted

A bijective proof in combinatorics just means that you transfer one counting problem that seems "difficult" to another "easier" one by putting the two sets into exact correspondence.

Reworded, Ilmari's example (which is really the example) is that we want to count subsets of $[n]$. It is, however, "easier" to count strings over $\{0,1\}$ of length $n$: there are two possibilities for each of $n$ positions, so there are clearly $2^n$ of them. On the other hand:

  • Each string $s$ defines a subset $S$: if $s = s_1s_2\cdots s_n$, define $S$ by ${i : s_1 = 1}$
  • Each subset defines a string: given $S$ define $s$ by $s_i = 1$ if $i\in S$ and $s_i = 0$ otherwise

Since both of these maps are 1-1, we are done.

A more complicated example, which is one of my favorites, is the following proof of Cayley's famous theorem that the number of labeled trees on $n$ vertices is $n^{n-2}$ due to Joyal.

Instead of counting trees, we count "doubly rooted trees" $(T,b,r)$ where $T$ is a tree and $b$ and $r$ are distinguished "blue" and "red" vertices. If the number of trees on $n$ vertices is $N$, then clearly the number of doubly rooted trees is $n^2 N$.

So now we need a set of objects that has size $n^n$ to line up with doubly rooted trees. Again strings come up, this time of length $n$ on $n$ letters. The number of these is $n^n$: there are $n$ choices for each position.

Now we use a bijective argument to count functions from $[n]\to [n]$: these can all be written down as strings of length $n$ on $n$ letters so there are $n^n$ of them as well.

At this point, we've arrived at the main step: doubly rooted trees are in bijective correspondence with functions from $[n]$ to $[n]$. If we have this, we are done, since $n^n/n^2 = n^{n-2}$, which is what we'd set out to prove.

Given a doubly rooted tree $(T,a,b)$, we define a function $f$ as follows:

  • There is a unique path $P$ from $a$ to $b$. Listing out the vertices on this path in order of the walk from $a$ to $b$ we get a linear ordering of these vertices which defines a permutation of them. This defines $f$ on the vertices of $P$.
  • For every other vertex $i$, there is a unique shortest path to a vertex in $P$. We define $f(i)$ to be the next vertex $j$ on this path.

This defines a function, and is clearly $1-1$, since all the choices are determined.

For the other direction, we note that any function from $[n]\to [n]$ is completely defined by:

  • A permutation on its periodic points (i.e., those for which you can repeatedly apply $f$ and get back to the same point)
  • A sequence of non-repeating values $f(i)$, $f(f(i))$, ... $f^j(i)$ for the smallest $j$ such that $f^j(i)$ is periodic

This was exactly the data from a doubly rooted tree, so this map is 1-1 as well, and we're done.

share|improve this answer
add comment

I'm not sure how simple you want, but let's do problem 1 from the list linked to by Kannappan Sampath:

  1. The number of subsets of an $n$-element set is $2^n$.

Proof: Let us assume, for simplicity, that the $n$-element set is $S = \{0, 1, \dotsc, n-1\}$. (By definition, there is a bijection from any other $n$-element set to $S$.) To prove the result, we will construct a bijection from the set $\mathcal P(S)$ of subsets of $S$ to the $2^n$-element set $T = \{0, 1, \dotsc, 2^n-1\}$. In particular, an example of such a bijection is the function $f: \mathcal P(S) \to T$ given by $$f(X) = \sum_{k \in X}\; 2^k.$$

If the definition of $f$ doesn't seem intuitive, it helps to think in terms of binary numbers: the $k$-th bit of $f(X)$ is $1$ if and only if $k \in X$. From this definition, it's not hard to show that

  • a) $X \subseteq S \implies f(X) \in T$,
  • b) $X \ne Y \implies f(X) \ne f(Y)$, and
  • c) for each $i \in T$, there exists a subset $X \subseteq S$ such that $f(X) = i$.

Property (a) shows that $f$ is indeed a function from $\mathcal P(S)$ to $T$, (b) shows that it is injective, and (c) that it is surjective. Together, these imply that $f$ is a bijection from $\mathcal P(S)$ to $T$, which implies that these two sets have the same size, QED.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.