Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell into this category (but now see arXiv:0910.3442v1). Many unimodality results also fall into this category. Do you know of any other results of this kind, especially results that look frustratingly like they ought to have simple combinatorial proofs?
For the purposes of this question, "combinatorial result" should be interpreted as meaning some kind of exact enumeration, and "combinatorial proof" should be interpreted as meaning, more or less, "bijective proof." (So for example I am not interested in bounds on Ramsey numbers.)
Best Answer
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.