Archive

Posts Tagged ‘Catalan numbers’

The problem with combinatorics textbooks

July 3, 2021 Leave a comment

Every now and then I think about writing a graduate textbook in Combinatorics, based on some topics courses I have taught. I scan my extensive lecture notes, think about how much time it would take, and whether there is even a demand for this kind of effort. Five minutes later I would always remember that YOLO, deeply exhale and won’t think about it for a while.

What’s wrong with Combinatorics?

To illustrate the difficulty, let me begin with two quotes which contradict each other in the most illuminating way. First, from the Foreword by Richard Stanley on (his former student) Miklós Bóna’s “A Walk Through Combinatorics” textbook:

The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include. There is no more-or-less canonical corpus as in such other subjects as number theory and complex variable theory. [here]

Second, from the Preface by Kyle Petersen (and Stanley’s academic descendant) in his elegant “Inquiry-Based Enumerative Combinatorics” textbook:

Combinatorics is a very broad subject, so the difficulty in writing about the subject is not what to include, but rather what to exclude. Which hundred problems should we choose? [here]

Now that this is all clear, you can probably insert your own joke about importance of teaching inclusion-exclusion. But I think the issue is a bit deeper than that.

I’ve been thinking about this when updating my “What is Combinatorics” quotation page (see also my old blog post on this). You can see a complete divergence of points of view on how to answer this question. Some make the definition or description to be very broad (sometimes even ridiculously broad), some relatively narrow, some are overly positive, while others are revoltingly negative. And some basically give up and say, in effect “it is what it is”. This may seem puzzling, but if you concentrate on the narrow definitions and ignore the rest, a picture emerges.

Clearly, these people are not talking about the same area. They are talking about sub-areas of Combinatorics that they know well, that they happen to learn or work on, and that they happen to like or dislike. Somebody made a choice what part of Combinatorics to teach them. They made a choice what further parts of Combinatorics to learn. These choices are increasingly country or culture dependent, and became formative in people’s mind. And they project their views of these parts of Combinatorics on the whole field.

So my point is — there is no right answer to “What is Combinatorics?“, in a sense that all these opinions are biased to some degree by personal education and experience. Combinatorics is just too broad of a category to describe. It’s a bit like asking “what is good food?” — the answers would be either broad and bland, or interesting but very culture-specific.

Courses and textbooks

How should one resolve the issue raised above? I think the answer is simple. Stop claiming that Combinatorics, or worse, Discrete Mathematics, is one subject. That’s not true and hasn’t been true for a while. I talked about this in my “Unity of Combinatorics” book review. Combinatorics is comprised of many sub-areas, see the Wikipedia article I discussed here (long ago). Just accept it.

As a consequence, you should never teach a “Combinatorics” course. Never! Especially to graduate students, but to undergraduates as well. Teach courses in any and all of these subjects: Enumerative Combinatorics, Graph Theory, Probabilistic Combinatorics, Discrete Geometry, Algebraic Combinatorics, Arithmetic Combinatorics, etc. Whether introductory or advanced versions of these courses, there is plenty of material for each such course.

Stop using these broad “a little bit about everything” combinatorics textbooks which also tend to be bulky, expensive and shallow. It just doesn’t make sense to teach both the five color theorem and the Catalan numbers (see also here) in the same course. In fact, this is a disservice to both the students and the area. Different students want to know about different aspects of Combinatorics. Thus, if you are teaching the same numbered undergraduate course every semester you can just split it into two or three, and fix different syllabi in advance. The students will sort themselves out and chose courses they are most interested in.

My own teaching

At UCLA, with the help of the Department, we split one Combinatorics course into two titled “Graph Theory” and “Enumerative Combinatorics”. They are broader, in fact, than the titles suggest — see Math 180 and Math 184 here. The former turned out to be quite a bit more popular among many applied math and non-math majors, especially those interested in CS, engineering, data science, etc., but also from social sciences. Math majors tend to know a lot of this material and flock to the latter course. I am not saying you should do the same — this is just an example of what can be done.

I remember going through a long list of undergraduate combinatorics textbooks a few years ago, and found surprisingly little choice for the enumerative/algebraic courses. Of the ones I liked, let me single out Bóna’s “Introduction to Enumerative and Analytic Combinatorics and Stanley’s “Algebraic Combinatorics“. We now use both at UCLA. There are also many good Graph Theory course textbooks of all levels, of course.

Similarly, for graduate courses, make sure you make the subject relatively narrow and clearly defined. Like a topics class, except accessible to beginning graduate students. Low entry barrier is an advantage Combinatorics has over other areas, so use it. To give examples from my own teaching, see unedited notes from my graduate courses:

Combinatorics of posets (Fall 2020)

Combinatorics and Probability on groups (Spring 2020)

Algebraic Combinatorics (Winter 2019)

Discrete and Polyhedral Geometry (Fall 2018) This is based on my book. See also videos of selected topics (in Russian).

Combinatorics of Integer Sequences (Fall 2016)

Combinatorics of Words (Fall 2014)

Tilings (Winter 2013, lecture-by-lecture refs only)

In summary

In my experience, the more specific you make the combinatorics course the more interesting it is to the students. Don’t be afraid that the course would appear be too narrow or too advanced. That’s a stigma from the past. You create a good course and the students will quickly figure it out. They do have their own FB and other chat groups, and spread the news much faster than you could imagine…

Unfortunately, there is often no good textbook to cover what you want. So you might have to work a little harder harder to scout the material from papers, monographs, etc. In the internet era this is easier than ever. In fact, many extensive lecture notes are already available on the web. Eventually, all the appropriate textbooks will be written. As I mentioned before, this is one of the very few silver linings of the pandemic…

P.S. (July 8, 2021) I should have mentioned that in addition to “a little bit about everything” textbooks, there are also “a lot about everything” doorstopper size volumes. I sort of don’t think of them as textbooks at all, more like mixtures of a reference guide, encyclopedia and teacher’s manual. Since even the thought of teaching from such books overwhelms the senses, I don’t expect them to be widely adopted.

Having said that, these voluminous textbooks can be incredibly valuable to both the students and the instructor as a source of interesting supplementary material. Let me single out an excellent recent “Combinatorial Mathematics” by Doug West written in the same clear and concise style as his earlier “Introduction to Graph Theory“. Priced modestly (for 991 pages), I recommend it as “further reading” for all combinatorics courses, even though I strongly disagree with the second sentence of the Preface, per my earlier blog post.

Who named Catalan numbers?

February 5, 2014 2 comments

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?

February 20, 2013 5 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