Bijective proof? Examples?

Question

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.

Answer 1

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$ as $\left\{i : s_i = 1\right\}$.
• 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 (which may and may not be distinct). 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:

• Pick a bijection between the vertices of $T$ and $[n]$. This induces a bijection between linear orderings of any subset $S$ of the vertices of $T$ and permutations of $S$.
• 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. From the previous step, we get a permutation $\pi$ of the vertices of $P$. The action of $f$ of these vertices is that of $\pi$.
• 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.

Answer 2

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.