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
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 $...
- 5,612
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
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+...
- 509
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
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
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?
- 111
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
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
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
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 ...
- 33
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,...
- 5,612
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 ...
- 163
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
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)$ ...
- 43.1k
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
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$ ...
- 17.9k
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 ...
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 ...
- 43.1k
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 ...
- 685
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,...
- 103
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,612
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}$....
- 524
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$...
- 4,928
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}}$...
- 5,612
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 ...
- 26.5k
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 \...
- 820
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 $...
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
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 ...
- 53
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
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 ...
- 215
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
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
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]^...
- 43.1k
15
votes
1
answer
259
views
A formula for this generating function that is similar to the $qt$-Catalan numbers
I came up with the following conjecture:
$$
\sum_{n \ge 0} z^n \sum_{\mu \vdash n} \frac{ t^{\sum l}q^{\sum a}}{\prod (q^a - t^{l+1})(t^l - q^{a+1})} = \exp\left(\sum_{n \ge 1} \frac{z^n}{n(q^n-1)(t^n-...
- 1,509
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
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
13
votes
1
answer
497
views
What's the dimension of the Lie algebra generated by transpositions on $n$ objects?
Define a Lie bracket on the group algebra of the permutation group $S_n$ in the following way:
$$[\sigma, \tau] = \sigma\circ\tau - \tau\circ\sigma,$$
where $\sigma, \tau \in S_n$, and the ...
- 593
4
votes
1
answer
469
views
A generalisation of the Catalan numbers
Let $n$ be a nonnegative integer. It is well-known that the number of lattice paths from $(0, 0)$ to $(n, n)$ with steps $(0, 1)$ and $(1, 0)$ that are never rising above the line $y=x$ is given by ...
- 155
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
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