All Questions
Tagged with catalan-numbers reference-request
16 questions
2
votes
0
answers
172
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}$...
- 43.1k
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
1
vote
0
answers
100
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 ...
- 43.1k
4
votes
1
answer
221
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$ ...
- 17.9k
1
vote
1
answer
139
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
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 ...
- 5,612
6
votes
0
answers
381
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$-...
- 24.2k
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
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
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
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
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
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
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
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
4
votes
2
answers
346
views
Equidistribution of returns and height of first peak of Dyck paths
I believe that it is "well known" that the following two statistics on Dyck paths have symmetric joint distribution:
number of returns to the axis $RET(D)$
height of the first peak (or length of the ...
- 5,792