Questions tagged [catalan-numbers]

For questions on Catalan numbers, a sequence of natural numbers that occur in various counting problems.

503 questions
Filter by
Sorted by
Tagged with
1 vote
78 views

Deriving the generating function for the Catalan triangle

I'm hoping for help in deriving the two-variable generating function for the Catalan triangle, also known as a truncated version of Pascal's triangle. There are a few variations floating around, so to ...
• 2,209
1 vote
50 views

Find the number of lattice paths weakly under a slope $y = \mu x$

How many lattice paths are there from an arbitrary point $(a,b)$ to another point $(c,d)$ that stay weakly (i.e. it can touch the line) under a slope of the form $y = \mu x$, with $\mu \in \mathbb{N}$?...
210 views

• 195
1 vote
99 views

Counting the number of possible sequences increasing by no more than one [closed]

Count the number of sequences of integers $a_1, a_2, \dots, a_n$ such that $$a_1 = 0 \quad\text{and}\quad 0 \leq a_{i+1} \leq a_i + 1 \quad\text{for}\quad 1 \leq i < n.$$ At first, I was ...
• 61
57 views

Combinatorial explanation of Catalan asymptotics

It is well-known that the Catalan numbers have an asymptotic approximation $$C_n\sim \frac{4^n}{\sqrt{\pi}n^{3/2}}.$$ I am curious about combinatorial interpretations of this formula, rather than a ...
1 vote
50 views

What is the difference between counting plane tree and binary tree by Catalan numbers? [duplicate]

Problems: Prove that the number of plane trees with $(n+1)$ vertices is $n-th$ Catalan number $C_n$. For this problem: I have found a solution in a post on Mathstack Prove that number of non-...
• 1,238
165 views

Passenger entrance/exit combinations

In question is: The number of possible ways a vehicle with capacity $K$ can pickup and drop off $n$ passengers in a single tour, while each passenger has an individual pickup and dropoff location. ...
1 vote
27 views

I want to count the multiplicity of specific peak sets occurring in a standard shifted tableau with some restrictions. Possibly using path counting?

Ok first some definitions: Let a shifted diagram of some strict partition $\lambda$ be a Young tableau whose $i^{th}$ row is shifted $i-1$ spaces to the right, (I use french notation, and start ...
• 31
1 vote
205 views

55 views

Formal Power Series for Recursion where Successor is Linear Combination of all Predecessors

I am trying to solve a recursion of the form \begin{equation*}a_n=\sum_{j=1}^{n-1} k_{j,n} \cdot a_j + d_n \end{equation*} where $k_{j,n}$ and $d_n$ are constants depending on $j,n$ and $n$, ...
• 115
153 views

A curious identity for powers of the generating function of the Catalan numbers.

For a power series $\displaystyle f(x)=\sum_{n\geq 0}a_n x^n$ let $\displaystyle[f(x)]_r=\sum_{n\geq r} a_n x^n.$ Let $\displaystyle c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the ...
• 1,379
39 views

Balanced binary sequence with odd length.

I am facing an equal problem to this but I can't seem to have an algorithm that would allow me to count it. The problem: Let X(n) be the set of all possible balanced binary sequences, where 0's ...
286 views

• 49
1 vote
49 views

Dyck paths without centered tunnels

This is from Stanley's Catalan Numbers, problem 36: I have difficulty understanding the problem: there is no $L$, $L$'s endpoints lie on $P$ (what is $P$?) and every point of $L$ lies on or below $D$,...
• 719
1 vote
74 views

Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps

From Stanley's Catalan Numbers, problem 28: Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps. I don't understand what this means. If after a sequence of ups, there are equal number or ...
• 719
39 views

How to prove $\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$? [duplicate]

How to prove the following identity? $$\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$$ where $C_k$ is the $k$th Catalan number, $C_n=\frac{1}{k+1}\binom{2k}{k}$. This question is similar to this but ...
• 13