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
15 votes
1 answer
349 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
162 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 ...
  • 643
2 votes
1 answer
109 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
97 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
172 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
90 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
311 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
170 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 ...
  • 643
0 votes
1 answer
123 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
236 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
244 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
144 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
267 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
0 answers
130 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} ...
  • 21
11 votes
2 answers
328 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 ...
  • 22.5k
4 votes
1 answer
225 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
178 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
193 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
243 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$-...
  • 19.6k
5 votes
1 answer
324 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
312 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
255 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
6 votes
0 answers
127 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 $\...
  • 823
6 votes
0 answers
168 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
201 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,471
5 votes
0 answers
132 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,471
7 votes
1 answer
485 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 ...
  • 19.6k
12 votes
1 answer
407 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
305 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
797 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
0 answers
74 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,064
5 votes
1 answer
307 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
83 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
0 answers
253 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
1 answer
199 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.3k
13 votes
1 answer
518 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} \, \...
  • 15.8k
3 votes
1 answer
210 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
2 answers
566 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
4 answers
474 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 ...
  • 307
9 votes
1 answer
395 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?
  • 5,029
1 vote
1 answer
223 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 ...
  • 5,885
3 votes
1 answer
206 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
1 answer
461 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
1 answer
926 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
1 answer
271 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 ...
  • 313
30 votes
1 answer
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 ...
21 votes
2 answers
435 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 ...
  • 7,917
10 votes
1 answer
610 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
0 answers
197 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_{...