Who named Catalan numbers?

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

Who computed Catalan numbers?

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.

Conventional wisdom

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’s paper in the same volume (unsigned, but universally attributed to Euler).  My fan translation into English.

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. 

On triple crowns in mathematics and AMS badges

As some of you figured out from the previous post, my recent paper (joint with Martin Kassabov) was accepted to the Annals of Mathematics.  This being one of my childhood dreams (well, a version of it), I was elated for a few days.  Then I thought – normal children don’t dream about this kind of stuff.  In fact, we as a mathematical community have only community awards (as in prizes, medals, etc.) and have very few “personal achievement” benchmarks.  But, of course, they are crucial for the “follow your dreams” approach to life (popularized famously in the Last Lecture).  How can we make it work in mathematics?

I propose we invent some new “badges/statistics” which can be “awarded” by AMS automatically, based on the list of publications, and noted in the MathSciNet Author’s Profile.  The awardees can then proudly mention them on the department websites, they can be included in Wikipedia entries of these mathematicians, etc.   Such statistics are crucial everywhere in sports, and most are individual achievements.  Some were even invented to showcase a particular athlete.   So I thought – we can also do this.  Here is my list of proposed awards. Ok, it’s not very serious…  Enjoy!

Triple Crown in Mathematics

A paper in each of Annals of Mathematics, Inventiones, and Journal of AMS.  What, you are saying that “triple crown” is about horse racing?  Not true.  There are triple crowns in everything, from bridge to golf, from hiking to motor racing.  Let’s add this one to the list.

Other Journal awards

Some (hopefully) amusing variations on the Tripe Crown.  They are all meant to be great achievements, something to brag about.

Marathon – 300 papers

Ultramarathon – 900 papers

Iron Man – 5 triple crown awards

Big Ten – 10 papers in journals where “University” is part of the title

Americana – 5 papers in journals whose title may only include US cities (e.g. Houston), states (e.g. Illinois, Michigan, New York), or other parts of American geography (such as Rocky Mountains, Pacific Ocean)

Foreign lands – 5 papers in journals named after non-US cities (e.g. Bordeaux, Glasgow, Monte Carlo, Moscow), and five papers in journals named after foreign countries.

Around the world – 5 papers in journals whose titles have different continents (Antarctica Journal of Mathematics does not count, but Australasian Journal of Combinatorics can count for either continent).

What’s in a word – 5 papers in single word journals: (e.g. Astérisque, Complexity, Configurations, Constraints, Entropy, Integers, Nonlinearity, Order, Positivity, Symmetry).

Decathlon – papers in 10 different journals beginning with “Journal of”.

Annals track – papers in 5 different journals beginning with “Annals of”.

I-heart-mathematicians – 5 papers in journals with names of mathematicians (e.g. Bernoulli, Fourier, Lie, Fibonacci, Ramanujan)

Publication badges

Now, imagine AMS awarded badges the same way MathOverflow does, i.e. in bulk and for both minor and major contributions.  People would just collect them in large numbers, and perhaps spark controversies.  But what would they look like?  Here is my take:

enthusiast (bronze) – published at least 1 paper a year, for 10 years (can be awarded every year when applicable)

fanatic (silver) – published at least 10 papers a year, for 20 years

obsessed (gold) – published at least 20 papers a year, for 30 years

nice paper (bronze) – paper has at least 2 citations

good paper (silver) – paper has at least 20 citations

great paper (gold) – paper has at least 200 citations

famous paper (platinum) – paper has at least 2000 citations

necromancer (silver) – cited a paper which has not been cited for 25 years

asleep at the wheel (silver) – published an erratum to own paper 10 years later

destroyer (silver) – disproved somebody’s published result by an explicit counterexample

peer pressure (silver) – retracted own paper, purchased and burned all copies, sent cease and desist letters to all websites which illegally host it

scholar (bronze) – at least one citation

supporter (bronze) – cited at least one paper

writer (bronze) – first paper

reviewer (bronze) – first MathSciNet review

self-learner (bronze) – solved own open problem in a later paper

self-citer (bronze) – first citation of own paper

self-fan (silver) – cited 5 own papers at least 5 times each

narcissist (gold) – cited 15 own papers at least 15 times each

enlightened rookie (silver) – first paper was cited at least 20 times

dry spell (bronze) – no papers for the past 3 years, but over 100 citations to older papers over the same period

remission (silver) – first published paper after a dry spell

soliloquy (bronze) – no citation other than self-citations for the past 5 years

drum shape whisperer (silver) – published two new objects with exactly same eigenvalues

neo-copernicus (silver) – found a coordinate system to die for

gaussian ingenuity (gold) – found eight proofs of the same law or theorem

fermatist (silver) – published paper has a proof sketched on the margins

pythagorist (gold) – penned an unpublished and publicly unavailable preprint with over 1000 citations

homologist (platinum) – has a (co)homology named after

dualist (platinum) – has a reciprocity or duality named after

ghost-writer (silver) – published with a person who has been dead for 10 years

prince of nerdom (silver) – wrote a paper joint with a computer

king of nerdom (gold) – had a computer write a joint paper

sequentialist (gold) – authored a sequel of five papers with the same title

prepositionist (gold) – ten papers which begin with a preposition “on”, “about”, “toward”, or “regarding” (prepositions at the end of the title are not counted, but sneered at).

luddite (bronze) – paper originally written NOT in TeX or LaTeX.

theorist (silver) – the implied constant in O(.) notation in the main result in greater than 10⁸⁰.

conditionalist (silver) – main result is a conditional some known conjecture (not awarded in Crypto and Theory CS until the hierarchy of complexity classes is established)

ackermannist (gold) – main result used a function which grows greater than any finite tower of 2’s.

What about you?  Do you have any suggestions? 🙂

Britannica, Wikipedia and Combinatorics

All right, as we just learned, Britannica is done publishing.  Wikipedia won.  It wasn’t much of a contest, really.  We all expected this a long time ago.  Even if WP wasn’t as big as it is now (English language WP has about 4 mil pages), looking up there is noticeably faster than figuring out which volume of Britannica has your information.  So should we celebrate or commiserate?  I think neither, but we should instead turn this crisis into an opportunity.

First, how to think of the Britannica?  I say, as a series of historical documents, written by some of the best writers and scientists.  The case in point: Combinatorics article, which exists both in WP and in Britannica (the webpage has a free access this month).  Let’s review:

1) The Britannica Combinatorics article is overly long and incomplete at the same time, somewhat biased, very out of date, and barely coherent.  Lots of little examples are mentioned (multinomial coefficients, PBIB, etc.) and a few big things (graph theory, Ramsey theory, combinatorical geometry).  Nothing remotely recent (like algebraic combinatorics), most references from the 1960s and a couple of 1980s textbooks which are “accessible to laymen” (a lovely turn of phrase).  Sort of reminds me of this bridge – nice, useful in the past, but ultimately useless nowdays.

2) The Wikipedia Combinatorics article was in a horrible shape only about 3 years ago.  As a big WP fan, I was upset over this, and over the 1998 winter break largely rewrote the page myself.  The current version is still about 95% the same as I made it.  Rather than give silly examples and historical discussions, I simply made it into a portal with wikilinks to relevant subfields and few sentences describing each.  I thought I would get back to the article and write some more, but never did.  Sorry!

So, what gives?  Neither version is really a winner.  The Britannica article is outdated.  The WP article by itself has very little information.  The real difference can be seen only by going along the links – the total scope and quality of WP articles in combinatorics is noticeably better.  Still, some areas have WP pages which are not well written and/or have little information.  In summary, neither article gives a picture of the field.  If I were to choose a well written and accessible Combinatorics encyclopedia article, I would suggest Enumerative and Algebraic Combinatorics by Zeilberger, Extremal and Probabilistic Combinatorics by Alon and Krivelevich, and other articles from The Princeton Companion in Mathematics (Ed. by Tim Gowers).   

On the other hand, if viewed as a historical document Britannica article has a number of hidden treasures.  Written (at least in part) by Grünbaum (I am guessing in the 1960s), it correctly predicts the future growth of the extremal cominatorics and discrete geometry.  It is off base when it come to some other areas, like Polya’s theory which is rarely taught now and viewed as old fashioned.  Still, the page gives a window into the 1960 (or 1980?) thinking of what combinatorics is about.  In fact, even the name of the article was different – until recently it was “Combinatorial Analysis”.

My favorite “hidden gem” is the section on Partition Theory.  Check out theorem (F₁) there, which has both the statement and the proof (!).  This is common for WP (see e.g. this page), but rather unique for the Britannica.  It so happens, this section was originally written by Percy MacMahon in the 1911 Britannica (which is out of copyright now).  His version was up to date and beautifully written, later corrupted and shortened but never completely disappeared.  In fact, compared to 1911, new mistakes were introduced, e.g. an unpleasant typo in the section title “The Ferrer diagram” which I noticed in the 1960 edition managed to survive all these decades (they are named after Norman Ferrers).

Finally, my modest suggestion.  Treat the Britannica as a historical treasure that is up for sale (not unlike this one, sold in 1998).  After all, it dates back to 1768, three times older than this “Historic Cultural Monument” in my neighborhood.  The Britannica currently sells its digital version, but I bet this line of income will also dry up.  We (the people) should simply buy the whole thing and make it free and publicly available on the web.  Make sure to have available on the web all editions, not just the latest one.  This would give an instant window of how the same subject was treated over time.  Perhaps UNESCO?  Google?  Microsoft?  (it’s better than your Encarta, really!)  Amazon?  NSF?  Anyone with money?  I bet it’s cheap…

P.S.  A side comment – I want to praise Harald Helfgott’s recent serious effort to overhaul the Number Theory WP article.