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
38
votes
4
answers
2k
views
A family of words counted by the Catalan numbers
In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan ...
- 2,339
36
votes
2
answers
1k
views
Is there a combinatorial reason that the (-1)st Catalan number is -1/2?
The $n$th Catalan number can be written in terms of factorials as
$$ C_n = {(2n)! \over (n+1)! n!}. $$
We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$:
$$...
- 14k
35
votes
4
answers
4k
views
How does this relationship between the Catalan numbers and SU(2) generalize?
This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...
- 118k
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
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 ...
- 15.8k
27
votes
5
answers
7k
views
Probability of a Random Walk crossing a straight line
Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
- 733
24
votes
8
answers
4k
views
Higher-dimensional Catalan numbers?
One could imagine defining various notions of higher-dimensional Catalan numbers,
by generalizing objects they count.
For example, because the Catalan numbers count the triangulations of convex ...
- 151k
22
votes
1
answer
883
views
q-Catalan numbers from Grassmannians
In this question by $q$-Catalan numbers I mean the $q$-analog given by the formula $\frac{1}{[n+1]_q}\left[{2n\atop n}\right]_q$. The polynomial $\left[{2n\atop n}\right]_q$ represents the class of ...
- 85.5k
22
votes
2
answers
467
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 ...
- 8,659
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
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
16
votes
0
answers
558
views
Catalan objects associated to a univariate polynomial
Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data:
a noncrossing matching on $2n$ ...
- 6,282
15
votes
5
answers
2k
views
enumerative meaning of natural q-Catalan numbers
Define $[n]=(1-q^n)/(1-q)$ and $[n]!=[1][2][3] \cdots [n]$, so that $[2n]!/[n]![n+1]!$ is a polynomial in $q$ (the most algebraically natural $q$-analogue of the Catalan numbers); what enumerative ...
- 19.7k
15
votes
1
answer
1k
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 ...
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
14
votes
1
answer
2k
views
When does a Catalan number equal a Fibonacci number?
The $n=3$'rd Catalan number (A000108) is $1,1,2,5$ : $\frac{\binom{2n}{n}}{n+1}=\frac{\binom{6}{3}}{4}=\frac{20}{4}=$ 5.
The $n=4$'th Fibonacci number (A000045) is $1,1,2,3,5,...$ : 5.
Q. Which ...
- 151k
14
votes
1
answer
391
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 ...
- 8,659
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
13
votes
1
answer
1k
views
Lots of combinatorial interpretations of Catalan numbers
During a lecture I gave on Catalan numbers, I pointed out that that it
is possible to give a continuum number of combinatorial
interpretations of these numbers. See the solution to (f$^5$) on
page 54 ...
- 50.8k
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
13
votes
1
answer
564
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} \, \...
- 17k
12
votes
1
answer
553
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 ...
- 5,612
12
votes
1
answer
509
views
Probability of a graph procedure
We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
- 175
12
votes
2
answers
778
views
Determinant of a checkerboard Hankel matrix with Catalan numbers
My goal is to compute
\begin{equation}
I = \det \left(\mathbf{I} + \mathbf{A}\right)
\end{equation}
where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers:
$$
\left\{
...
- 840
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
11
votes
2
answers
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-...
- 1,190
11
votes
2
answers
604
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\...
- 1,305
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
10
votes
1
answer
752
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_{...
- 2,896
10
votes
2
answers
386
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,112
10
votes
1
answer
344
views
Non-abelian freeness of SU_2
The distribution of the trace of a random element of $SU_2$ is the Sato-Tate distribution.
The analogue of the Gaussian distribution in free probability theory is the Wigner semicircle distribution.
...
- 148k
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
9
votes
3
answers
1k
views
Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?
This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...
- 18.4k
9
votes
2
answers
709
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 "...
- 43.1k
9
votes
3
answers
1k
views
Intuition Behind a Decimal Representation with Catalan Numbers
From $0 = 0.5 - 0.5 = 0.5 - \sqrt{0.25}$, we can adjust the subtrahend slightly to obtain
$$0.5 - \sqrt{0.249} = 0.001\ 001\ 002\ 005\ 014\ 042\ldots$$
where the decimal representation contains the ...
- 7,831
9
votes
1
answer
470
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,792
9
votes
0
answers
213
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_{...
- 5,612
8
votes
2
answers
810
views
Modular congruences related to sums of Catalan numbers
I am curious if somebody can be helpful concerning the following
experimental observation:
There exist two rational sequences $\alpha_0,\alpha_1,\dots$ and
$\beta_0,\beta_1,\dots$, both with values ...
- 17.9k
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
7
votes
4
answers
3k
views
A generalization of Catalan numbers
It is well-known that the $n$th Catalan number is equal to $(n+1)^{-1}\binom{2n}{n}$. A long time ago I had wondered what happens if you look at the sequence generated by $(n+k)^{-1}\binom{pn}{n}$ - ...
- 6,962
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
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
1
answer
318
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 $...
- 26.5k
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
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
7
votes
0
answers
530
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 \...
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
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
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
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