Catalan Numbers Page

Warning: This list is vastly incomplete as I included only downloadable articles and books (sometimes, by subscription) that I found useful at different times. I do plan to gradually expand it, but will try not to overwhelm the list, so many related results can be obtained by forward and backward reference searches. Let me know if you find it useful.

Basics:

Larger values: at OEIS. Examples and Images: Catalan numbers (MacTutor History of Math.) Another meaning.

Encyclopedia and survey articles:

• OEIS: A108
• English Wikipedia: Catalan number
• MathWorld: Catalan number
• Richard Stanley's Exercise 19, solutions, and Catalan addendum (.pdf)
  Bonus: the story behind the exercise (the original link)
• Richard Stanley, Catalan numbers, Cambridge Universiy Press (2015), with an appendix by Igor Pak.
• Henry W. Gould, Research Bibliography of Catalan Numbers, 465 refs (1979, updated 2007)

Catalan numbers history articles:

• Igor Pak, History of Catalan numbers (August 2014), most up to date summary of current historical knowledge; based on historical documents (see below) and two earlier blog posts:
  • "Who computed Catalan numbers?" (Feb 20, 2013).
  • "Who named Catalan numbers?" (Feb 5, 2014).
  • see also Henry Gould's response (May 16, 2014).
• Marc Renault, The Ballot Problem website; original articles and their English translations.
• W. G. Brown, Historical Note on a Recurrent Combinatorial Problem (1965), local copy; brief historical timeline and refs.
• P. J. Larcombe and P.D.C. Wilson, On the trail of the Catalan sequence, Math. Today (1998); careful historical overview.
• U. Tamm, Olinde Rodrigues and combinatorics, in Mathematics and social utopias in France (2005); a very readable description of Rodrigues's contributions in the context of history of Catalan numbers.
• J. Laurentin, Réflexions sur la triangulation des polygones convexes, Bulletin de la SABIX (French, 2009); overview of the combinatorial work by Lamé.
• K. Humphreys, A history and a survey of lattice path enumeration, J. Stat. Planning Inference (2010)

Introductory articles:

• M. Hall, Combinatorial theory, Chapter 3 (1967)
• J.H. van Lint, Combinatorial Theory Seminar, Chapter 3, Lecture Notes in Math. (1974)
• M. Gardner, Catalan Numbers, Scientific American (June 1976)
• D. Singmaster, An elementary evaluation of the Catalan numbers, Amer. Math. Monthly (1978)
• D.M. Campbell, The Computation of Catalan Numbers, Math. Mag. (1984)
• P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer (1991)
• D. Rubenstein, Catalan numbers revisited, JCTA (1994)
• R.P. Stanley, Hipparchus, Plutarch, Schröder, and Hough, Amer. Math. Monthly (1997)
• M. Aigner, Catalan and other numbers: a recurrent theme, in Algebraic Combinatorics and Computer Science (2001)
• F. Hirzerbuch, Fax to Chern on Catalan numbers (11 November, 2003; meaning of Fax).
• T. Koshy, The Ubiquitous Catalan Numbers, Math. Teacher (2006)
• J. McCammond, Noncrossing partitions in surprising locations, Amer. Math. Monthly (2006)
• M. Renault, Four Proofs of the Ballot Theorem, Math. Mag. (2007)
• D. Armstrong, Catalan Numbers: From EGS to BEG, slides of MIT Combinatorics Seminar talk (May 2015).
• S. Roman, An introduction to Catalan numbers, Springer, 2015.

Videos of introductory lectures:

• Catalan Numbers, Part I by Mohamed Omar, and Part II by Michael Penn, March 2020.
• Evgeny Smirnov, Coursera lecture on Catalan numbers, HSE. This is Part 1; for other parts follow the links below the video, c. 2017.
• Po-Shen Loh, NYMC Talk on Catalan Numbers, Part 1 and Part 2, June 2015.
• Robert Sedgewick, Coursera lecture on Catalan numbers, Princeton; this is a portion of an early lecture in the Analysis of Algorithms course, c. 2014.
• Alissa S. Crans, A Surreptitious Sequence: The Catalan Numbers, MAA (2014), a longer version at MSRI (2017), and an even longer version at MoMath (2014).
• Federico Ardila, Lecture 6 of the Enumerative Combinatorics course, SFSU, Sep. 2013.
• Norman J. Wildberger, Euler's triangulation of a polygon, Insights into Mathematics, Feb. 2013.

Videos of research lectures:

• Xavier Viennot, The Catalan Garden, Chapter 2a, Chapter 2b, Chapter 2c and Chapter 2d, IMSc, Jan-Mar 2016.
• Nantel Bergeron, Generalizations of Catalan numbers (static video), FI, Nov 22, 2014.
• Richard Stanley, Some Catalan Musings (see also slides), IMA, Nov 10, 2014.
• Christos Athanasiadis, Catalan and Narayana Numbers for Weyl Groups, MSRI, Nov 5, 2008 (large files).
• Don Knuth, The Associative Law, or the Anatomy of Rotations in Binary Trees, Stanford, Nov 30, 1993.

Historical articles:

• Euler's letter exchange with Goldbach:
  • L. Euler, Letter to Goldbach (German, 4 September, 1751). Here are the scans of page 1 and page 2 of the relevant part of the original letter (these are courtesy Xavier Viennot). Euler introduces counting triangulation problem, finds the first 8 Catalan numbers, suggests an explicit product formula, and finds an explicit form g.f.
  • C. Goldbach, Reply to Euler (German, 16 October, 1751); by Goldbach makes a quick check of the first few terms of Euler's (correct) g.f.
  • L. Euler, Followup letter (German, 4 December, 1751); Euler shows that the product formula follows from the g.f. and the binomial theorem.

• St. Petersburg papers:
  • J.A. Segner, Enumeratio modorum quibus figurae planae rectilineae per diagonales dividuntur in triangula (Size: 13 Mb.), Novi Commentarii Academiae Scientiarum Imperialis Petropolitanae, vol. 7 (Latin, 1758/59, published in 1761); proof of a quadratic recurrence relation for Catalan numbers; clearly references Euler's earlier formulation and calculation; uses the formula to compute the first 18 Catalan numbers, the last 6 incorrectly.
  • L. Euler, Unsigned summary of Segner's article on the number of triangulations, ibid.; here Euler restates his product formula for Catalan numbers, fixes arithmetic mistakes in Segner's calculations, and extends them to the number of triangulations of n-gon, n≤25. See also my loose English translation.
  • S. Kotelnikow, Demonstratio seriei..., Novi Commentarii, vol. 10 (Latin, 1766); proves absolutely nothing.
  • N. Fuss, Solutio quæstionis, quot modis polygonum n laterum in polyga m laterum, per diagonales resolvi quæat (Size: 15 Mb.), Nova Acta Academiæ Scientarium Petropolitanæ, vol. 9 (Latin, 1795); Segner recurrence relation for the Fuss-Catalan numbers, thus answering Pfaff's question.

• French (and one German) papers:
  • G. Lamé, Extract from the letter to J. Liouville on the number of triangulations, Jour. de Math. (French, 1838, local copy); a complete elementary combinatorial proof of the recurrence relation and product formula via a double counting argument; English translation by D. Pengelley.
  • E. Catalan, Note sur une Équation aux différences finies, ibid. (local copy); discussion of Segner-Lamé recurrence relation and combinatorics of parentheses.
  • O. Rodrigues, Sur le nombre de manières de décomposer un Polygone en triangles au moyen de diagonales, ibid. (local copy); a direct inductive proof of the product formula for the number of triangulations.
  • O. Rodrigues, Sur le nombre de manières d'effectuer un produit de n facteurs, ibid. (local copy); a direct inductive proof of the product formula for the number of distinct products (bracket sequences).
  • M.J. Binet, Réflexions sur le Problème de déterminer le nombre de manières dont une figure rectiligne peut être partagée en triangles au moyen de ses diagonales, Jour. de Math. (French, 1839, local copy); a modern style g.f. proof.
  • E. Catalan, Solution nouvelle de cette question: Un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales?, ibid. (local copy); a new recurrence relation.
  • J.A. Grunert, Ueber die Bestimmung der Anzahl der verschiedenen Arten..., Archive der Mathematik und Physik (German, 1841); product formula for Fuss-Catalan numbers, g.f. approach.
  • J. Liouville, Remarques sur un Mémoire de N. Fuss, Jour. de Math. (French, 1843, local copy); a product formula for Fuss-Catalan numbers using Fuss's recurrence and Lagrange inversion.
  • l'abbé E. Gelin, Nombre de manières de décomposer un polygone convexe, Mathesis (1883); a likely case of plagiarism of Lamé's paper; of interest largely due to a historical comment by the editors.
  • E. Catalan, Sur les nombres de Segner, Rendiconti del Circolo Matematico di Palermo (French, 1887, local copy); divisibility properties of Catalan numbers.

• English papers:
  • T.P. Kirkman, On the K-Partitions of the R-Gon and R-Ace, Philosophical Transactions of the Royal Society (1857), local copy; introduction of Kirkman-Cayley numbers and a conjectured formula.
  • A. Cayley, On the analytical forms called trees, II, Philosophical Magazine (1859); plane trees, bijection to parenthetical expressions, g.f. solution.
  • W. A. Whitworth, Arrangements of m things of one sort and n things of another sort, under certain conditions of priority, Messenger of Math (1879), local copy; ballot sequences first defined and computed by a combinatorial argument.
  • H.M. Taylor and R.C. Rowe, Note on a Geometrical Theorem, Proc. London Math. Soc. (1882), local copy; g.f. proof of formula for the Fuss-Catalan numbers.
  • A. Cayley, On the partition of a polygon, Proc. London Math. Soc. (1890), local copy; proof of Kirkman's formula.

• Papers on the ballot problem: (translations by M. Renault)
  • (New!) L.F.A. Arbogast, Du calcul des derivations (French, 1800), see Example VI in §4.II; an explicit form of the Catalan triangle including product formulas for the Ballot numbers.
  • J. Bertrand, Solution d’un problème, C. R. Acad. Sci. (French, 1887); English translation; ballot problem solution by induction is announced.
  • É. Barbier, Généralisation du problème résolu par M. Bertrand, ibid.; English translation; generalized ballot problem to the Fuss-Catalan case.
  • D. André, Solution directed du problème résolu par M. Bertrand, ibid.; English translation; a different solution, variation on cycle lemma and reflection principle, similar to that by Whitworth.
  • D. Mirimanoff, A propos de l’interprétation géométrique du problème du scrutin, ibid. (1923); English translation; the reflection principle.

• Monographs:
  • E. Lucas, Théorie des nombres (French, 1891); an early monograph which briefly discussed Catalan numbers after Rodrigues (see Section 43, Ex IV)
  • E. Netto, Lehrbuch der Combinatorik (German, 1901); an early monograph which discussed Catalan numbers after Catalan & Rodrigues, as well as the Schröder numbers (see Chapter 9)
  • W. Feller, An Introduction to Probability Theory and its Applications (see §3.1); this 1950 monograph (mis-)attributed the "reflection principle" to André.

Trees and other combinatorial interpretations:

• I.M.H. Etherington, Some problems of nonassociative combinations (I), Edinb. Math. Notes (1940)
• N.G. de Bruijn and B.J.M. Morselt, A Note on Plane Trees, J. Comb. Theory (1967)
• D.A. Klarner, Correspondences between plane trees and binary sequences, J. Comb. Theory (1970)
• M.R.T. Dale and J.W. Moon, The permuted analogues of three Catalan sets, J. Stat. Planning Inference (1993)
• I. Pak, Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees, Discrete Math. (1999)
• D. Knuth, Three Catalan Bijections, preprint (2005)
• X.G. Viennot, Canopy of binary trees, Catalan tableaux and the asymmetric exclusion process, in Proc. FPSAC 2007.
• S. Heubach, N.Y. Li and T. Mansour, A garden of k-Catalan structures, preprint.
• A.N. Fan, T. Mansour and S.X.M. Pang, Elements of the sets enumerated by super-Catalan numbers, preprint.

Polygon dissections and noncrossing partitions:

• H.N.V. Temperley and E.H. Lieb, Relations between the 'percolation' and 'colouring' problem ..., Proc. Royal Soc. London, Ser. A (1971)
• N. Dershowitz and S. Zaks, Ordered trees and non-crossing partitions, Discrete Math. (1986)
• R.P. Stanley, Polygon dissections and standard Young tableaux (.ps file), JCTA (1996)
• R.P. Stanley, Parking functions and noncrossing partitions, Electron. J. Comb. (1997)
• J. Przytycki and A. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, JCTA (2000)
• R. Simion, Noncrossing partitions, Discrete Math. (2000)

Motzkin, Riordan and Baxter numbers:

• R. Donaghey and L.W. Shapiro, Motzkin Numbers, JCTA (1977)
• R. Cori, S. Dulucq and G. Viennot, Shuffle of parenthesis systems and Baxter permutations, JCTA (1986)
• M. Aigner, Motzkin Numbers, European J. Comb. (1998)
• A. Kuznetzov, I. Pak and A. Postnikov, Trees Associated with the Motzkin Numbers, JCTA (1996)
• F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discrete Math. (1999)
• O. Guibert and S. Linusson, Doubly alternating Baxter permutations are Catalan (.ps.gz file), Discrete Math. (2000)

Fine and Schröder numbers:

• L.W. Shapiro and R.A. Sulanke, Bijections for the Schröder numbers, Math. Mag. (2000)
• E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math. (2001)

Lattice walks and generalized ballot numbers:

• P. Franklin and C.F. Gummer, Solutions of Problems: 2681, Amer. Math. Monthly (1919)
• A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. (1947)
• T.V. Narayana, Sur les treilles formés par les partitions d'un entier et leurs applications à la théorie des probabilités, C. R. Acad. Sci. (French, 1955)
• Ph. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. (1980)
• D. Zeilberger, André’s reflection proof generalized to the many-candidate ballot problem, Discrete Math. (1983)
• M.P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theor. Comp. Sci. (1984)
• M. Desainte-Catherine and G. Viennot, Enumeration of certain Young tableaux with bounded height, in Lecture Note in Math. 1234 (1986).
• I.M. Gessel, A probabilistic method for lattice path enumeration (also free version), J. Stat. Planning Inference (1986)
• N. Dershowitz and S. Zaks, The cycle lemma and some applications, European J. Comb. (1990)
• I.M. Gessel and D. Zeilberger, Random walk in a Weyl chamber, Proc. AMS (1992)
• M. Bousquet-Mélou and G. Schaeffer, Walks on the slit plane, PTRF (2002)
• I.P. Goulden and L.G. Serrano, Maintaining the Spirit of the Reflection Principle when the Boundary has Arbitrary Integer Slope, JCTA (2003)

Pattern avoidance:

• P.A. MacMahon, Combinatory Analysis (Chapter 5, §97,98), Cambridge University Press, London, 1915.
• J. West, Generating Trees and the Catalan and Schröder Numbers (.ps.gz file), Discrete Math. (1995)
• S. Elizalde and I. Pak, Bijections for refined restricted permutations, JCTA (2004)
• A. Claesson and S. Kitaev, Classification of bijections between 321-and 132-avoiding permutations, Sém. Lothar. Comb. (2008)
• S. Kitaev, Patterns in Permutations and Words, e-book (by subscription), Springer, Berlin, 2011.

q-Catalan numbers:

• J. Fürlinger and J. Hofbauer, q-Catalan numbers, JCTA (1985)
• G.E. Andrews, Catalan numbers, q-Catalan numbers and hypergeometric series, JCTA (1987)
• V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, JCTA (2004)

q,t-Catalan numbers:

• A.M. Garsia and M. Haiman, A remarkable q,t-Catalan sequence and q-Lagrange inversion, J. Algebraic Comb. (1996)
• J. Haglund, The q,t-Catalan Numbers and the Space of Diagonal Harmonics, AMS, 2008 (.pdf file).
• E. Gorsky and M. Mazin, Compactified Jacobians and q,t-Catalan numbers, part I and part II (2011/12).
• P. Galashin and T. Lam, Positroids, knots, and q,t-Catalan numbers, arXiv (2020)
• P. Galashin and T. Lam, Positroid Catalan numbers, arXiv (2021)

Noncommutative Catalan numbers:

• A. Berenstein and V. Retakh, Noncommutative Catalan numbers, Ann. Comb. (2019)

Hyperplane arrangements:

• C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. (2004)
• S. Fishel and M. Vazirani, A bijection between dominant Shi regions and core partitions, European J. Comb. (2010)

Generalization to Coxeter groups:

• V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. (1997)
• C.A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Comb. (1998)
• D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Memoirs of the AMS (2009)
• A. Fink and B. Iriarte Giraldo, A bijection between noncrossing and nonnesting partitions for classical reflection groups, in Proc. FPSAC 2009
• D. Armstrong, C. Stump and H. Thomas, A uniform bijection between nonnesting and noncrossing partitions, Trans. AMS (2013)
• C. Stump, H. Thomas and N. Williams, Cataland: Why the Fuss?, arXiv (2015).
• P. Galashin, T. Lam, M.-T. Quang Trinh, N. Williams, Rational Noncrossing Coxeter-Catalan Combinatorics, arXiv (2022).

Catalan matroid:

• F. Ardila, The Catalan matroid, JCTA (2003)
• J. Bonin, A. De Mier and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, JCTA (2003)

Graph of triangulations:

• J.M. Lucas, The rotation graph of binary trees is Hamiltonian, J. Algorithms (1987)
• D.D. Sleator, R.E. Tarjan and W.P. Thurston, Rotation distance, triangulations, and hyperbolic geometry, JAMS (1988)
• J.A. De Loera, J. Rambau and F. Santos, Triangulations: Structures for Algorithms and Applications, Section 3 (e-book, WorldCat), Springer, 2010.
• J.-J. Liu, W.C.-K. Yen and Y.-J. Chen, An Optimal Algorithm for Untangling. Binary Trees via Rotations, Computer J. (2011)

Associahedron:

• M.M. Kapranov, The permutoassociahedron ..., J. Pure Applied Algebra (1993)
• V. Reiner and G.M. Ziegler, Coxeter-associahedra, Mathematika (1994)
• A. Tonks, Relating the associahedron and the permutohedron (.ps.gz file), in Operads, AMS, 1997.
• R. Simion, Convex Polytopes and Enumeration, Advances Applied Math. (1997)
• J.L. Loday, Parking functions and triangulation of the associahedron, in Contemporary Mathematics, 2007.
• C. Hohlweg and C. Lange, Realizations of the Associahedron and Cyclohedron, Discrete Comp. Geom. (2007)
• A. Postnikov, Permutohedra, associahedra, and beyond, IMRN (2009)
• C. Ceballos, F. Santos and G.M. Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica (2015)
• C. Ceballos and G.M. Ziegler, Realizing the Associahedron: Mysteries and Questions, in Progress in Mathematics, 2012.
• D. Armstrong and B. Rhoades and N. Williams, Rational Catalan Combinatorics: The Associahedron, DMTCS (2013)
• P. Galashin, Poset associahedra, arXiv (2021).

Asymptotic and probabilistic results:

• P. Flajolet and A.Odlyzko, The average height of binary trees and other simple trees, J. Comp. Sys. Sci. (1982)
• L. Devroye, Branching processes in the analysis of the heights of trees, Acta Informatica (1987)
• L. Takács, A Bernoulli excursion and its various applications, Advances Applied Probability (1990)
• D. Aldous, Triangulating the circle, at random, Amer. Math. Monthly (1994)
• D. Aldous, Recursive Self-Similarity for Random Trees, Random Triangulations and Brownian Excursion, Annals of Probability (1994)
• M. Drmota and B. Gittenberger, On the profile of random trees, Random Structures Algorithms (1997)
• R. Speicher, Free probability theory and non-crossing partitions, Sém. Lothar. Combin (1997)
• L. Devroye, P. Flajolet, F. Hurtado, M. Noy and W. Steiger, Properties of Random Triangulations and Trees, Discrete Comp. Geom. (1999)
• Z. Gao and N.C. Wormald, The Distribution of the Maximum Vertex Degree in Random Planar Maps, JCTA (2000)
• L. Addario-Berry and B.A. Reed, Ballot theorems, old and new, in Bolyai Soc. Math. Stud., 2008.
• Ph. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
• M. Drmota, Random Trees (e-book, link), Springer, 2009.
• N. Bernasconi, K. Panagiotou and A. Steger, On properties of random dissections and triangulations, Combinatorica (2010)
• J. Ortmann, Large deviations for non-crossing partitions, Electron. J. Probab. (2012)
• N. Curien, Dissecting the circle, at random, ESAIM Proc., 2014.
• N. Madras and L. Pehlivan, Structure of random 312-avoiding permutations, preprint
• S. Miner and I. Pak, The shape of random pattern-avoiding permutations, Advances Applied Math. (2014)
• T. Dokos and I. Pak, The expected shape of random doubly alternating Baxter permutations, Online J. Analytic Combin. (2014)
• C. Hoffman, D. Rizzolo and E. Slivken, Pattern avoiding permutations and Brownian excursion, arXiv (2014), published later in two parts.
• S.H. Chan I. Pak and G. Panova, Sorting probability of Catalan posets, Adv. Applied Math. (2021)

Random walks:

• M. Molloy, B. Reed and W. Steiger, On the mixing rate of the triangulation walk (.ps file), in DIMACS Series, 1999.
• L. McShine and P. Tetali, On the mixing time of the triangulation walk and other Catalan structures, ibid.
• R.A. Martin and D. Randall, Sampling adsorbing staircase walks using a new Markov chain decomposition method, in Proc. FOCS 2000.

Acknowledgments:

The images of road signs and binary trees used above are taken from Wikpedia.

The first two animated gifs of Dyck paths are takes from tex.stackexchange.com, the last one is made by Alejandro Morales (it circles over all 5 excited diagrams in a staircase shape).

We thank Xavier Viennot for giving scans of Euler's original letter, and most recently telling us about the Arbogast forgotten reference (Nov 2020).

Click here to return to Igor Pak Home Page.
To e-mail me, click here and delete .zzz

Last updated: 4/4/2023