Skip to main content

Questions tagged [catalan-numbers]

The Catalan numbers form the sequence of numbers starting 1,1,2,5,14,42,... with explicit formula $\frac{1}{n+1}\binom{2n}{n}$. It counts many combinatorial objects like planar binary trees, triangulations, noncrossing partitions, Dyck paths, etc. See https://oeis.org/A000108

109 questions
Filter by
Sorted by
Tagged with
2 votes
1 answer
140 views

• 5,592
2 votes
0 answers
231 views

Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon. Let $P_n$ be the number of three-connected planar ...
• 5,682
4 votes
0 answers
239 views

Representations of $\mathrm{sl}(3,\mathbb{C})$ and Catalan-like paths

Background on representations of $\mathrm{sl}(3,\mathbb{C})$ In Chapter 6 of Brian C. Hall's book "Lie Groups, Lie Algebras, and Representations", he constructs the irreducible ...
8 votes
3 answers
855 views

• 5,592
6 votes
0 answers
265 views

Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
• 15.7k
7 votes
0 answers
250 views

• 5,592
7 votes
2 answers
397 views

• 42.3k
15 votes
1 answer
254 views

• 15.7k
3 votes
0 answers
116 views

Seeking bijective proof of a recurrence for generalized Narayana numbers

Consider lattice paths in $d$ dimensions with the steps $X_1\mathrel{:=}(1,0,\dotsc,0)$, $X_2\mathrel{:=} (0,1,\dotsc,0)$,…, $X_d\mathrel{:=} (0,0,\dotsc,1)$. Let $\mathcal C(d, n)$ denote the set of ...
• 1,524
5 votes
1 answer
402 views

Non-nesting matchings and Catalan numbers

It is well-known that the number of non-nesting perfect matchings on $2n$ points is given by the Catalan number $C_n$; see part (a) of the figure below. This is item e^5 in Stanley's list (http://www-...
-1 votes
1 answer
89 views

Domination relationship between generalized Dyck Paths

In short, we are seeking an injection between generalized Dyck paths that end at a certain height into the set of paths of the same length that end at a lower height such that the image path stays ...