**1**

vote

**1**answer

153 views

### Solving for f given constraint involving f(x, y) and f(xy, y)

I am interested in a weighted version of the Catalan numbers. The generating function for this case,
$$ f(x, y) = \sum_s \sum_n f_{s n} x^s y^n $$
(where the $y^n$ term is the weight), obeys the ...

**2**

votes

**0**answers

53 views

### Is there a distance function on Dyck/Tamari words of arbitrary length?

Consider sequences of well-formed parentheses (or up/down sequences) of the type counted by the Catalan numbers. See http://www-math.mit.edu/~rstan/ec/catalan.pdf
These are sometimes called Dyck ...

**18**

votes

**1**answer

379 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 ...

**8**

votes

**3**answers

831 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 ...

**3**

votes

**0**answers

60 views

### Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where
$$
D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( \sqrt{1-4z+4z^{p+...

**10**

votes

**2**answers

359 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\{
...

**7**

votes

**1**answer

260 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, ...

**12**

votes

**1**answer

755 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 ...

**11**

votes

**1**answer

1k 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 ...

**0**

votes

**1**answer

397 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**10**

votes

**1**answer

265 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.
...

**4**

votes

**0**answers

121 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 ...

**22**

votes

**3**answers

911 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 ...

**2**

votes

**1**answer

180 views

### Even more generalized Catalan numbers

What is the number of ways to parenthesize $n$ elements using applications of operators of arbitrary arities larger than or equal to $2$? For example, for $n=3$, there are $3$ ways:
$$
abc, a(bc),(ab)...

**34**

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 ...

**3**

votes

**1**answer

148 views

### Why are the dinv-statistic and the partition length equidistributed?

A partition of $n$ is a weakly decreasing sequence of natural numbers $\lambda = (\lambda_1, \lambda_2, \dots)$ such that $\sum \lambda_i = n$. Its length $l(\lambda)$ is the number of positive ...

**3**

votes

**1**answer

659 views

### What does the $q$-Catalan Numbers count?

I had completed a paper describing the $q$-Catalan numbers, which is the $q$-analog of the Catalan numbers.
The $n$-th Catalan numbers can be represented by:
$$C_n=\frac{1}{n+1}{2n \choose n}$$
and ...

**3**

votes

**1**answer

229 views

### Semi-planar partition monoid/algebra

Here are some beginner questions on partition algebras...
I am trying to understand the monoid called $P_k$ in Tom Halverson, Arun Ram, Partition Algebras. For the sake of simplicity, let $k$ be a ...

**9**

votes

**3**answers

605 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 ...

**6**

votes

**4**answers

1k 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}$ - ...

**2**

votes

**2**answers

958 views

### Application of Catalan number [closed]

Hi guys just a quick questions
What are the real life application of catalan numbers?
Thanks a lot!

**10**

votes

**5**answers

1k 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 ...

**13**

votes

**0**answers

434 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$ ...

**4**

votes

**2**answers

267 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 ...

**22**

votes

**5**answers

4k 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 ...

**7**

votes

**2**answers

732 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 ...

**3**

votes

**2**answers

5k views

### Combinatorial proof of a recurrence for the Catalan numbers

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers:
$$
C_{n+1}=\frac{4n+2}{n+2} C_n.
$$
Thanks!~

**4**

votes

**1**answer

385 views

### Counting $(n,k)$-forests of binary trees

Given $k,n\in\mathbf{N}$ with $n\ge k$, define the set $\mathcal{F}(k,n)$ of $(k,n)$-forests of binary rooted trees (where a $(k,n)$-forest is a collection of $k$ rooted trees, which have a totality ...

**26**

votes

**4**answers

2k 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 ...

**29**

votes

**1**answer

916 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$:
$$...