Archive

Archive for February, 2013

Who computed Catalan numbers?

February 20, 2013 4 comments

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

Advertisements