{'fraction_non_alphanumeric': 0.041502294501247886, 'fraction_numerical': 0.029788261814668707, 'mean_word_length': 4.6155063291139244, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
History of Catalan numbers

We give a brief history of Catalan numbers, from their first discovery in the 18th century to modern times. This note will appear as an appendix in Richard Stanley's forthcoming book on Catalan numbers.


Introduction
In the modern mathematical literature, Catalan numbers are wonderfully ubiquitous. Although they appear in a variety of disguises, we are so used to having them around, it is perhaps hard to imagine a time when they were either unknown or known but obscure and underappreciated. It may then come as a surprise that Catalan numbers have a rich history of multiple rediscoveries until relatively recently. Below we review over 200 years of history, from their first discovery to modern times.
We break the history into short intervals of mathematical activity, each covered in a different section. We spend most of our effort on the early history, but do bring it to relatively recent developments. We should warn the reader that although this work is in the History of Mathematics, we are not a mathematical historian. Rather, this work is more of a historical survey with some added speculations based on our extensive reading of the even more extensive literature. Due to the space limitations, this survey is very much incomplete, as we tend to emphasize first discoveries and papers of influence rather than describe subsequent developments. This paper in part is based on our earlier investigation reported in [43]. Many primary sources are assembled on the Catalan Numbers website [44], including scans of the original works and their English translations.

Ming Antu
Ming Antu, sometimes written Ming'antu (c.1692-c.1763) was a Chinese scientist and mathematician, native of Inner Mongolia. In 1730s, he wrote a book Quick Methods for Accurate Values of Circle Segments which included a number of trigonometric identities and power series, some involving Catalan numbers: sin(2α) = 2 sin α − The integrality of Catalan numbers played no role in this work. Ming Antu's book was published only in 1839, and the connection to Catalan numbers was observed by Luo Jianjin in 1988. We refer to [33,39] for more on this work and further references.

Euler and Goldbach
In 1751, Leonhard Euler (1707-1783) introduced and found a closed formula for what we now call the Catalan numbers. The proof of this result had eluded him, until he was assisted by Christian Goldbach (1690-1764), and more substantially by Johann Segner. By 1759, a complete proof was obtained. This and the next section tell the story of how this happened.
On September 4, 1751, Euler wrote a letter to Goldbach which among other things included his discovery of Catalan numbers. 1 Euler was in Berlin (Prussia) at that time, while his friend and former mentor Goldbach was in St. Petersburg (Imperial Russia). They first met when Euler arrived to St. Petersburg back in 1727 as a young man, and started a lifelong friendship, with 196 letters between them [58].
For example, C 3 = (2 · 6 · 10)/(2 · 3 · 4) = 5. He concludes with the formula for the Catalan numbers g.f. : In his reply to Euler dated October 16, 1751, Goldbach notes that the g.f. A(x) satisfies quadratic equation He then suggests that this equation can be used to derive Catalan numbers via an infinite family of equations on its coefficients. Euler writes back to Goldbach on December 4, 1751. There, he explains how one can obtain the product formula (1) from the binomial formula: From the context of the letter, it seems that Euler knew the exact form of (4) before his investigation of the Catalan numbers. Thus, once he found the product formula (1), he was able to derive (2) rather than simply guess it. We believe that Euler did not include his derivation in the first letter as the g.f. formula appears at the very end of it, but once Goldbach became interested he patiently explained all the steps, as well as other similar formulas.

Euler and Segner
Johann Andreas von Segner (1704-1777) was another frequent correspondent of Euler. Although Segner was older, Euler rose to prominence faster, and in 1755 crucially helped him to obtain a position at University of Halle, see [10, p. 40]. It seems, there was a bit of competitive tension between them, which adversely affected the story. 1 The letters between Euler and Goldbach were published in 1845 by P. H. Fuss, the son of Nicolas Fuss. The letters were partly excised, but the originals also survived. Note that the first letter shows labeled quadrilateral and pentagon figures missing in the published version, see [44].
In the late 1750s, Euler suggested to Segner the problem of counting the number of triangulations of an n-gon. We speculate 2 based on Segner's later work, that Euler told him only values up to C 7 , and neither the product formula (1) nor the g.f. (2).
Segner accepted the challenge and in 1758 wrote a paper [49], whose main result is a recurrence relation which he finds and proves combinatorially: He then uses the formula to compute the values of C n , n ≤ 18, but makes an arithmetic mistake in computing C 13 = 742, 900, which then invalidates all larger values. Euler must have realized that equation (5) is the last missing piece necessary to prove (3). He arranged for Segner's paper to be published in the journal of St. Petersburg Academy of Sciences, but with his own 3 Summary [18]. In it, he states (1), gives Segner a lavish compliment, then points out his numerical mistake, and correctly computes all C n for n ≤ 23. It seems unlikely that given the simple product formula, Segner would have computed C 13 incorrectly, so we assume that Euler shared it only with his close friend Goldbach, and kept Segner in the dark until after the publication.
In summary, a combination of results of Euler and Segner, combined with Goldbach's observation gives a complete proof of the product formula (1). Unfortunately, it took about 80 years until the first complete proof was published.

Kotelnikow and Fuss
Semën Kirillovich Kotelnikow (1723-1806) was a Russian mathematician of humble origin who lived in St. Petersburg all his life. In 1766, soon after the Raid on Berlin, Euler returned to St. Petersburg. Same year, Kotelnikow writes a paper [31] elaborating on Catalan numbers. Although he claimed to have another way to verify (1), Larcombe notes that he "does little more than play around with the formula" [34].
Nicolas Fuss (1755-1826) was a Swiss born mathematician who moved to St. Petersburg to become Euler's assistant in 1773. He married Euler's granddaughter, became a well known mathematician in his own right, and remained in Russia until death. In his 1795 paper [20], in response to Pfaff's question on the number of subdivisions of an n-gon into k-gons, Fuss introduced what is now know as the Fuss-Catalan numbers (see Exercise A14), and gave a generalization of Segner's formula (5), but not the product formula.

The French school, 1838-1843
In 1836, a young French mathematician Joseph Liouville (1809-1882) founded the Journal de Mathématiques Pures et Appliquées. He was in the center of mathematical life in Paris and maintained a large mailing list, which proved critical in this story.
In 1838, a Jewish French mathematician and mathematical historian Olry Terquem (1782-1862) asked Liouville if he knows a simple way to derive Euler's formula (1) from Segner's recurrence (5). Liouville in turn communicated this problem to "various geometers". What followed is a remarkable sequence of papers giving foundation to "Catalan studies".
First, Gabriel Lamé (1795-1870) wrote a letter to Liouville outlining the solution, a letter Liouville promptly published in the Journal and further popularized [32]. Lamé's solution was to use an elegant double counting argument. Let's count the number A n of triangulations of 2 Euler's letters to Segner did not survive, as Segner directed all his archive to be burned posthumously [19, p. 153]. Segner's letters to Euler did survive in St. Petersburg, but have yet to be digitized (there are 159 letters between 1741 and 1771). 3 The article is unsigned, but the authorship by Euler is both evident and reported by numerous sources.
an (n + 2)-gon with one of its (n − 1) diagonals oriented. On the one hand, A n = 2(n − 1)C n .
On the other hand, by summing over all possible directed diagonals we have Combining these two formulas with (5) easily implies (1). In 1738, Belgium born mathematician Eugène Charles Catalan (1814-1894) was a student of Liouville atÉcole Polytechnique. Inspired by the work of Lamé, he became interested in the problem. He was the first to obtain what are now standard formulas He then studied the problem of computing the number of different (non-associative) products of n variables, equivalent to counting the number of bracket sequences [12]. Olinde Rodrigues (1795-1851) was a descendant of a large Sephardic Jewish family from Bordeaux. He received his doctorate in mathematics and had a career as a banker in Paris, but continued his mathematical interests. In the same volume of the Journal, he published two back-to-back short notes giving a more direct double counting proof of (1). The first note [47] gives a variation on Lamé's argument, a beautiful idea often regarded a folklore. Roughly, he counts in two ways the number B n of triangulations of (n + 2)-gon where either an edge or a diagonal is oriented. On the one hand, B n = 2(2n+1)C n . On the other hand, B n = (n+2)C n+1 , since triangulations with an oriented diagonal are in bijection with triangulations of (n + 3)-gon obtained by inserting a triangle in place of a diagonal, and such edge can be any edge except the first one. We omit the details.
In [48], Rodrigues gives a related, but even simpler argument for counting the bracket sequences. Denote by P n the number of bracket sequences of labeled terms x 1 , . . . , x n , e.g.
Then, on the one hand P n = n!C n . On the other hand, P n+1 = (4n − 2)P n since variable x n+1 can be inserted into every bracket sequence in exactly (4n − 2) ways. To see this, place a bracket around every variable and the whole product, e.g. ((x 2 )((x 1 )(x 3 ))). Now observe that a new variable is inserted immediately to the left of any of the (2n − 1) left brackets, or immediately to the right of any of the (2n − 1) right brackets, e.g.
In 1839, clearly unaware of Euler's letters, a senior French mathematician Jacques Binet (1786-1856) wrote a paper [7] with a complete g.f. proof of (1). Across the border in Germany, Johann August Grunert (1797-1872) became interested in the work of the Frenchmen on the one hand, and of Fuss on the other. A former student of Pfaff, in a 1841 paper [24] he found a product formula for the Fuss-Catalan numbers. He employed g.f.'s to reduce the problem to but seemed unable to finish the proof. The complete proof was given in 1843 by Liouville [37] using the Lagrange inversion (see [36]). 4 After a few more mostly analytic papers inspired by the problem, the attention of the French school turned elsewhere. Catalan however returned to the problem on several occasions throughout his career. Even fifty years later, in 1878, he published Sur les nombres de Segner [14] on divisibility of the Catalan numbers. 6. The British school, 1857-1891 Rev. Thomas Kirkman (1806-1895) was a British ordained minister who had a strong interest in mathematics. In 1857, unaware of the previous work but with Cayley's support, he published a lengthy treatise [30]. There, he introduced the Kirkman-Cayley numbers, defined as the number of ways to divide an n-gon with k non-intersecting diagonals (see A41), and states a general product formula, which he proves in a few special cases.
In 1857, Arthur Cayley (1821-1895) was a lawyer in London and extremely prolific mathematically. He was interested in a related counting of plane trees, and in 1859 published a short note [15], where (among other things) he gave a conventional g.f. proof of that the number of plane trees is the Catalan number. Like Kirkman, he was evidently unaware of the previous work. His final formula is which he called "a remarkably simple form". Curiously, in the same paper he also discovered and computed the g.f. for the ordered Bell numbers.
In 1860, Cayley won a professorship in Cambridge and soon became a central figure in British mathematics. Few years later, Henry Martyn Taylor (1842-1927) became a student in Cambridge, where he remained much of his life, working in geometry, mathematical education and politics. 5 In 1882, he and R. C. Rowe published a paper [55] where they carefully examined the literature of the French school, but gave an erroneous description of the Euler-Segner story. They evidently missed later papers by Grunert and Liouville, and computed the Fuss-Catalan numbers along similar lines, using the Lagrange inversion, see [35].
Cayley continued exploring g.f. methods for a variety of enumerative problems, among over 900 papers he wrote. In 1891, Cayley used g.f. tour de force to completely resolve Kirkman's problem [16].

The ballot problem
The ballot numbers were first defined by Catalan in 1839, disguised as the number of certain triangulations [13]. We believe this contribution was largely forgotten since Catalan gave a formula for the ballot numbers in terms of the Catalan numbers, but neither gave a closed formula nor even a table of the first few values.
The ballot sequences were first introduced in 1878 by William Allen Whitworth (1840-1905), a British mathematician, a priest and a fellow at Cambridge. He resolved the problem completely by an elegant counting argument and found interesting combinatorial applications [59]. Despite both geographical and mathematical proximity to Cayley, he did not notice that the numbers 1, 2, 5, 14, . . . he computed are the Catalan numbers.
In modern terminology, the ballot problem was introduced in 1887 by Joseph Bertrand (1822Bertrand ( -1900. In a half a page note [6], he defined the probability P m,n that in an election with (m + n) voters, a candidate who gathered m votes is always leading the candidate with n votes. Bertrand announced that one can use induction to show that P m,n = m − n m + n .
He famously concludes by saying: Il semble vraisemblable qu'un résultat aussi simple pourrait se démontrer d'une manière plus directe. (It seems probable that such a simple result could be shown in a more direct way.) Within months, Bertrand's protégé Joseph-Émile Barbier (1839-1889) announced a generalization of P m,n to larger proportions of leading votes [4], a probabilistic version of the formula for the Fuss-Catalan numbers. Désiré André (1840André ( -1918) was a well known French combinatorialist, a former student of Bertrand. He published an elegant proof of Bertrand's theorem [3] in the same 1887 volume of Comptes Rendu as Bertrand and Barbier. Although he is often credited with the reflection method, this attribution is incorrect, 6 as Andre's proof was essentially equivalent to that by Whitworth (cf. [45]). The reflection principle is in fact due to Dmitry Semionovitch Mirimanoff (1861-1945), a Russian-Swiss mathematician who discovered it in 1923, in a short note [41]. Andre's original proof was clarified and extended to Barbier's proposed generalization in [17].
We should mention here Takács's thorough treatment of the history of the ballot problem in probabilistic context [54], Humphreys's historical survey on general lattice paths and the reflection principle [26], and Bru's historical explanation on how Bertrand learned it from Ampère [9].

Later years
Despite a large literature, for decades the Catalan numbers remained largely unknown and unnamed in contrast with other celebrated sequences, such as the Fibonacci and Bernoulli numbers. Yet the number of publications on Catalan numbers was growing rapidly, so much that we cannot attempt to cover even a fraction of them. Here are few major appearances.
The first monograph citing the Catalan numbers is the Théorie des Nombres byÉdouard Lucas (1842-1891), published in Paris in 1891. Despite the title, the book had a large combinatorial content, including Rodrigues's proof of Catalan's combinatorial interpretation in terms of brackets and products [38, p. 68].
The next notable monograph is the Lehrbuch der Combinatorik by Eugen Netto (1848-1919), published in Leipzig in 1901. This is one of the first Combinatorics monographs; it includes a lot of material on permutations and combinations, and it devotes several sections to the papers by Catalan, Rodrigues and some related work by Schröder [42, p. 193-202].
We should mention that these monographs were more the exception than the rule. Many classical combinatorial books do not mention Catalan numbers at all, most notably Percy MacMahon, Combinatorial Analysis (1915/6), John Riordan, An Introduction to Combinatorial Analysis (1958), and H. J. Ryser, Combinatorial Mathematics (1963).
A crucial contribution was made by William G. Brown in 1965, when he recognized and collected a large number of references on the "Euler-Segner problem" and the "Pfaff-Fuss problem", as he called them [8]. 7 From this point on, hundreds of papers involving Catalan numbers have been published and all standard textbooks started to include it (see e.g. [25, §3.2] and [57, §3] for an early adoption). Some 465 references were assembled by Henry W. Gould in a remarkable bibliography [22], which first appeared in 1971 and revised in 2007. At about that time, various lists of combinatorial interpretations of Catalan numbers started to appear, see e.g. [23], Appendix 1 and a very different kind of list in [56, p. 263]. 6 Marc Renault was first to note the mistake [45]; he traces the confusion to Stochastic Processes by J.L. Doob (1953) and An Introduction to Probability Theory by W. Feller (2nd ed., 1957). In a footnote, Feller writes: "The reflection principle is used frequently in various disguises, but without the geometrical interpretation it appears as an ingenious but incomprehensible trick. The probabilistic literature attributes it to D. André (1887). It appears in connection with the difference equations for random walks. These are related to some partial differential equations where the reflection principle is a familiar tool called method of images. It is generally attributed to Maxwell and Lord Kelvin." 7 Unfortunately, Brown used somewhat confusing notation D 0,m to denote the Catalan numbers.

The name
Because of their chaotic history, the Catalan numbers have received this name relatively recently.
In the old literature, they were sometimes called the Segner numbers or the Euler-Segner numbers, which is historically accurate as their articles were the first published work on the subject. Perhaps surprisingly, we are able to tell exactly who named them Catalan numbers and when. 8 Our investigation of this eponymy is informal, but we hope convincing (cf. [60] for an example of a proper historical investigation). First, let us discard two popular theories: that the name was introduced by Netto in [42] or by Bell in [5]. Upon careful study of the text, it is clear that Netto did single out Catalan's work and in general was not particularly careful with the references, 9 but never specifically mentioned "Catalan Zahlen". Similarly, Eric Temple Bell (1883-1960) was a well known mathematical historian, and referred to "Catalan's numbers" only in the context of Catalan's work. In a footnote, he in fact referred to them as the "Euler-Segner sequence" and clarifies the history of the problem.
Our investigation shows that the credit for naming Catalan numbers is due to an American combinatorialist John Riordan (1903Riordan ( -1988. 10 He tried this three times. The first two: Math Reviews MR0024411 (1948) and MR0164902 (1964) went unnoticed. Even Marshall Hall's influential 1967 monograph [25] does not have the name. But in 1968, when Riordan used "Catalan numbers" in the monograph [46], he clearly struck a chord.
Although Riordan's book is now viewed as somewhat disorganized and unnecessarily simplistic, 11 back in the day it was quite popular. 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 great influence on the field and cemented the terminology and some notation.
We have further evidence of Riordan's authorship of a different nature: the Ngram chart for the words "Catalan numbers", which searches Google Books content for this sentence over the years. 12 The search clearly shows that the name spread after 1968 and that Riordan's monograph was the first book which contained it.
There were three more events on the way to the wide adoption of the name "Catalan numbers". In 1971, Henry Gould used it in the early version of [22], a bibliography of Catalan numbers with 243 entries. Then, in 1973, Neil Sloane gave this name to the sequence entry in [50], with Riordan's monograph and Gould's bibliography being two of the only five references. But the real popularity (as supported by the Ngram chart), was achieved after the Martin Gardner's Scientific American column in June 1976, popularizing the subject: [Catalan numbers] have [..] delightful propensity for popping up unexpectedly, particularly in combinatorial problems. Indeed, the Catalan sequence is probably the most frequently encountered sequence that is still obscure enough to cause mathematicians lacking access to N.J.A. Sloane's Handbook of Integer Sequences to expend inordinate amounts of energy re-discovering formulas that were worked out long ago. [21] 10. The importance Now that we have covered over 200 years of the history of Catalan numbers, it is worth pondering if the subject matter is worth the effort. Here we defer to others, and include the following helpful quotes, in no particular order.

Manuel Kauers and Peter Paule write in their 2011 monograph:
It is not exaggerated to say that the Catalan numbers are the most prominent sequence in combinatorics. [27] Peter Cameron, in his 2013 lecture notes elaborates: The Catalan numbers are one of the most important sequences of combinatorial numbers, with a large range of occurrences in apparently different counting problems. [11] Martin Aigner gives a slightly different emphasis: The Catalan numbers are, next to the binomial coefficients, the best studied of all combinatorial counting numbers. [2] This flattering comparison was also mentioned by Neil Sloane and Simon Plouffe in 1995, in the final print edition of EIS: Catalan numbers are probably the most frequently occurring combinatorial numbers after the binomial coefficients. [51] Doron Zeilberger attempts to explain this in his Opinion 49 : Mathematicians are often amazed that certain mathematical objects (numbers, sequences, etc.) show up so often. For example, in enumerative combinatorics we encounter the Fibonacci and Catalan sequences in many problems that seem to have nothing to do with each other. [..] The answer, once again, is our human predilection for triviality. [..] The Catalan sequence is the simplest sequence whose generating function is a (genuine) algebraic formal power series. [61] In a popular article, Jon McCammond reveals a new side of Catalan numbers: The Catalan numbers are a favorite pastime of many amateur (and professional) mathematicians. [40] Christian Aebi and Grant Cairns give both a praise and a diagnosis: Catalan numbers are the subject of [much] interest (sometimes known as Catalan disease). [1] Thomas Koshy, in his introductory book on Catalan numbers, gives them literally a heavenly praise: Catalan numbers are even more fascinating [than the Fibonacci numbers]. Like the North Star in the evening sky, they are a beautiful and bright light in the mathematical heavens. They continue to provide a fertile ground for number theorists, especially, Catalan enthusiasts and computer scientists. [28] In conclusion, let us mention the following answer which Richard Stanley gave in a 2008 interview on how the Catalan numbers exercise came about: I'd have to say my favorite number sequence is the Catalan numbers. [..] Catalan numbers just come up so many times. It was well-known before me that they had many different combinatorial interpretations. [..] When I started teaching enumerative combinatorics, of course I did the Catalan numbers. When I started doing these very basic interpretationsany enumerative course would have some of this -I just liked collecting more and more of them and I decided to be systematic. Before, it was just a typed up list. When I wrote the book, I threw everything I knew in the book. Then I continued from there with a website, adding more and more problems. [29]