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

Filter by
Sorted by
Tagged with
3
votes
1answer
181 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}}$...
2
votes
0answers
97 views

Generating Fuss-Catalan numbers using the regular Catalan number

Let $A_{n}(p,r)$ denote the $n$-th Fuss-Catalan number with parameter $(p,r)$. $A_{n}(p,r)$ has the closed form $A_{n}(p,r) = \frac{r}{np+r} {np+r \choose n}.$ For example, $A_{n}(2,1) = \frac{1}{n+1} ...
11
votes
2answers
292 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
1answer
206 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
0answers
174 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
1answer
131 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
0answers
200 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$-...
4
votes
1answer
280 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
0answers
296 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
1answer
196 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 ...
6
votes
0answers
118 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
0answers
158 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
5answers
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
1answer
159 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
0answers
114 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
1answer
404 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 ...
12
votes
1answer
341 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
1answer
253 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
1answer
748 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 ...
2
votes
0answers
57 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
1answer
236 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
1answer
81 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
0answers
213 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
1answer
173 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
1answer
497 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
1answer
178 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
2answers
507 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
4answers
431 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
1answer
349 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
1answer
207 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
1answer
200 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
1answer
433 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
1answer
892 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
1answer
215 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
1answer
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 ...
19
votes
2answers
421 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 ...
9
votes
1answer
523 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
0answers
185 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_{...
11
votes
2answers
1k 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-...
7
votes
1answer
287 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 $...
12
votes
1answer
334 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
2answers
293 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
1answer
167 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 ...
5
votes
1answer
463 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
2answers
540 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
2answers
384 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
2answers
513 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
1answer
330 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
0answers
412 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
2answers
186 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 ...