38
votes
Accepted
Looking for a combinatorial proof for a Catalan identity
By the ballot theorem, $\frac{k}{n} \binom{2n}{n+k}$ is the number of Dyck paths, i.e. $(1,1), (1,-1)$-walks in the quadrant, from the origin to $(2n-1, 2k-1)$. You need to concatenate a pair of those ...
- 3,927
22
votes
Proving an identity about Catalan numbers
Algebraically, this identity is
$$\sum_{n=0}^\infty C(n) x^n (1-x)^{n+1} = 1, $$
which is a consequence of the generating function
$$\sum_{n=0}^\infty C(n) x^n = \frac{1-\sqrt{1-4x}}{2x}.$$
- 17k
19
votes
Accepted
Proving an identity about Catalan numbers
$C_n$ is the number of Catalan sequences $(x_1,\ldots,x_{2n})$ of $\pm 1$ with zero sum and non-negative prefix sums $x_1+\ldots+x_k$, for $k=1,\ldots,2n$. Note that any such sequence contains an ...
- 109k
14
votes
Math journal publishing work related to combinatorics, probability, counting problems etc.?
You may want to try Combinatorics, Probability & Computing or The Electronic Journal of Combinatorics. Your chances at getting published depend on the quality of your paper.
13
votes
Oddity of generalized Catalan numbers: Part I
I believe the answer to Question 1 is "yes". The easiest proof I know for the parity of the regular Catalan numbers uses the recurrence
$$
C_n=C_0C_{n-1}+C_1C_{n-2}+\cdots+C_{n-1}C_0.
$$
From this it ...
- 2,339
13
votes
Looking for a combinatorial proof for a Catalan identity
More generally,
$$\sum_{k\ge1} \frac{k}{m}\binom{2m}{m-k}\cdot\frac{k}{n} \binom{2n}{n-k} = C_{m+n-1}.$$
This can be proved by the same reasoning as in Timothy Budd's answer.
This formula gives the ...
- 17k
12
votes
Accepted
Curious Catalan convolutions
For the first identity, see additional problem A33 in my book Catalan Numbers. References are given to bijective proofs by Andrews and Nagy.
- 50.8k
12
votes
Accepted
A matrix identity related to Catalan numbers
After unpacking the equation $$\left( {{C(i+j,k+2)}} \right)_{i,j = 0}^{n - 1}=A_{n}G_{n,k} A_{n}^T$$
we see that we want to prove the identity
$$C(i+j,k+2)=\frac{k+2}{(2i+2j+k+2)}\binom{2i+2j+k+2}{i+...
- 85.5k
12
votes
Looking for a combinatorial proof for a Catalan identity
Not sure if this is what you look for, but still:
$$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^2= \sum_{k=1}^n \big[1-\frac{(n+k)(n-k)}{n^2}\big]\binom{2n}{n+k}\binom{2n}{n-k}$$
$$=\sum_{k=1}^n ...
- 34.3k
11
votes
Accepted
Show a sequence of sums involving Catalan Numbers converges
By 'magic' and a computer (see the book "A=B" by Petkovsek, Wilf and Zeilberger https://www.math.upenn.edu/~wilf/AeqB.html) the numbers $\mathcal{E}_s$ satisfies the recurrence
$\sum_{k=0}^3 P_k(s) \...
- 1,907
11
votes
Accepted
What's the dimension of the Lie algebra generated by transpositions on $n$ objects?
In "L'algèbre de Lie des transpositions" (arXiv:math/0502119
), Ivan Marin shows the Lie algebra generated by transpositions is the product of a 1 dimensional Lie algebra, and of a semi-...
- 8,524
10
votes
Accepted
generating $q$-Catalan numbers
The functions
$$
C_n(q)=\sum_{P\in\square_n}q^{area(P)}
$$
satisfy the following recurrence relation
$$
C_n(q)=\sum_{k=1}^nq^{k-1}C_{k-1}(q)C_{n-k}(q).\tag{1}
$$
Proof.
(taken from the book "The q, t-...
- 5,624
10
votes
How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$
The ordinary generating function of the $C_k$ is well-known:
$$\sum_{k \geq 0} C_k x^k = \frac{1 - \sqrt{1 - 4x}}{2x}$$
This can be deduced from the problem of counting binary planar trees and ...
- 53.3k
9
votes
How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$
$k$-th summand is the probability that a symmetric random walk with steps $\pm 1$ returns first time to the initial point at time $2(k+1)$. Since this random walk is recurrent, the sum of ...
- 109k
9
votes
Accepted
Counting monomials and the Catalan numbers
Any monomial $P:=\prod x_i^{c_i}$ of degree $\sum c_i=n$ maps to a non-zero constant after symmetrization
$$
P\to \Phi(P):=G_{\mathfrak{S}_{n+1}}\frac{P}{(x_1-x_2)(x_2-x_3)\ldots (x_n-x_{n+1})}.
$$
...
- 109k
9
votes
Accepted
A sequence of polynomials related to Catalan numbers
I find a slightly different initial condition for the recurrence:
$$0=\sum_{j=0}^nP_{n-j}(P_j-(-x)^j)$$
for $n\ne 1$; for $n=1$ the sum is $-1$. It's easy to derive a formula for the generating ...
- 17k
8
votes
Reference request: Heyting algebra structure on Catalan numbers
I found a reference: "Dyck algebras, interval temporal logic and posets of intervals", which discusses these Heyting algebras (though not from a topos-theoretic perspective).
- 8,659
8
votes
Intuition behind Hook Length Formula
Here is a bijection to Dyck paths (or to well-formed bracketings):
Take a SYT of shape $2\times n$ (so it contains the numbers $\{1,\ldots,2n\}$, and we aim to form a word of $n$ up-steps (opening ...
- 3,271
7
votes
Accepted
Products of Catalan numbers
It should be possible here to mimic the same argument that Erdos uses in his paper "On some divisibility properties of $\binom{2n}{n}$".
Suppose that $c(n)=c(a_1)c(a_2)\cdots c(a_k)$ and $n$ is large ...
- 85.5k
7
votes
Accepted
Is the order on repeated exponentiation the Dyck order?
EDIT: I can complete half of the proof, showing that the magma order refines the Dyck order.
Following Martin Rubey's comment, there is a standard bijection between association orders and Dyck paths ...
- 82.6k
7
votes
Accepted
Proofs of some combinatorial identities
Partial answer: Your first identity is
\begin{equation}
\sum\limits_{k=0}^n \left(-1\right)^k \dbinom{2k}{k} \dbinom{2\left(n-k\right)}{n-k} = \left[n \text{ is even}\right] 2^n \dbinom{n}{n/2} ,
\end{...
- 33.8k
7
votes
Oddity of generalized Catalan numbers: Part I
The answer to QUESTION 1 is Yes.
The following proof simplifies my suggestion in the comments.
According to the OEIS entry, the shifted generating function
$$
g(x) = \sum_{n=0}^\infty C_{2,n} x^{n+...
- 79.9k
7
votes
Accepted
Mysterious symmetry - in search for a bijection
Oliver Pechenik and I have some partial progress to report. Maybe someone else can see how to supply the remaining missing ingredients.
First, let's establish some notation.
We say your ascent ...
- 1,989
7
votes
Coincidences between average Catalan tableaux
This is not a solution, but rather a long comment. Let
$f^{a,b}$ denote the number of standard Young tableaux (SYT)
of shape $(a,b)$. The number of SYT $T$ of shape $(n,n)$
with $T_{1d}=k$ is $f^{d-1,...
- 50.8k
7
votes
Accepted
A formula for this generating function that is similar to the $qt$-Catalan numbers
This identity can be proved using the results in Garsia and Haiman's paper "A Remarkable q,t-Catalan Sequence and q-Lagrange Inversion". In particular theorem 3.10(e) gives
$$\sum_{\mu \...
- 85.5k
7
votes
Accepted
Reference request: recurrence relation for Catalan numbers
T. Koshy, Catalan Numbers with Applications (Oxford, 2009), page 322, proves a very similar identity:
$$C_n=\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}(-1)^{k-1} \binom{n-k+1}{k} C_{n-k}$$
$$\...
- 188k
7
votes
Accepted
Conjecture on sum over permutations of products of Catalan numbers
The problem naturally fits in the framework of breakpoint graphs (per Peter Taylor's observation), which makes it possible to obtain a differential equation for the generating function
$$H(x,u,s_1,s_2,...
- 34.3k
6
votes
Accepted
Is there a combinatorial interpretation or bijective proof for this Catalan number identity?
There is an obvious bijective proof of the identity
$$ 2 \binom{2n}{n} + 2 \binom{2n}{n + 1} = \binom{2n+2}{n+1}$$
and also a bijective proof of
$$ 2\binom{2n}{n} - 2 \binom{2n}{n+1} = 2C_n,$$
see ...
- 7,239
6
votes
Distribution of the area statistic for Catalan paths
An attempt to provide the whole distribution using analytic combinatorics (though one answer is already accepted). In particular, we can obtain the first and the second moment using this technique (...
- 247
6
votes
Accepted
Number of tilting modules
Let $e$ be the idempotent in $B$ such that $Be$ is the direct sum of the $n-l$ indecomposable projective-injectives which do not have projective proper submodules.
Then the two-sided ideal $BeB=Be$ ...
- 3,686
Only top scored, non community-wiki answers of a minimum length are eligible