# 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

109
questions

2
votes

1
answer

140
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
$...

5
votes

1
answer

134
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 $...

2
votes

0
answers

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

4
votes

0
answers

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

8
votes

3
answers

855
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+...

0
votes

0
answers

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

2
votes

0
answers

166
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}$...

5
votes

0
answers

189
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} \...

1
vote

0
answers

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

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?

2
votes

0
answers

237
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 &...

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

6
votes

0
answers

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

7
votes

0
answers

250
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,...

3
votes

1
answer

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

5
votes

1
answer

489
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,...

7
votes

2
answers

397
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)^...

16
votes

1
answer

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

4
votes

0
answers

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

2
votes

1
answer

134
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)$ ...

6
votes

0
answers

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

4
votes

1
answer

219
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$ ...

1
vote

1
answer

128
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

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

2
votes

1
answer

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

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

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

6
votes

1
answer

274
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}$....

3
votes

1
answer

185
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
votes

1
answer

403
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}}$...

11
votes

2
answers

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

4
votes

1
answer

286
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 \...

2
votes

0
answers

181
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

257
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

318
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$-...

5
votes

1
answer

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

10
votes

0
answers

345
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^...

6
votes

1
answer

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

7
votes

0
answers

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

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
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]^...

15
votes

1
answer

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

5
votes

0
answers

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

7
votes

1
answer

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

13
votes

1
answer

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

4
votes

1
answer

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

17
votes

1
answer

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

3
votes

0
answers

116
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

402
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

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