All Questions
Tagged with enumerative-combinatorics catalan-numbers
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
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
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
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
2
votes
1
answer
141
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)$ ...
- 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
347
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 ...
- 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
0
votes
1
answer
148
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
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
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
3
votes
0
answers
123
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,644
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
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
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