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
29 questions with no upvoted or accepted answers
16
votes
0
answers
558
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$ ...
- 6,282
10
votes
0
answers
349
views
A bijective proof for the odd companion to Shapiro's Catalan convolution
Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number):
$$
\sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n.
$$
In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^...
- 1,190
9
votes
0
answers
213
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_{...
- 5,612
7
votes
0
answers
252
views
Hankel determinants for some convolutions of Catalan numbers
Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers and let $$x^k c(x)^{2k}=(c(x)-1)^k =\sum_{n\geq0}c(k,n)x^n.$$
Consider the determinants $$D(k,n,m)= \det\left(c(k,...
- 5,612
7
votes
0
answers
184
views
Upper bounds for a sequence of integers
Given $\alpha\geq0$ we consider the sequence
$$
C_k=k^\alpha\sum_{j=0}^{k-1}C_jC_{k-1-j}
$$
with $C_0=1$. I'm interested in upper bounds (in terms of $\alpha$) for such a sequence. I know that when $\...
- 843
7
votes
0
answers
530
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 \...
6
votes
0
answers
164
views
Can one naturally transform Tamari lattices into distributive lattices with the same number of elements?
Many of the zillions of combinatorial objects counted by Catalan numbers come with various lattice structures.
The $n$th Tamari lattice $T_n$, as originally defined, is the lattice of all those maps $...
- 18.4k
6
votes
0
answers
295
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.8k
6
votes
0
answers
112
views
Bijection between forests and skew SYT + Cyclic sieving
Consider the two-row skew shape $\lambda_n = (2n+1,n)/(1)$.
The number of standard Young tableaux of this shape is
$\binom{3n}{n}-\binom{3n}{n-2}$ (since one can easily biject this to the set of non-...
- 15.8k
6
votes
0
answers
381
views
Reference request: colored Motzkin path interpretation of Catalan numbers
Recall that a Dyck path of length $2n$ is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(2n,0)$ consisting of $n$ up steps $U=(1,1)$ and $n$ down steps $D=(1,-1)$ which never goes below the $x$-...
- 24.2k
6
votes
0
answers
214
views
Looking for a combinatorial proof for an identity involving $q$-Catalan triangles
Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...
- 43.1k
6
votes
0
answers
152
views
A conjecture about sums over partitions arising from Hilbert scheme of points
$\DeclareMathOperator{\leg}{\operatorname{leg}}\DeclareMathOperator{\arm}{\operatorname{arm}}$The following situation arose from the study of some localization computations on Hilbert schemes of ...
- 1,509
5
votes
0
answers
190
views
Yet, another generalization of Catalan determinants
The discussion on this page is motivated by Johann Cigler's MO question. My intention arose from a possible generalization of Cigler's matrix
$$A_{n,m}=\left( \binom{2m}{j-i+m}-\binom{2m}{m-i-j-1} \...
- 43.1k
4
votes
0
answers
272
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 ...
- 484
4
votes
0
answers
205
views
Non-crossing and crossing bijection in higher genus
This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
- 685
4
votes
0
answers
289
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 ...
- 457
4
votes
0
answers
144
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+...
- 141
4
votes
0
answers
208
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 ...
- 13.4k
3
votes
0
answers
123
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,644
2
votes
0
answers
89
views
The linear independence and linear elimination of non-crossing matching polynomials
Consider the polynomial set:
$$
f_{ij} = (t_i - t_j)x_i x_j + x_i - x_j, \quad (1 \leq j < i \leq 2n)
$$
where $ t_1, t_2, \dots, t_{2n} $ are pairwise distinct.
Let's look at the non-crossing ...
- 21
2
votes
0
answers
235
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,792
2
votes
0
answers
172
views
Lattice paths avoiding holes
Consider lattice paths from $(0,0)$ to $(2n,2n)$ with steps $N=(0,1)$ and $E=(1,0)$ avoiding the points $(2i-1,2i-1)$ for all $1\leq i\leq n$. There are Catalan many $C_{2n}=\frac1{2n+1}\binom{4n}{2n}$...
- 43.1k
2
votes
0
answers
241
views
Determinants of band matrices which are related to Hankel matrices of Catalan numbers
Let $A_{n,m}$ be the band matrix $$ A_{n,m}=\left( \binom{2m}{j-i+m}-\binom{2m}{m-i-j-1} \right)_{0\leq {i,j} \leq {n-1}}.$$
For example,
$$A_{6,2}=\left ( \begin{matrix} 2 & 3 & 1& 0 &...
- 5,612
2
votes
0
answers
182
views
Does this question have anything to do with Catalan numbers?
I think this question has something to do with Catalan numbers but I'm not really sure. I want to find out the number of strings that consist of $n$ $L$'s and $n$ $R$'s, under the constraint that for ...
2
votes
0
answers
80
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 ...
1
vote
0
answers
100
views
Super Catalan (super ballot) numbers
We refer to this article by Ira Gessel. In section 6, page 10, equation (28), the Super Catalan numbers are defined as
$$S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}.$$
On page 12, equation (31), there goes ...
- 43.1k
1
vote
0
answers
78
views
Shifted Hankel determinants for convolutions of Catalan numbers
It is well known that for $m\in \mathbb N$ the Hankel determinants $$D_m(n)= \det\left(C_{i+j+m}\right)_{0\leq i,j\leq {n-1}}$$ satisfy $D_m(n)=p_m(n)$, where $p_m(n)=\prod_{1 \leq i \leq j \leq {m-1}}...
- 5,612
0
votes
0
answers
92
views
Solving a Catalan-like recursion of polynomials, related to the KdV energies
I am working on a PDE problem. The goal is to connect the higher order energies of the Gross-Pitaevskii equation to those of the Korteweg-de-Vries equation. As these higher order energies are ...
- 203
0
votes
2
answers
747
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 ...
- 21