This isn't exactly an answer, but since this is community wiki I hope it's in the spirit of things if I add a twist to the question.
One of the excellent things about the excellent theory of species is that it has at its heart a notion of natural bijective proof. Let me sketch the basic idea. A species is simply a functor from the category
$$
\mathcal{B} = (\mbox{finite sets } + \mbox{ bijections})
$$
to the category of sets. One thinks of a species as a way of decorating a finite set with some extra combinatorial structure. For example, there is a species $L$ defined by
$$
L(X) = \{ \mbox{linear orders on } X\}
$$
for finite sets $X$ (and defined in the obvious way on morphisms). Thus $L(X)$ is the set of ways of "decorating" $X$ with a linear order. Or, there is another species $P$ defined by
$$
P(X) = \{ \mbox{permutations on }X\}
$$
for finite sets $X$ (and defined in the obvious way on morphisms).
You can think of species as categorified generating functions. More exactly, for any species $S$ that is finite (takes values in finite sets), you can form its exponential generating function $\sum_n s_n x^n/n!$, where $s_n$ is the cardinality of $S(X)$ for any $n$-element set $X$. By passing from a species to its generating function (decategorification), you lose some information. I'll give a non-trivial example of this in a moment.
There's an obvious notion of isomorphism of species, namely, natural isomorphism of functors. Are the species $L$ and $P$ above isomorphic? We have $L(X) \cong P(X)$ for all $X$, since an $n$-element set admits both $n!$ linear orders and $n!$ permutations. But you can show that there is no natural isomorphism $L \cong P$. So no, $L$ and $P$ are not isomorphic. The intuition is this: in order to match up permutations and orders, you'd have to choose an order to correspond to the identity permutation; but an abstract finite set carries no canonical linear order, so you'd have to make a random choice. Hence there's no canonical correspondence between them.
In particular, this implies that species with the same generating function ($\sum_n n! x^n/n! = 1/(1-x)$, here) need not be isomorphic. So yes, passing to the generating function can lose information.
Moral: one notion of "bijective proof" is "existence of an isomorphism of species". It's quite a demanding notion, as the permutation/order example shows. One might consider compiling a list of all the pairs of species that have the same generating function but are not isomorphic. This list could usefully be compared to Stanley's list.
The number of pairs $(P,Q)$ of standard Young tableaux of the same shape and with $n$ squares is $n!$.
The number of oscillating tableaux of length $2n$ and empty shape is $1\cdot 3\cdot 5\cdots (2n-1)$.
The number of leaf-labeled complete (unordered) binary trees with $n$ leaves is $1\cdot 3\cdot 5\cdots (2n-3)$ (Schröder's third problem).
The number of compact-rooted directed animals of size $n$ is $3^n$. See MathSciNet MR0956559 (90c:05009).
Let $f(n)$ be the number of $n\times n$ matrices $M=(m_{ij})$ of nonnegative integers with row and column sum vector $(1,3,6,\dots,{n+1\choose 2})$ such that $m_{ij}=0$ if $j>i+1$. Then $f(n)=C_1C_2\cdots C_n$, where $C_i$ is a Catalan number. No combinatorial proof of this result is known. See Exercise 6.C12 on page 38 (solution on page 84) of http://math.mit.edu/~rstan/ec/catadd.pdf
Best Answer