The question. A year ago, on this blog, I investigated Who computed Catalan numbers. Short version: it’s Euler, but many others did a lot of interesting work soon afterwards. I even made a Catalan Numbers Page with many historical and other documents. But I always assumed that the dubious honor of naming them after Eugène Catalan belongs to Netto. However, recently I saw this site which suggested that it was E.T. Bell who named the sequence. This didn’t seem right, as Bell was both a notable combinatorialist and mathematical historian. So I decided to investigate who did the deed.
First, I looked at Netto’s Lehrbuch der Combinatorik (1901). Although my German is minuscule and based on my knowledge of English and Yiddish (very little of the latter, to be sure), it was clear that Netto simply preferred counting of Catalan’s brackets to triangulations and other equivalent combinatorial interpretations. He did single out Catalan’s work, but mentioned Rodrigues’s work as well. In general, Netto wasn’t particularly careful with the the references, but in fairness neither were were most of his contemporaries. In any event, he never specifically mentioned “Catalan Zahlen”.
Second, I checked the above mentioned 1938 Bell’s paper in the Annals. As I suspected, Bell mentioned “Catalan’s numbers” only in passing, and not in a way to suggest that Catalan invented them. In fact, he used the term “Euler-Segner sequence” and provided careful historical and more recent references.
Next on my list was John Riordan‘s Math Review MR0024411, of this 1948 Motzkin’s paper. The review starts with “The Catalan numbers…”, and indeed might have been the first time this name was introduced. However, it is naive to believe that this MR moved many people to use this expression over arguably more cumbersome “Euler-Segner sequence”. In fact, Motzkin himself is very careful to cite Euler, Cayley, Kirkman, Liouville, and others. My guess is this review was immediately forgotten, but was a harbinger of things to come.
Curiously, Riordan does this again in 1964, in a Math Review on an English translation of a popular mathematics book by A.M. Yaglom and I.M. Yaglom (published in Russian in 1954). The book mentions the sequence in the context of counting triangulations of an n-gon, without calling it by any name, but Riordan recognizes them and uses the term “Catalan numbers” in the review.
The answer. To understand what really happened, see this Ngram chart. It clearly shows that the term “Catalan numbers” took off after 1968. What happened? Google Books immediately answers – Riordan’s Combinatorial Identities was published in 1968 and it used “the Catalan numbers”. The term took off and became standard within a few years.
What gives? It seems, people really like to read books. Intentionally or unintentionally, monographs tend to standardize the definitions, notations, and names of mathematical objects. In his notes on Mathematical writing, Knuth mentions that the term “NP-complete problem” became standard after it was used by Aho, Hopcroft and Ullman in their famous Data Structures and Algorithms textbook. Similarly, Macdonald’s Symmetric Functions and Hall Polynomials became a standard source of names of everything in the area, just as Stanley predicted in his prescient review.
The same thing happened to Riordan’s book. Although now may be viewed as tedious, somewhat disorganized and unnecessarily simplistic (Riordan admitted to dislike differential equations, complex analysis, etc.), back in the day there was nothing better. It was lauded as “excellent and stimulating” in P.R. Stein’s review, which continued to say “Combinatorial identities is, in fact, a book that must be read, from cover to cover, and several times.” We are guessing it had a tremendous influence on the field and cemented the terminology and some notation.
In conclusion. We don’t know why Riordan chose the term “Catalan numbers”. As Motzkin’s paper shows, he clearly knew of Euler’s pioneer work. Maybe he wanted to honor Catalan for his early important work on the sequence. Or maybe he just liked the way it sounds. But Riordan clearly made a conscious decision to popularize the term back in 1948, and eventually succeeded.
UPDATE (Feb. 8, 2014) Looks like Henry Gould agrees with me (ht. Peter Luschny). He is, of course, the author of a definitive bibliography of Catalan numbers. Also, see this curious argument against naming mathematical terms after people (ht. Reinhard Zumkeller).
UPDATE (Aug 25, 2014): I did more historical research on the subject which is now reworked into an article History of Catalan Numbers.
UPDATE (Oct 13, 2016): I came across a quote from Riordan himself (see below) published in this book review. In light of our investigation, this can be read as a tacit admission that he misnamed the sequence. Note that Riordan seemed genially contrite yet unaware of the fact that Catalan learned about the sequence from Liouville who knew about Euler and Segner’s work. So the “temporary blindness” he is alleging is perhaps misaddressed…
“Nevertheless, the pursuit of originality and generality has its perils. For one
thing, the current spate of combinatorial mappings has produced the feeling
that multiplicity abounds. Perhaps the simplest example is the continuing
appearances of the Catalan numbers [..] Incidentally, these numbers
are named after E. Catalan because of a citation in Netto’s Kombinatorik, in
relation to perhaps the simplest bracketing problem, proposed in 1838. An
earlier appearance, which I first learned from Henry Gould, is due to the
Euler trio, Euler-Fuss-Segner, dated 1761. There are now at least forty
mappings, hence, forty diverse settings for this sequence; worse still, no end
seems in sight. In this light, the Catalan (or Euler-Fuss-Segner) originality
may be regarded as temporary blindness.”
I tend to write longish posts, in part for the sake of clarity, and in part because I can – it is easier to express yourself in a long form. However, the brevity has its own benefits, as it forces the author to give succinct summaries of often complex and nuanced views. Similarly, the lack of such summaries can provide plausible deniability of understanding the basic points you are making.
This is the second time I am “inspired” by the Owl blogger who has a Tl;Dr style response to my blog post and rather lengthy list of remarkable quotations that I compiled. So I decided to make the following Readers Digest style summaries of this list and several blog posts.
1) Combinatorics has been sneered at for decades and struggled to get established
In the absence of History of Modern Combinatorics monograph, this is hard to prove. So here are selected quotes, from the above mentioned quotation page. Of course, one should reade them in full to appreciate and understand the context, but for our purposes these will do.
Combinatorics is the slums of topology – Henry Whitehead
Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. [..] Another criticism of combinatorics is that it “lacks abstraction.” The implication is that combinatorics is lacking in depth and all its results follow from trivial, though possible elaborate, manipulations. This argument is extremely misleading and unfair. – Richard Stanlеy (1971)
The opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. – László Lovász (1979)
Combinatorics [is] a sort of glorified dicethrowing. – Robert Kanigel (1991)
This prejudice, the view that combinatorics is quite different from ‘real mathematics’, was not uncommon in the twentieth century, among popular expositors as well as professionals. – Peter Cameron (2001)
Now that the readers can see where the “traditional sensitivities” come from, the following quote must come as a surprise. Even more remarkable is that it’s become a conventional wisdom:
Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics. – John Stillwell (2010)
Of course, the prejudice has never been limited to Combinatorics. Imagine how an expert in Partition Theory and q-series must feel after reading this quote:
[In the context of Partition Theory] Professor Littlewood, when he makes use of an algebraic identity, always saves himself the trouble of proving it; he maintains that an identity, if true, can be verified in a few lines by anybody obtuse enough to feel the need of verification. – Freeman Dyson (1944), see here.
2) Combinatorics papers have been often ostracized and ignored by many top math journals
This is a theme in this post about the Annals, this MO answer, and a smaller theme in this post (see Duke paragraph). This bias against Combinatorics is still ongoing and hardly a secret. I argue that on the one hand, the situation is (slowly) changing for the better. On the other hand, if some journals keep the proud tradition of rejecting the field, that’s ok, really. If only they were honest and clear about it! To those harboring strong feelings on this, listening to some breakup music could be helpful.
3) Despite inherent diversity, Combinatorics is one field
In this post, I discussed how I rewrote Combinatorics Wikipedia article, largely as a collection of links to its subfields. In a more recent post mentioned earlier I argue why it is hard to define the field as a whole. In many ways, Combinatorics resembles a modern nation, united by a language, culture and common history. Although its borders are not easy to define, suggesting that it’s not a separate field of mathematics is an affront to its history and reality (see two sections above). As any political scientist will argue, nation borders can be unhelpful, but are here for a reason. Wishing borders away is a bit like French “race-ban” – an imaginary approach to resolve real problems.
Gowers’s “two cultures” essay is an effort to describe and explain cultural differences between Combinatorics and other fields. The author should be praised both for the remarkable essay, and for the bravery of raising the subject. Finally, on the Owl’s attempt to divide Combinatorics into “conceptual” which “has no internal reasons to die in any foreseeable future” and the rest, which “will remain a collection of elementary tricks, [..] will die out and forgotten [sic].” I am assuming the Owl meant here most of the “Hungarian combinatorics”, although to be fair, the blogger leaves some wiggle room there. Either way, “First they came for Hungarian Combinatorics” is all that came to mind.
Do you think you know the answer? Do you think others have the same answer? Imagine you could go back in time and ask this question to a number of top combinatorialists of the past 50 years. What would they say? Would you agree with them at all?
Turns out, these answers are readily available. I collected them on this page of quotes. The early ones are uncertain, defensive, almost apologetic. The later ones are bolder, prouder of the field and its status. All are enlightening. Take your time, read them all in order.
During my recent MIT visit, Jacob Fox showed me this blog which I found to be rather derogatory in its treatment of combinatorics and notable combinatorialists. This brought me back to my undergraduate days in Moscow, reminded of the long forgotten but back then very common view of combinatorics as “second rate mathematics”. In the US, I always thought, this battle has been won before my time, back in the 1980s. The good guys worked hard and paved the road for all younger combinatorialists to walk on, and be proud of the field. But of course the internet has its own rules, and has room for every prejudice known to men.
While myself uninterested in engaging in conversation, I figured that there got to be some old “war-time” replies which I can show to the Owl blogger. As I see it, only the lack of knowledge can explain these nearsighted generalizations the blogger is showing. And in the age of Google Scholar, there really is no excuse for not knowing the history of the subject, and its traditional sensitivities.
But while compiling the list of quotes linked above, I learned a few things. I learned how tumultuous was the history of combinatorics, with petty fights and random turns into blind alleys. I learned how myopic were some of the people, and how clever and generous were others. I also discovered that there is a good answer to the question in the title (see below), but that answer is not a definition.
What do authorities say?
Not a lot, actually. The AMS MSC (which I love criticizing) lists Combinaorics as 05, on par with about 70 fields, such as Number Theory (11), Geometry (51), Probability (60) and Computer Science (68). It is also on the same level as Nonassociative rings (17), K-theory (19) and Integral equations (51), which are perfectly fine areas, just much smaller. It is one of the 32 categories on the arXiv, but who knows how these came about.
At the level of NSF, it is one of the 11 Disciplinary Research Programs, no longer lumped with “Algebra and Number Theory” (which remain joined at the hip according to NSF). Around the country, Combinatorics is fairly well represented at the top 100 universities, even if breaking “top 10” barrier remains difficult. Some are firmly in the “algebraic” camp, some in “probabilistic/extremal”, some have a lot of Graph Theory experts, but quite a few have a genuine mix.
This all reminded me of a story how I found out “What is mathematics“. It started with me getting a Master of Arts degree from Harvard. It arrived by mail, and made me unhappy. I thought they made a mistake, that I should have been given Master of Sciences. So I went to the registrar office, asked to see the director and explained the problem. The director was an old lady, who listened carefully, and replied “let me check”. She opened some kind of book, flipped a few pages and declared: “Yes, I see. No mistake made. Mathematics is an Art.” Seeing my disappointed face, she decided to console me “Oh, don’t worry, dear, it’s always been that way at Harvard…”
What the experts are saying.
About the title question, I mean. Let’s review the quotes page. Turns out, a lot of things, often contradicting each other and sometimes themselves. Some are cunning and ingenuous, while others are misleading or plain false. As the management maxim says, “where you stand depends on where you sit”. Naturally, combinatorialists in different areas have a very different view on the question.
Few themes emerge. First, that combinatorics is some kind of discrete universe which deals with discrete “configurations”, their existence and counting. Where to begin? This is “sort of” correct, but largely useless. Should we count logic, rectifiable knots and finite fields in, and things like Borsuk conjecture and algebraic combinatorics out? This is sort of like defining an elephant as a “large animal with a big trunk and big ears”. This “descriptive” definition may work for Webster’s dictionary, but if you have never seen an elephant, you really don’t know how big should be the ears, and have a completely wrong idea about what is a trunk. And if you have seen an elephant, this definition asks you to reject a baby elephant whose trunk and ears are smaller. Not good.
Second theme: combinatorics is defined by its tools and methods, or lack of thereof. This is more of a wishful thinking than a working definition. It is true that practitioners in different parts of combinatorics place a great value on developing new extensions and variations of the available tools, as well as ingenuous ad hoc arguments. But a general attitude, it seems, is basically “when it comes to problem solving, one can use whatever works”. For example, our recent paper proves unimodality results for the classical Gaussian coefficients and their generalizations via technical results for Kronecker coefficients, a tool never been used for that before. Does that make our paper “less combinatorial” somehow? In fact, some experts openly advocate that the more advanced the tools are, the better, while others think that “term ‘combinatorial methods’, has an oxymoronic character”.
Third theme: combinatorics is “special” and cannot be defined. Ugh… This reminds me of an old (1866), but sill politically potent Russian verse (multiple English translations) by Tyutchev. I can certainly understand the unwillingness to define combinatorics, but saying it is not possible is just not true.
Finally, a piecemeal approach. Either going over a long list of topics, or giving detailed and technical rules why something is and something isn’t combinatorics. But this bound to raise controversy, like who decides? For example, take PCM’s “few constraints” rule. Really? Somebody thinks block designs, distance-regular graphs or coding theory have too few constraints? I don’t see it that way. In general, this is an encyclopedia style approach. It can work on Wikipedia which is constantly updated and the controversies are avoided by constant search for a compromise (see also my old post), but it’s not a definition.
My answer, after Gian-Carlo Rota.
After some reading and thinking, I concluded that Gian-Carlo Rota’s 44 y.o. explanation in “Discrete thoughts” is exactly right. Let me illustrate it with my own (lame) metaphor.
Imagine you need to define Russia (not Tyutchev-style). You can say it’s the largest country by land mass, but that’s a description, not a definition. The worst thing you can do is try to define it as a “country in the North” or via its lengthy borders. You see, Russia is huge, spead out and disconnected. It lies to the North of China but has a disconnected common border, it has a 4253 mile border with Kazakhstan (longer than the US-Canada border excluding Alaska), surrounding the country from three sides, it lies North-West of Japan, East of Latvia, South-West of Lithuania (look it up!), etc. It even borders North Korea, not that this tiny border is much in use. Basically, Russian borders are complicated and are a result of numerous wars and population shifts; they have changed many times and might change again.
Now, Rota argues that Combinatorics is similarly formed by the battles, and can only be defined as such. It is a large interconnected field concentrated (but not coinciding!) around basic discrete tools and problems, but with tentacles reaching deep into “foreign territory”. Its current shape is a result of numerous “wars” – the borderline problems are tested on which tools are more successful, and whoever “wins”, gets to absorb a new subfield. For example, in its “war” with topology, combinatorics “won” graph theory and “lost” knot theory (despite a strong combinatorial influence). In other areas, such as computer science and discrete probability, Rota argues there a lot of cooperation, a mutually beneficial “joint governance” (all lame metaphors are mine). But as a consequence, if one is to define Combinatorics (or Russia), the historical-cultural approach would go best. Not all that different from Sheldon’s approach to define Physics “from the beginning”.
In conclusion, let’s acknowledge that Combinatorics can indeed be defined in the same (lengthy historical) manner as a large diverse country, but such definition would be neither short nor enlightening, more like a short survey. As Danny Kleitman writes, in practice this lack of a clear and meaningful definition of the subject “never bothered him”, and we agree. I think it’s time to stop worrying about that. But if someone makes blank general statements painting all of combinatorics in a certain way, this is just indefensible.
UPDATE (May 29, 2013)
I thought I would add a link to this article by Gian-Carlo Rota, titled “What ‘is’ mathematics?” This was originally distributed by email on October 7, 1998. For those too young to remember the Fall of 1998, Bill Clinton’s testimony was released on September 21, 1998, with its infamous “It depends on what the meaning of the word ‘is’ is” quote. Rota’s email never mentions this quote, but is clearly influenced by it.
UPDATE (August 5, 2015)
Since this article was written, Russian borders changed again, and not in a way I could have imagined (or supported). I am guessing, Combinatorics boundaries also changed. See e.g. our latest blog post titled The power of negative thinking on the use of Computability in Enumerative Combinatorics.
The Annals of Mathematics has been on my mind in the past few days (I will explain why some other day). More precisely, I was wondering
Does the Annals publish articles in Combinatorics? If not, why not? If yes, what changed?
What’s coming is a lengthy answer to this question, and a small suggestion.
I decided to investigate by searching the MR on MathSciNet (what else?) For our purposes, Combinatorics is defined as “Primary MSC = 05”). For a control group, I used Number Theory (“Primary MSC = 11”). I chose a break point date to be the year 2000, a plausible dividing line between the “old days” and “modern times”. I got the following numbers.
All MR papers: about 2.8 mil, of which 1 mil after 2000. In the Annals: 5422, of which 742 after 2000.
Combinatorics papers: about 88k, of which 41k after 2000. In the Annals: 18, of which 13 after 2000.
Number Theory papers: about 58k, of which 29k after 2000. In the Annals: 225, of which 129 after 2000.
So any way you slice it, as a plain number, as percentage of all papers, before 2000, after 2000, or in total – NT has about 10 times as many papers as Combinatorics. The bias seems transparent, no?
Well, there is another way to look at the numbers. MR finds that about 3% of all papers are in Combinatorics (which includes Graph Theory, btw). The percentage of Combinatorics in the Annals is about 0.3% Oops… But the percentage in recent years clearly picked up – since 2000, 13 Combinatorics papers constitute about 1.7% of all Annals papers. Given that there are over 50 major “areas” of mathematics (according to MSC), and Combinatorics is about 4.1% of all published papers since 2000, this is slightly below average, but not bad at all.
So what exactly is going on? Has Combinatorics finally reached the prominence it deserves? It took me awhile to figure this out, so let me tell this slowly.
Let’s looks at individual combinatorialists. Leonard Carlitz authored about 1000 papers, none in the Annals. George Andrews wrote over 300 and Ron Graham over 450 papers, many classical ones. Both аre former presidents of AMS. Again, none in the Annals. The list goes on: W.T. Tutte, Gian-Carlo Rota, Richard Stanely, Don Knuth, Doron Zeilberger, Béla Bollobás, János Pach, etc. – all extremely prolific, and neither published a single paper in the Annals. These are just off the top of my head, and in no particular order.
The case of Paul Erdős is perhaps the most interesting. Between 1937 and 1955, he published 25 papers in the Annals in a variety of fields (Analysis, Number Theory, Probability, etc.) Starting 1956, over the span of 40 years, he published over 1000 papers and none in the Annals. What happened? You see, in 1956 he coauthored a paper with Alfréd Rényi titled “On some combinatorical problems”, his very first paper with MSC=05. Their pioneer paper “On the evolution of random graphs” came just four years later. Nothing was ever the same again. Good bye, the Annals! Coincidence? Maybe a little. But from what I know about Erdős’s biography, his interests did shift to Combinatorics about that time…
Now, in NT and other fields things are clearly different. After many trials, two champions I found are Manjul Bhargava (6 out of his 21 papers were published in the Annals), and Hassler Whitney (19 out of 65), both with about 30% rate.
In fact, it is easier to list those who have published Combinatorics papers in the Annals. Here is the list of all 18 papers, as it really holds the clue to answering our initial question. A close examination of the list shows that the 13 papers since 2000 are quite a bit diverse and interconnected to other areas of mathematics. Some, but not most, are solutions to major open problems. Some, but not most, are in a popular area of extremal/probabilistic combinatorics, etc. Overall, a good healthy mix, even if a bit too small in number.
Note that in other fields things are different. Check out Discrete Geometry (52C), a beautiful and rapidly growing area of mathematics. Of the about 1800 papers since 2000, only three appeared in the Annals: one retracted (by Biss), and two are solutions of centuries old problems (by Hales and by Musin), an impossibly high standard. One can argue that this sample is too small. But think about it – why is it so small??
In summary, the answer to the first question is YES, the Annals does now publish Combinatorics papers. It may look much warmer towards NT, but that’s neither important, nor the original question. As for what caused the change, it seems, Combinatorics has become just like any other field. It is diverse in its problems, has a long history, has a number of connections and applications to other fields, etc. It may fall short on the count of faculty at some leading research universities, but overall became “normal”. Critically, when it comes to Combinatorics, the old over the top criterion by the Annals (“must be a solution of a classical problem”), is no longer applied. A really important contribution is good enough now. Just like in NT, I would guess.
I grew up (mathematically) in a world where the Annals viewed Combinatorics much the same way it viewed Statistics – as a foreign to mathematics fields with its own set of journals (heck, even its own annals). People rarely if ever submitted their papers to the Annals, because neither did the leaders of the field. Things clearly have changed for the better. Now the Annals does publish papers in Combinatorics, and will probably publish more if more are submitted. The main difference with Statistics is obvious – statisticians worked very hard to separate themselves from Mathematics, to create a separate community with their own departments, journals, grants, etc. They largely succeeded. Combinatorialists on the other hand, worked hard to become a part of mainstream Mathematics, and succeeded as well, to some extent. The change of attitude in the Annals is just a reflection on that.
The over-representation of NT is also easy to explain. I argued on MO that there is a bit of first-mover advantage going on, that some fields of mathematics feel grandfathered and push new fields away. While clearly true, let’s ask who benefits? Not the people in the area, which then has higher expectations for them (as in “What? No paper is the Annals yet?”). While it may seem that as a result, an applicant in NT might get an unfair advantage over that in Combinatorics, the hiring committees know better. This is bad for the Annals as well. In these uncertain times of hundreds of mathematics journals (including some really strange), various journal controversies, often misused barely reasonable impact factors, and new journals appearing every day, it is good to have some stability. Mathematics clearly needs at least one journal with universally high standards, and giving preferences to a particular field does not help anyone.
It seems, combinatorialists and perhaps people in other fields have yet to realize that the Annals is gradually changing in response to the changing state of the field(s). Some remain unflinching in their criticism. Notably, Zeilberger started calling it “snooty” in 1995, and continues now: “paragon of mathematical snootiness” that will “only publish hard-to-understand proofs” (2007), “high-brow, pretentious” (2010). My suggestion is trivial – ignore all that. Combinatorialists should all try to send their best papers to the top journals in Math, not just in the field (which are plenty). I realize that the (relative) reward may seem rather small, there is a lot of waiting involved, and the rejection chances are high, but still – this is important for the field. There is clearly a lot of anxiety about this among job applicants, so untenured mathematicians are off the hook. But the rest of us really should do this with our best work. I trust the editors will notice and eventually more Combinatorics papers will get published.
P.S. BTW, it is never too late. Of the 100+ papers by Victor Zalgaller, his first paper in the Annals appeared in 2004, when he was 84, exactly 65 years after his very first paper appeared in Russia in 1939.
One can argue whether some proofs are from the book, while others maybe not. Some such proofs are short but non-elementary, others are elementary but slightly tedious, yet others are short but mysterious, etc. (see here for these examples). BTW, can one result have two or more “proofs from the book”?
However, very occasionally you come across a proof that is both short, elementary and completely straightforward. One would call such a proof trivial, if not for the fact that it’s brand new. I propose a new term for these – let’s call them lost proofs, loosely defined as proofs which should have been discovered decades or centuries ago, but evaded this fate for whatever accidental historical circumstances (as in lost world, get it?) And when you find such a proof you sort of can’t believe it. Really? This is true? This is new? Really? Really?!?
The number of integer sequences such that , and for , is equal to the total number of partitions of integers into parts .
For example, for the first set is sequences is , while the second of partitions is , both with six elements.
This result was discovered about 20-25 years too soon. In 1879-1882, while at Johns Hopkins University, Sylvester pioneered what he called a “constructive partition theory”, and had he seen his good friend’s older paper, he probably would have thought about finding a bijective proof. Apparently, he didn’t. In all fairness to everybody involved, Cayley had written over 900 papers.
Now, the problem was rediscovered by Minc (1959), and notably by Andrews, Paule, Riese and Strehl (2001) as a biproduct of computer experiments. Both Cayley’s and APRS’s proofs are analytic (using generating functions). More recent investigations by Corteel, Lee and Savage (2005 and 2007 papers), and Beck, Braun and Le (2011) proved various extensions, still using generating functions.
We are now ready for the “lost proof”, which is really a lost bijection. It’s given by just one formula, due to Matjaž Konvalinka and me:
For example, for we get the following bijection:
Of course, once the bijection is found, the proof of Cayley’s theorem is completely straightforward. Also, once you have such an affine formula, many extensions become trivial.
One wonders, how does one can come up with such a bijection. The answer is: simply compute it assuming there is an affine map. It tends to be unique. Also, we have done this before (for convex partitions and LR-coefficients). There is a reason why this bijection is so similar to Sylvie Corteel’s “brilliant human-generated one-line proof” in the words of Doron Zeilberger. So it’s just amazing that this simple proof has been “lost” for over 150 years, until now…
See our paper (Konvalinka and Pak, “Cayley compositions, partitions, polytopes, and geometric bijections”, 2012) for applications of this “lost bijection” and my survey (Pak, “Partition Bijections, a Survey”, 2006) for more on partition bijections.