# 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

62
questions

**0**

votes

**0**answers

28 views

### Counting planar trees with the same underlying tree

$T$ be a tree, and $P_T$ denote the number of planar rooted trees whose underlying tree is $T$. Here, a planar rooted tree is a rooted tree such that the children of every vertex are totally ordered. ...

**2**

votes

**0**answers

47 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 ...

**5**

votes

**1**answer

168 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

74 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 ...

**4**

votes

**0**answers

175 views

### Dyck paths weighted by height profile

We are interested in a question concerning a weight function on Dyck paths that penalizes visits to higher heights.
Let $\rho$ be a parameter. Let $D_k$ be the set of all nearest neighbor random walk ...

**1**

vote

**1**answer

129 views

### A divisibility problem involving Catalan numbers

The Catalan numbers in combinatorics are given by
$$C_n=\frac1{n+1}\binom{2n}n=\binom{2n}n-\binom{2n}{n+1}\ \ (n=0,1,2,\ldots).$$
In 2014 I formulated the following conjecture.
Conjecture. For each $...

**13**

votes

**1**answer

467 views

### Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...

**3**

votes

**1**answer

143 views

### “Oddity” of $q$-Catalan polynomials: Part II

This question extends my earlier MO post for which I'm grateful for answers and useful comments.
The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ satisfy:
$\text{$C_{1,n}$ is odd iff $n=2^j-1$ for ...

**9**

votes

**2**answers

481 views

### Oddity of generalized Catalan numbers: Part I

The famous (classical) Catalan numbers $C_{1,n}=\frac1{n+1}\binom{2n}n$ satisfy the following well-known arithmetic property:
$$\text{$C_{1,n}$ is odd iff $n=2^j-1$ for some $j$}.\tag1$$
Consider the "...

**0**

votes

**4**answers

373 views

### How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$ [closed]

How to compute this series: $$\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$$ where $C_k$ is the catalan number: $C_k=\frac{1}{k+1}{2k \choose k}$. (Further, is there any general method to treat this ...

**8**

votes

**1**answer

312 views

### Products of Catalan numbers

Let $c(n)=\frac{1}{n+1}\binom{2n}{n}$ be the Catalan number. It seems that a product $\prod_{n\in I} c(n)$, where $I\subset\mathbb N_{>1}$, is never a Catalan number. Is this a (known) fact?

**1**

vote

**1**answer

178 views

### Reference request: Catalan number of type B

Are there some generalized Catalan number of type $B$ such that the sequence of the numbers is $3,9,29,97,333$ for $n=2,3,4,5,6$?
As discussed in this previous question, there are at least two types ...

**3**

votes

**1**answer

188 views

### Reference request for some determinants of binomial coefficients

Let $C_{n}=\binom{2n}{n}\frac{1}{n+1}$ be a Catalan number. I am interested in books or papers where the following identities occur:
$$\det\left(\binom{i+j+1}{i-j+1}\right)_{0 \leq i,j\leq {n-1}}=C_{n}...

**12**

votes

**1**answer

366 views

### A matrix identity related to Catalan numbers

Let $$C_n=\frac{1}{2n+1}\binom{2n+1}{n}$$ be a Catalan number. It is well-known that $$(\sum_{n\ge{0}}C_n x^n)^k=\sum_{n\ge{0}}C(n,k)x^n$$ with $$C(n,k)=\frac{k}{2n+k}\binom{2n+k}{n}.$$
It is also ...

**15**

votes

**1**answer

857 views

### Math journal publishing work related to combinatorics, probability, counting problems etc.?

I'm a high school student. My peer and I have done some work on the Ballot Theorem counting problem and Catalan Numbers. We have come up with a new proof to the Ballot Theorem and we demonstrate the ...

**5**

votes

**1**answer

176 views

### Show a sequence of sums involving Catalan Numbers converges

Let $C_n$ be the $n$-th Catalan Number and let $\mathcal{O}_{s,j} = {{2s-j-1}\choose{j}} C_{s-j}^2$. Then we want to consider $\mathcal{E}_s = \sum_{j=0}^{s-1} (-1)^j\mathcal{O}_{s,j}$. We want to ...

**30**

votes

**1**answer

1k views

### Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...

**18**

votes

**2**answers

389 views

### Is the order on repeated exponentiation the Dyck order?

The Catalan numbers $C_n$ count both
the Dyck paths of length $2n$, and
the ways to associate $n$ repeated applications of a binary operation.
We call the latter magma expressions; we will ...

**8**

votes

**1**answer

418 views

### Curious Catalan convolutions

Question. Do these identities involving even-index Catalan numbers have a known combinatorial interpretation? They look as though they should. I haven’t seen one in the literature.
$$\sum_{a+b=n}C_{...

**9**

votes

**0**answers

169 views

### Some quotients of Hankel determinants

This question has been inspired by Hankel determinants of binomial coefficients.
For a sequence $\{h_{n}\}_{n=0}^{\infty}$ denote by $H_n$ the Hankel matrix
$$H_{n}:=\begin{pmatrix}
h_{0} & h_{...

**10**

votes

**2**answers

893 views

### Proofs of some combinatorial identities

Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\dfrac{1}{\sqrt{1-4z}}$ and $C(z)=\dfrac{1-...

**6**

votes

**1**answer

251 views

### Number of tilting modules

Let $A=A_n$ be the algebra of upper triangular matrices over a field $K$ with $n$ simple modules.
It is a nice result that there are $C_{n+1}=1,2,5,14,...$ (Catalan numbers for $n \geq 1$) tilting $...

**11**

votes

**1**answer

320 views

### Reference request: Heyting algebra structure on Catalan numbers

I've noticed that for every natural number $n\in\mathbb{N}$, there is a finite Heyting algebra with cardinality $C(n)$, where $C(n)$ is the $n$th Catalan number,
$$1,1,2,5,14,42,132,\ldots$$
I'm ...

**10**

votes

**2**answers

275 views

### Distribution of the area statistic for Catalan paths

A Catalan path of semilength $n$ is a path from $(0,0)$ to $(2n,0)$ that proceeds by taking northeast (1,1) or southeast (1,-1) steps, and never goes below the $x$-axis. The area of a path $P$ is the ...

**1**

vote

**1**answer

143 views

### On generalized Catalan numbers

Counting some things in homological algebra, I found this sequence:
https://oeis.org/A025242.
Is there a good motivation why this sequence is called "generalized Catalan numbers"?
In the link there ...

**6**

votes

**1**answer

379 views

### generating $q$-Catalan numbers

An $n$-Dyck path (or a Catalan path) is a lattice path $P$, unit East and North steps, in an $n\times n$ square grid which stays (weakly) above the main diagonal. Let $\square_n$ denote all such paths....

**11**

votes

**2**answers

507 views

### Does $q$-Catalan number count subspaces?

Consider the $n$-element subsets $\{a_1<a_2<\cdots <a_n\}$ of $\{1,\ldots ,2n\}$ satisfying $a_i\geq 2i$ for all $i=1,\ldots ,n$. The number of such subsets is given by $${2n\choose n}-{2n\...

**4**

votes

**2**answers

361 views

### Intuition behind Hook Length Formula

Suppose I have a Standard Young Tableaux with dimensions $2$ x $n$. The Catalan numbers, $C_n$ count the number of ways to arrange the numbers $\left\{1, ..., 2n\right\}$. This can be derived using ...

**3**

votes

**2**answers

469 views

### Is there a combinatorial interpretation or bijective proof for this Catalan number identity?

Is there any combinatorial interpretation or bijective proof for this identity
$$2C_n=4{2n \choose n}-{2n+2 \choose n+1}$$
where $C_n$ is the sequence of Catalan numbers?

**4**

votes

**1**answer

270 views

### genus zero permutation and noncrossing partition

Question
Let $g$ to be an element of permutation group $S_n$, and $\tau = (1,2,3,\cdots,n)$ is the circular permutation. $g$ and $\tau g$ have $n+1$ cycles in total(fixed point is also a cycle), ...

**7**

votes

**0**answers

345 views

### Can we define the Mandelbrot set in terms of the generating function of the Catalan numbers?

For each complex number $c$, define $P_{0}(c)=0$ and $P_{n+1}(c) = (P_{n}(c))^{2} + c$ . The Mandelbrot set is the set of complex numbers c for which $|P_{n}(c)|$ stays bounded as $n\rightarrow \...

**1**

vote

**2**answers

180 views

### Solving for f given constraint involving f(x, y) and f(xy, y)

I am interested in a weighted version of the Catalan numbers. The generating function for this case,
$$ f(x, y) = \sum_s \sum_n f_{s n} x^s y^n $$
(where the $y^n$ term is the weight), obeys the ...

**2**

votes

**0**answers

69 views

### Is there a distance function on Dyck/Tamari words of arbitrary length?

Consider sequences of well-formed parentheses (or up/down sequences) of the type counted by the Catalan numbers. See http://www-math.mit.edu/~rstan/ec/catalan.pdf
These are sometimes called Dyck ...

**22**

votes

**1**answer

608 views

### q-Catalan numbers from Grassmannians

In this question by $q$-Catalan numbers I mean the $q$-analog given by the formula $\frac{1}{[n+1]_q}\left[{2n\atop n}\right]_q$. The polynomial $\left[{2n\atop n}\right]_q$ represents the class of ...

**9**

votes

**3**answers

1k views

### Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...

**4**

votes

**0**answers

129 views

### Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where
$$
D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( \sqrt{1-4z+4z^{p+...

**12**

votes

**2**answers

563 views

### Determinant of a checkerboard Hankel matrix with Catalan numbers

My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...

**11**

votes

**1**answer

385 views

### Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...

**13**

votes

**1**answer

919 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 ...

**13**

votes

**1**answer

2k 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 ...

**0**

votes

**2**answers

646 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**10**

votes

**1**answer

299 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.
...

**4**

votes

**0**answers

173 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 ...

**28**

votes

**3**answers

1k 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 ...

**3**

votes

**1**answer

218 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, a(bc),(ab)...

**37**

votes

**4**answers

2k 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 ...

**4**

votes

**1**answer

176 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 ...

**4**

votes

**1**answer

1k 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

**1**answer

251 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 ...

**9**

votes

**3**answers

956 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 ...