# Combinatorial results without known combinatorial proofs

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

-
Does enumerating Young tableaux of a given format count? Knuth volume 3 states that there is no simple proof for that result. –  Zsbán Ambrus Oct 9 '10 at 10:38
@Zsbán: If you mean the hook-length formula, then there is now a proof by Novelli, Pak, and Stoyanovskii that is as good a bijective proof as one can hope for. –  Timothy Chow Jan 7 '11 at 18:47

Warning: this used to be a great example, but I'm afraid it no longer is.

Let $H(n)$ be the number of horizontally-convex polyominoes in the plane, where "horizontally convex" means just what you think it means, and equivalence is just up to translations (so mirror images and rotations are considered distinct). Using a sequence of manipulations with two-variable generating functions and an amazing amount of cancellation, one finds that

$H(n) = 5H(n-1) - 7H(n-2) + 4H(n-3)$.

I learned this from Gil Kalai in 1991 (and the result is much older), and I'm quite sure there was no known combinatorial proof of this surprising result for a while. However fairly recently Dean Hickerson found one. I'm sure Dean thought that this looks frustratingly like something that ought to have a combinatorial proof, and then he proceeded to resolve this frustration in the only possible way.

-

Some "positivity results" can only be proven using heavy geometric machinery at the moment. The most prominent one is positivity of the coefficients of Kazhdan-Lusztig polynomials (in the case of Weyl groups).

-

The book Proofs that Really Count: The Art of Combinatorial Proof, by Art Benjamin and Jenny Quinn, contains a large number of combinatorial identities with no known combinatorial proof. (See the end of most of the chapters.) As the subtitle indicates, it is also a great reference for those interested in combinatorial proof techniques.

-

One result I like is that the number of 321-avoiding permutations of length 2n whose matrices are 180°-symmetric is (2n choose n). The best proof I know is fairly short, but I wouldn't call it bijective:

Under the Robinson-Schensted correspondence, the 180°-symmetric permutations are exactly the ones which map to ordered pairs of self-evacuating tableaux, which are in turn in bijection with ordered pairs of domino tableaux in the same shape. (See Stembridge) Now, if you look at the 2-row (since our permutations must be 321-avoiding) domino tableaux of size 2n, there are n+1 Ferrers shapes they can take, and they can be formed from those of size 2n-2 in a way satisfying the relation in Pascal's triangle, so the sum over all 2-row Ferrers shapes of the square of the number of domino tableaux of that shape is the sum of the squares of the binomial coefficients (2n choose i), yielding (2n choose n).

I've tried to "unpack" each of these steps into a simple bijection, but nothing's budged. Still, it seems like the kind of problem that someone else might be able to solve.

-

Atiyah conjecture for free groups. It has been proved by Peter Linnel using some operator-algebraic technique, but the statement seems to me to be ultimately combinatorial.

For example, as an important special case there is the analytical 0-divisors conjecture: Let T be a self-adjoint element of the complex group ring of a free group of $l^2$-norm at most 1. Consider the sequence $t_n$ of complex numbers: $t_n$ is the coefficient of the neutral element of the element $(1-T)^n$ of the group ring (so this is a combinatorial thing.)

One of the formulations of the analytical 0-divisors conjecture is the following theorem.

Theorem (P. Linnel): If T is not 0 then the limit of the sequence $t_n$ is 0.

Similarly for many other groups for which Atiyah conjecture is known. For example, the proof for elementary amenable group (again Linnel) uses deep K-theory, but admittedly it might be that this deep K-theory is proven using combinatorics.

-

PROBLEM Of splitting a necklace between two thieves:

Two thieves want to share equally the stones of a necklace ( an open circle).
The necklace has $s$ types of stones ( each type of stone appears an even number of time.).

They want to minimize the number of cuts ( the link are costly and they do not want to make a mess of it).
Show that it is always possible to achieve the split using $s$ cuts.

SOLUTIONS:

For $s=2$ a combinatorial solution is not too difficult.

For any $s$, a topological/linear algebra proof exists ( a nice exposition by Jiri Matousek in reference below.)

http://www.amazon.com/Using-Borsuk-Ulam-Theorem-Combinatorics-Universitext/dp/3540003622

Though by now there seem to be a combinatorial proof.
AT : http://www.combinatorics.org/Volume_16/PDF/v16i1r79.pdf

Yet I believe it might be of interest as a problem that had no combinatorial proof for a while.

-

The following statement seems to not have clear combinatorial proof (or at least it did not in 2003, when I heard of it):

Denote by L(n) the set of all partitions of n into distinct parts with the smallest part being odd. Let L_o(n), L_e(n) be the subsets of L(n) consisting of partitions into odd and even number of parts respectively. Then |L_o(n)|-|L_e(n)| is 0 if n is not a perfect square, and is (-1)^n if n is a perfect square.

-
COuld you please clarify this statement? To me, a "partition into even parts" would be a partition whose parts are even, but there are not many of those whose smallest part is odd. –  Hugh Thomas Nov 14 '09 at 17:46
@Hugh: edited: what I meant was "partitions into odd/even number of parts". Sorry - today is my official misprint day. –  Vladimir Dotsenko Nov 14 '09 at 18:36
@Vladimir: thanks. I wondered if that was what you meant, but couldn't get it to work our correctly for n=5. The partitions in L(5) into an even number of parts seem to be 41, 2111; while those with an odd number of parts seem to be 5, 311, 221, 11111. Can you explain? –  Hugh Thomas Nov 15 '09 at 14:56
@Hugh - I hope it's finally correct - with partitions of distinct parts. For example, in the case of 5 what we have is 41 vs 5, in the case of 6 - 51 vs 321, in the case of 7 - 7 and 421 vs 61 and 43 etc. –  Vladimir Dotsenko Nov 16 '09 at 15:26

The Graham-Pollak Theorem states that the minimum number of complete bipartite graphs needed to disjointly cover the edge set of the complete graph on n vertices is n-1. The only known proofs all use linear algebra, and there is no pure counting proof is known as far as I know. There is a chapter about this in Aigner and Ziegler's Proofs from the BOOK.

-
Perhaps I haven't had enough coffee this morning. I certainly don't have access to Signer and Ziegler's book. Anyway, where is the linear algebra in the following? Base case n=1 : m(n)=0 follows by inspection as there are no edges. More generally, extract Ka,b from Ka+b, then m(a+b) is bounded above by (and must be equal for at least one pair a,b) 1 + m(a) + m(b), giving the additional result of equality using any pair (a,b). If the linear algebra is hiding in the addition, I don't see it. –  Gerhard Paseman Mar 24 '12 at 17:47
I should insist on a and b being positive integers as above. Gerhard "I Forgot My Signature Too!" Paseman, 2012.03.24 –  Gerhard Paseman Mar 24 '12 at 17:50
I believe the linear algebra part isn't showing that $m(n)≤n−1$, but showing that you can't do it with fewer. –  Kevin P. Costello Mar 24 '12 at 20:30
Yes, but the cool part about the above sketch is that there is a minimum decomposition which is of the form suggested above, with minimum value 1 + m(a) +m(b), and strong induction carries the day. Again, where is the linear algebra? Or do I need to be more explicit about the lower bound? Gerhard "Ask Me About System Design" Paseman, 2012.03.24 –  Gerhard Paseman Mar 25 '12 at 2:59
Ah. I get it now. I cannot prove yet that one of the pieces in a minimal decomposition must be of the form Ka,b when I start with the complete graph on a+b vertices. Although I might be able to prove that by an edge count, I do not see it yet. OK. Gerhard "Back To The Drawing Board" Paseman, 2012.03.24 –  Gerhard Paseman Mar 25 '12 at 3:02

This is a very common theme in enumerative combinatorics. You can find a lot of examples with the Google search "no bijective proof" (with quotes).

First, I can say something about why you might care about bijective proofs. Combinatorial species are certainly a nice theory, but they are a fairly specific and elaborate answer related to generating functions. A more general reason is that a bijective proof categorifies an equality in combinatorics to the category of sets. In other words, it promotes an equality $|A| = |B|$ to an isomorphism $A \cong B$. In my opinion, it is just as important to find any other categorification, for instance to the category of vector spaces. Instead of showing that two sets are the same size with a bijection, you would show that they are the same size using an invertible matrix.

Second, of the many examples, I can name one that I encountered. This example is interesting because the objects in question seem very similar. Recall that an alternating sign matrix is a matrix whose non-zero entries in each row and column alternate between $1$ and $-1$, and such that the first and last non-zero entry in each row and column is $1$. One interesting subclass is the ASMs of order $2n+1$ which are symmetric about a vertical line. Another interesting subclass is the ASMs of order $2n$ which are diagonally symmetric and have 0s on the diagonal. (ASMs of either type of the opposite parity do not exist.) The first class was discovered by David Robbins and I found the second class. I proved David's product formula for the first class and I established the same product formula for the second class. So these two classes of ASMs are equinumerous, but no bijective proof is known.

Here is another interesting example in the same vein. A cyclically symmetric, self-complementary plane partition (CSSCPP) is equivalent to a tiling of a regular hexagon of order $2n$ by unit lozenges, which is invariant under 60 degree rotation. Here a unit lozenge is two unit equilateral triangles stuck together. A totally symmetric, self-complementary plane partition (TSSCPP) is the same thing except with full dihedral symmetry. (I make the size even because otherwise there aren't any plane partitions with the imposed symmetry.) The formulas for both classes were also conjectured by David Robbins; George Andrews proved his conjecture for TSSCPPs and I proved the conjecture for CSSCPPs. In particular, the number CSSCPPs of a fixed size is the square of the number of TSSCPPs, but no one knows a good bijection.

The single most striking thing that David Robbins found was that the number of TSSCPPs, which are plane partitions with full symmetry, equals the number of ASMs with no imposed symmetry. No bijective proof of that is known either. On the positive side, Doron Zeilberger's proof of the ASM conjecture, and his later paper on refined ASMs, could be steps towards one because they equate certain generalizations and refined enumerations. However, alternating-sign matrices look totally different from plane partitions. In my opinion, the most frustrating case is when we can't even match like to like.

-
Apropos of Greg's first point: there are such things as "linear species", which are functors from B = (finite sets + bijections) to Vect. Any linear species has a generating function, as long as it takes values in finite-dimensional vector spaces. So the theory of species allows you to categorify the theory of generating functions not just in the set-theoretic sense of categorification, but also in the linear sense. Also: I don't know why you use the word "elaborate": what could be simpler than the definition of species? –  Tom Leinster Nov 15 '09 at 2:04
The theory of species is more elaborate than the definition of a species. For instance, the description of "basic" operations on species in Wikipedia could be called elaborate. I guess my real point is that species seem intended as a categorification of generating function methods, which is fine, but not all combinatorial objects fit well into that framework. –  Greg Kuperberg Nov 15 '09 at 2:49

The number of (isomorphism classes of) self complementary graphs on n vertices is the difference between the number of graphs on n vertices with an odd number of edges and the number with an even number of edges.

This is relatively easy to prove with counting arguments, but I'd love to have a combinatorial proof of this...

-
But surely "counting arguments" is combinatorial. Do you mean you want a bijective proof? –  Emil Nov 16 '09 at 10:42
Yes, I wasn't really clear. The proof I know uses Polya theory and so you just set up the equations and the numbers magically come out the same on both sides. So it is just algebraic manipulation, rather than anything else. Therefore I'd like something bijective or at least a natural interpretation of this difference. –  Gordon Royle Nov 16 '09 at 13:11

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.

-
On the other hand, I tend to think that most people would say there IS a "bijective proof" of the fact that the number of linear orders agrees with the number of permutations, though there's no canonical bijection. You might say that the former is a torsor for the latter; is there a good way to express this in species language? –  JSE Nov 14 '09 at 3:07
I'm not used to talking about species, bu the fact that L is a torsor for P should be restatable as saying that LxL is canonically isomorphic to LxP. –  Alison Miller Nov 14 '09 at 6:47
A (canonical) combinatorial proof that |L(X)|=|P(X)|: consider sets already decorated with a linear order. Then new (unrelated) linear orders on these sets are in canonical 1-1 correspondence with permutations taking the old order to the new one, so |L(X)|*#decorations = |P(X)|*#decorations, and dividing both sides by the number of decorations gives the result. –  David Eppstein Nov 14 '09 at 8:29
This is a decategorification of Alison's definition of torsor above! –  JSE Nov 14 '09 at 19:55
JSE and Alison: one way to express the torsor property is that the species LxL and LxP are isomorphic (in a particular way). All you have to do to prove this is check that some naturality squares commute. David: indeed, but note that in order to "divide both sides by the number of decorations [of X by linear orders]", you need to know that there exists a linear order on X. This is true, but you can't canonically exhibit one. –  Tom Leinster Nov 15 '09 at 2:53

For example, according to Stanley the identity $n \cdot \text{pp}(n) = \sum_{i=1}^{n} \sigma_2(i) \text{pp}(n-i)$ has no known bijective proof, where $\text{pp}(n)$ denotes the number of plane partitions of $n$.

-
IINM, there's also no known bijective proof of the fact that pp(n) is the number of partitions of n into 1 type of size 1, 2 types of size 2, etc. (Is that equivalent to the above recursion? Feeling too lazy to check right now.) Or equivalently that it's the number of functions on an n-set up to permutation of the underlying set. –  Harry Altman Oct 8 '10 at 1:12