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
111 questions
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
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
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 ...
- 13.4k
2
votes
1
answer
147
views
$R$-recursion for Fibonacci numbers using signed Catalan numbers
Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here
$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, F_1 = 1.
$$
Let $C_n$ be A000108 (i.e., Catalan numbers). Here
$$
C_n = \frac{1}{n+1}\binom{2n}{n}.
$$
Let
$...
- 4,928
5
votes
1
answer
148
views
Identities for the generating functions of a sort of convolution powers of the Narayana numbers
Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers.
It satisfies $$\frac{1}{c(x)^k}+x^k c(x)^k=L_k(1,-x),$$
where $L_n(x,s)$ denote the Lucas polynomials defined by $...
- 34.3k
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
3
votes
1
answer
331
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)...
- 1,446
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
8
votes
3
answers
921
views
Alternating Sum Involving Catalan Numbers
I was wondering if anyone knew how to obtain a simpler closed form of the following sum(or had any other insights regarding it):
$$\sum_{k=0}^n (-1)^k{n \choose k} C_{2n-2-k} $$
Here $C_n = \frac{1}{n+...
- 18.4k
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
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
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
10
votes
2
answers
2k
views
Proving an identity about Catalan numbers
$$C_{n} = \sum_{i=1}^n (-1)^{i-1} \binom{n-i+1}{i} C_{n-i}$$
Are there any good combinatorial proofs or algebraic proofs of this?
- 10.5k
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
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
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
4
votes
2
answers
346
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 ...
- 1,446
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,...
- 24.2k
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
5
votes
1
answer
502
views
A polynomial identity related to Catalan numbers
Let $F_n^{(k)}(x)= \sum_j {\binom{n+(k-1)j}{kj} x^j}$ and $G_n^{(k)}(x)= \sum_j {\binom{n+j}{kj} x^j}.$
I am interested in the coefficients ${a_{n,k,j}}$ such that
$$G_n^{(k)}(x)=\sum_{j\geq0 }{a_{n,...
- 3,255
3
votes
1
answer
131
views
Why is this alternating sum involving Catalan numbers $\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0$ for all $t$?
I need the result that for all $t$,
$$\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0,$$
where $C_{t-i-1}$ is the $(t-i-1)$-th Catalan number. I've checked for $t$ up to ...
- 17k
7
votes
1
answer
608
views
Reciprocity for fans of bounded Dyck paths
This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel ...
- 24.2k
7
votes
2
answers
424
views
A sequence of polynomials related to Catalan numbers
The sequence of polynomials
$$P_n=\sum_{k=0}^{\lfloor(2n-1)/3\rfloor}
\frac{(2n-2k-1)!(2n-2k-2)!}{k!(n-k)!(n-k-1)!(2n-3k-1)!}x^k$$
satisfies apparently the identities
$$0=\sum_{j=0}^nP_{n-j}(P_j-(-x)^...
- 17.9k
16
votes
1
answer
545
views
Conjecture on sum over permutations of products of Catalan numbers
Context
In a recent paper involving entanglement in linear optics, we came across some summations involving Catalan numbers and permutations. In particular, these sums arise when doing integration ...
- 34.3k
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-...
- 13.4k
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 ...
- 63.9k
2
votes
1
answer
141
views
Counting monomials and $q$-Catalan polynomials
Define $N(F)$ to be the number of monomials of a multi-variable polynomial $F$. For example $N(x^2y+3xy-y^5)=3$.
If $\mathbf{x}=(x_1,\dots,x_n)$ and $F_n(\mathbf{x})=\prod_{k=1}^n(x_1+\cdots+x_k)$ ...
- 148k
4
votes
1
answer
221
views
Reference for a definition of Catalan numbers
The $l$-th Catalan number ${2l\choose l}\frac{1}{l+1}$ is equal
to the number of sequences $s_0,\ldots,s_{l+1}$ of length $l+2$ with the following
properties:
(1) $s_0=s_{l+1}=1$ and $s_1,\ldots,s_l$ ...
- 24.2k
3
votes
1
answer
193
views
Sequences that sums up to second differences of Bell and Catalan numbers
Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
Let $g(n)$ be A025480, $g(2n) = n$...
- 34.3k
1
vote
1
answer
139
views
A big list of Narayana-enumerated objects
By a Narayana-enumerated object I mean an object whose count is given by the Narayana number $N(n,k)=\frac{1}{n} {n \choose k} {n \choose k-1}$. Can you give me a reference to some good big list of ...
- 188k
5
votes
1
answer
347
views
Counting monomials and the Catalan numbers
Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\
N((x+z)(x+y)^2)=N(x^3 ...
- 33.8k
2
votes
1
answer
199
views
Sequence of monotone tuples and permutation condition for rotation
I was doing some counting in $S_n$ symmetric group I encountered the following problem, which also someway related to central factorial number.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the ...
- 34.3k
0
votes
1
answer
148
views
What is this numerically-generated function?
This question is an "outgrowth" of https://math.stackexchange.com/questions/4380919/ which led to a numerically-generated two-parameter function $f_b(n)$, where $b$ is the number base $2,3,4,...
- 34.3k
33
votes
3
answers
2k
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 ...
- 156k
5
votes
1
answer
251
views
Hankel determinants for q-Catalan numbers where q is a root of unity?
Let ${C_n}(q)$ be the weight of the Dyck paths of semilength $n$ where the upsteps have weight $1$ and the downsteps which end on height $i$ have weight $q^i$.
They satisfy ${C_n}(q) = \sum\limits_{j ...
- 5,792
6
votes
1
answer
281
views
Another generalization of parity of Catalan numbers
Recently, a question by T. Amdeberhan gathered up many enjoyable proofs that a Catalan number $C_n$ is odd if and only if $n=2^r-1$.
Noam D. Elkies' answer considered $F=\sum_{n=0}^\infty C_n x^{n+1}$....
- 34.3k
4
votes
1
answer
423
views
Generating functions for Hankel determinants of Catalan numbers
The Hankel determinants of the Catalan numbers are well known and can be written as
$d(k,n)= \det \left( C_{k + i + j} \right)_{i,j = 0}^{n - 1}=\prod_{i=1}^{k-1}\frac{\binom{2n+2j}{j}}{\binom{2j}{j}}$...
- 24.2k
11
votes
2
answers
367
views
Kernel of a matrix and the Catalan numbers
Let $B_n$ denote the Boolean lattice of a set with $n \geq 2$ elements and $C_n$ the matrix with entries $c_{i,j}=1$ if $i \leq j$ and $c_{i,j}=0$ else, where $i,j\in B_n$.
Let $M_n:=C_n+C_n^T$ (this ...
- 50.8k
4
votes
1
answer
298
views
Generalization of Catalan numbers
Some time ago I was trying to find a closed form formula for the number of tuples $(a_k)_{k=1}^{n+s}$ of non-negative integers satisfying following conditions:
$\sum_{k=1}^{n+s} a_k = n$,
$\forall m \...
- 24.2k
17
votes
1
answer
885
views
Proof of certain $q$-identity for $q$-Catalan numbers
Let us use the standard notation for $q$-integers, $q$-binomials,
and the $q$-analog
$$
\operatorname{Cat}_q(n) := \frac{1}{[n+1]_q} \left[\matrix{2n \\ n}\right]_q.
$$
I want to prove that for all ...
- 15.8k
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 ...
0
votes
1
answer
287
views
Dyck words and Catalan numbers
One of the many applications of the $n$th Catalan number is to calculate the number of strings consisting of $n$ $X$'s and $n$ $Y$'s, such that any prefix of the string will contain at least as many $...
- 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
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
5
votes
1
answer
416
views
Reference request: recurrence relation for Catalan numbers
I would like to know if the following recurrence relation for Catalan numbers (see mathoverflow.net/questions/191524 and also math.stackexchange.com/questions/2113830) has appeared in a paper or a ...
- 4,713
3
votes
1
answer
366
views
A recurrence relation on Catalan numbers
In the classical problem of bracketing $n$ numbers, I know the response is $C_{n-1}$. I find this
$$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$
but I ...
- 4,713
6
votes
1
answer
362
views
Are the “generalized Catalan numbers” of Dumitrescu–Mulase the "moments" of some "multivariate Wigner semicircle distribution"?
The classical Catalan numbers
$$ C_n = \frac{1}{n+1} \binom{2n}{n}, $$
well-known for their numerous combinatorial interpretations (the second volume of Stanley's Enumerative Combinatorics famously ...
- 56
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 $\...
- 14.2k
5
votes
1
answer
2k
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 ...
- 24.2k
13
votes
5
answers
2k
views
Looking for a combinatorial proof for a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the familiar Catalan numbers.
QUESTION. Is there a combinatorial or conceptual justification for this identity?
$$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^...
