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 http://oeis.org/A000108

learn more… | top users | synonyms

11
votes
1answer
590 views

Lots of combinatorial interpretations of Catalan numbers

During a lecture I gave on Catalan numbers, I pointed out that that it is possible to give a continuum number of combinatorial interpretations of these numbers. See the solution to (f$^5$) on page 54 ...
10
votes
1answer
1k views

When does a Catalan number equal a Fibonacci number?

The $n=3$'rd Catalan number (A000108) is $1,1,2,5$ : $\frac{\binom{2n}{n}}{n+1}=\frac{\binom{6}{3}}{4}=\frac{20}{4}=$ 5. The $n=4$'th Fibonacci number (A000045) is $1,1,2,3,5,...$ : 5. Q. Which ...
8
votes
1answer
217 views

Non-abelian freeness of SU_2

The distribution of the trace of a random element of $SU_2$ is the Sato-Tate distribution. The analogue of the Gaussian distribution in free probability theory is the Wigner semicircle distribution. ...
3
votes
0answers
78 views

More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
22
votes
3answers
793 views

A double grading of catalan numbers

This is something I found in trying to work on Vince Vatter's excellent question. I have no solution, but a much more precise conjecture. Recall that a rooted planar tree is a rooted tree where, for ...
2
votes
1answer
157 views

Even more generalized Catalan numbers

What is the number of ways to parenthesize $n$ elements using applications of operators of arbitrary arities larger than or equal to $2$? For example, for $n=3$, there are $3$ ways: $$ abc, ...
34
votes
4answers
1k views

A family of words counted by the Catalan numbers

In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan ...
3
votes
1answer
121 views

Why are the dinv-statistic and the partition length equidistributed?

A partition of $n$ is a weakly decreasing sequence of natural numbers $\lambda = (\lambda_1, \lambda_2, \dots)$ such that $\sum \lambda_i = n$. Its length $l(\lambda)$ is the number of positive ...
2
votes
1answer
384 views

What does the $q$-Catalan Numbers count?

I had completed a paper describing the $q$-Catalan numbers, which is the $q$-analog of the Catalan numbers. The $n$-th Catalan numbers can be represented by: $$C_n=\frac{1}{n+1}{2n \choose n}$$ and ...
3
votes
1answer
193 views

Semi-planar partition monoid/algebra

Here are some beginner questions on partition algebras... I am trying to understand the monoid called $P_k$ in Tom Halverson, Arun Ram, Partition Algebras. For the sake of simplicity, let $k$ be a ...
7
votes
3answers
527 views

Intuition Behind a Decimal Representation with Catalan Numbers

From $0 = 0.5 - 0.5 = 0.5 - \sqrt{0.25}$, we can adjust the subtrahend slightly to obtain $$0.5 - \sqrt{0.249} = 0.001\ 001\ 002\ 005\ 014\ 042\ldots$$ where the decimal representation contains the ...
6
votes
4answers
886 views

A generalization of Catalan numbers

It is well-known that the $n$th Catalan number is equal to $(n+1)^{-1}\binom{2n}{n}$. A long time ago I had wondered what happens if you look at the sequence generated by $(n+k)^{-1}\binom{pn}{n}$ - ...
2
votes
2answers
702 views

Application of Catalan number [closed]

Hi guys just a quick questions What are the real life application of catalan numbers? Thanks a lot!
10
votes
5answers
876 views

enumerative meaning of natural q-Catalan numbers

Define $[n]=(1-q^n)/(1-q)$ and $[n]!=[1][2][3] \cdots [n]$, so that $[2n]!/[n]![n+1]!$ is a polynomial in $q$ (the most algebraically natural $q$-analogue of the Catalan numbers); what enumerative ...
13
votes
0answers
397 views

Catalan objects associated to a univariate polynomial

Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data: a noncrossing matching on $2n$ ...
4
votes
2answers
254 views

Equidistribution of returns and height of first peak of Dyck paths

I believe that it is "well known" that the following two statistics on Dyck paths have symmetric joint distribution: number of returns to the axis $RET(D)$ height of the first peak (or length of the ...
20
votes
5answers
3k views

Probability of a Random Walk crossing a straight line

Let $(S_n)\_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
7
votes
2answers
704 views

Modular congruences related to sums of Catalan numbers

I am curious if somebody can be helpful concerning the following experimental observation: There exist two rational sequences $\alpha_0,\alpha_1,\dots$ and $\beta_0,\beta_1,\dots$, both with values ...
3
votes
2answers
4k views

Combinatorial proof of a recurrence for the Catalan numbers

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers: $$ C_{n+1}=\frac{4n+2}{n+2} C_n. $$ Thanks!~
4
votes
1answer
357 views

Counting $(n,k)$-forests of binary trees

Given $k,n\in\mathbf{N}$ with $n\ge k$, define the set $\mathcal{F}(k,n)$ of $(k,n)$-forests of binary rooted trees (where a $(k,n)$-forest is a collection of $k$ rooted trees, which have a totality ...
28
votes
1answer
833 views

Is there a combinatorial reason that the (-1)st Catalan number is -1/2?

The $n$th Catalan number can be written in terms of factorials as $$ C_n = {(2n)! \over (n+1)! n!}. $$ We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$: ...