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
35 questions
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
5
votes
1
answer
613
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....
- 43.1k
4
votes
0
answers
208
views
More 3-connected cubic graphs with all 2-factors of same cycle type?
The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...
- 13.4k
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
4
votes
1
answer
597
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), ...
- 165
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
3
votes
1
answer
366
views
A recurrence relation on Catalan numbers
In the classical problem of bracketing $n$ numbers, I know the response is $C_{n-1}$. I find this
$$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$
but I ...
- 149
3
votes
1
answer
224
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 ...
- 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
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