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 became rather interested in the early history of Catalan numbers after reading multiple somewhat contradictory historical accounts. Now that I checked the sources, most of which are available online (see my Catalan Numbers page), I think I understand what happened. While I conclude that Euler deserve most of the credit, as I see it, what really happened is a bit more complicated. Basically, this is a story of research collaboration, only fragments of which are known.
Warning: I am assuming you are familiar with basic results on Catalan numbers, which allows me to concentrate on the story rather than the math.
All sources basically agree that Catalan numbers are named after Eugène Catalan (1814–1894), though they were computed by Leonhard Euler. There are several narratives in the literature, which are variations on the following statements, neither of which is really correct:
1. The problem was introduced by Segner in his 1758 article and solved by Euler in an unsigned article in the same journal volume.
2. The problem was introduced by Euler in his 1758 unsigned article and solved by Segner by a recurrence relation in the same volume.
3. The problem was introduced/solved by Euler in a 1751 letter to Goldbach, but Segner’s paper is the first published solution.
4. Although the problem was raised by Euler and/or Segner, neither of which found a proof. The first proof was given by Lamé in 1838.
Let me delay the explanation of what I think happened. Please be patient!
People and places
There are three heroes in this story: Leonhard Euler (1707–1783), Christian Goldbach (1690–1764), and Johann von Segner (1704–1777). Goldbach was the most senior of the three, he moved to St. Petersburg in 1725, tutored Tsarevich Peter II, and lived in Russia for the rest of his life. When young Euler arrived to St. Petersburg in 1727, Goldbach became his mentor, lifelong friend and a correspondent for over 35 years. Of the numerous letters between them, many were edited and published by Euler’s former assistant, a mathematician and grandson-in-law Nicolas Fuss (1755–1826).
Segner was a physician by trade, but in 1732 became interested in mathematics. In 1735 he was appointed the first mathematics professor at the University of Göttingen (not a big deal at the time). Euler left Russia in 1741 to a position at the Berlin Academy, and joined the court of Frederick the Great of Prussia, at which point he became a frequent correspondent with Segner. Their relationship, perhaps, was closer to a friendly competition than a true friendship between Euler and Goldbach. Although Segner and Euler were contemporaries, Euler rose to prominence very quickly and had a lot of political sway. For example, he slyly engineered Senger’s position at the University of Halle in Saxony, where Segner moved in 1755. Unfortunately, only letters from Segner to Euler survived (159 of them) and these have yet to be digitized.
In 1756, Frederick II overrun the Saxony as a part of initial hostilities of the Seven Year’s War, which put Prussia and Russia on different sides. But Euler continued to publish in Russia, where he was widely respected. When Russian troops marched through Berlin in 1760 (not for the last time), he did not leave the city. Later, when his personal estate was marauded, he was eventually compensated by Catherine the Great (whose court he joined in 1766).
Letter exchange between Euler and Goldbach
* First letter: September 4, 1751 letter, from Euler to Goldbach.
Near the end of the letter, Euler writes matter of factly, that he figured out the numbers of triangulations of the polygons with at most 10 sides. Evidently, he does this by hand, and then takes ratios of successive number to guess the general product formula. He writes:
Die Induction aber, so ich gebraucht, war ziemlich mühsam, doch zweifle ich nicht, dass diese Sach, nicht sollte weit leichter entwickelt werden können.
He continues to guess (correctly) a closed algebraic formula for the g.f. of the Catalan numbers sequence.
* Second letter: October 16, 1751 letter, from Goldbach to Euler.
Here Goldbach suggests there is a way to verify Euler’s g.f. formula by algebraic manipulations. Essentially, he rewrote Euler’s formula for the g.f. for Catalan numbers as a quadratic equation for power series. He the checks the equation for the first few coefficients.
* Third letter: December 4, 1751 letter, from Goldbach to Euler.
Here Euler uses the binomial theorem to show that the generating function formula indeed implies his product formula for the Catalan numbers.
Papers by Euler and Segner
* Segner’s paper in Novi Commentarii, volume 7 (dated 1758/59, but published only in 1761).
Here Segner finds and proves the standard quadratic relation between Catalan numbers. He starts by attributing the problem to Euler and mentioning the first few Catalan numbers that Euler calculated. He then uses this quadratic equation to calculate the first 18 Catalan numbers, but makes an arithmetic mistake, thus miscalculating the last 6.
Euler describes the number of triangulations problem, mentions Segner’s recurrence relation, and then his direct inductive formula for Catalan number, which he rewrites as a conventional product of n-2 fractions. He then uses this formula to correct and extend Segner’s table.
What happened (my speculation) :
This was a collaborative research effort. First, Euler introduced the number of triangulations problem, which perhaps came from his map making work both in Russia and in Berlin (he hints to that in his “summary”). Euler labored to compute by hand the first few Catalan numbers by using ad hoc methods; he correctly calculated them up to 1430 triangulations of a 10-gon. He used these numbers to guess a simple product formula for the Catalan numbers by observing a pattern in successive ratios, and a closed form algebraic formula for the g.f. He clearly realized that the proof of both is needed, but thought this was a difficult problem, at which point he writes to Goldbach. In his reply, Goldbach suggested how to verify the analytic formula, but Euler took a different route and showed that one formula implies the other. From a modern point of view, this was an open exchange of ideas between friends and collaborators, even if dominated by Euler’s genius.
Some years later, Euler evidently suggested this problem to Segner, but never informed him of the product formula which he guessed back then. While Euler’s letters to Segner did not survive, it is clear from Segner’s writing that he knew of some Euler’s calculations, but not the product formula (there is no way he would have made a mistake in the table otherwise), nor even the 1430 value (the largest number reported by Euler to him seemed to be 429). No wonder Segner did not prove Euler’s product formula – he simply did not know what he should be proving, so presented his results as a method for computing Catalan numbers.
Finally, when Euler saw Segner’s work, he immediately realized its value as the last missing piece. Essentially, Segner’s recurrence is exactly what remained in the sequence
combinatorial interpretation → recurrence relation → algebraic equation → closed algebraic formula → product formula,
where the first step is due to Segner, the second and third are easy and closely related to Goldbach’s approach, while the last step is due to Euler himself. Those who teach undergaduates this particular proof, know how much of a pain to teach this last step. As I understand, despite the war and geography, Euler continued editing the volumes of the St. Petersburg based Novi Commentarii. In what should have been the “Summary” of Segner’s article, he included his formula as a way to both gently correct Segner and show the superiority of his product formula. I should mention that Euler’s Latin original sugarcoated this. It is a pity that Euler never published anything else on the subject.
What happened next:
This is much better documented. First, in response to a question by Johann Pfaff, the above mentioned Nicolas Fuss published in 1791 a generalization of Segner’s recurrence relation, and converted it to a higher order algebraic equation for the g.f., thus generalizing Euler’s algebraic formula. This allowed Liouville to give a product formula for this generalization using the Lagrange inversion formula, which was later rediscovered by Kirkman, Cayley and others.
The problem was then studied French mathematician and promoter of Reform Judaism Olry Terquem (1782–1862). As hinted by Liouville in a foonote to Lamé’s article, Terquem knew of both Euler’s and Segner’s articles, but not of the algebraic formulas. He seem to have succeeded in proving that the recurrence relation implies the product formula, thus “achieving it with the help of some properties of factorials”. In in 1838, he suggested the problem to Joseph Liouville (1809–1882), who in turn suggested the problem to a number of people, some of whom became to actively work on the subject. Liouville’s colleague at École Polytechnique, Gabriel Lamé (1795–1870), quickly found an elegant combinatorial solution building on Segner’s approach. Liouville extracted mathematical content from the letter Lamé wrote to him, and quickly published it (English translation), in the Journal de Mathématiques which he started two years earlier. This became the first published complete proof of the product formula for Catalan numbers.
In the following year, other colleagues joint the effort (Binet, Catalan, Rodrigues), and their effort was also published by Liouville. In the following 175 years the problem has been repeatedly rediscovered and generalized (notably, by Bertrand in 1887, in the context of the ballot problem). A small portion of these papers is listed here. Henry Gould’s 2007 count gives 465 publications, surely undercounting the total.
What’s in a name?
Curiously, Catalan’s own contribution was helpful, but not crucial. Netto singled him out in his 1901 monograph, as he favorited Catalan’s language of parenthesized expressions over the less formal discussion of polygon triangulations. Catalan himself called them “Segner numbers“. Given that Euler already has plenty of numbers named after him, it’s too late to change this name. We are stuck with Catalan numbers!
Note: This post is not a piece of research in History of Mathematics, which is a serious field with high standards for quality and rigor. This is merely a speculation, my effort to put together some pieces of the story which do not seem to fit otherwise.
Update (Feb 28, 2013): S. Kotelnikow’s 1766 contribution is removed as he seem to have proved absolutely nothing.
Update (Feb 5, 2014): While Netto did indeed single out Catalan’s work, we now believe that it was Riordan solely responsible for the name (see this blog post).
Update (Aug 25, 2014): I did more historical research on the subject which is now reworked into an article History of Catalan Numbers.