# Questions tagged [catalan-numbers]

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

488 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

### Lattice Paths $C_{n}$ & $C_{n-1}$

I'm trying to see if I'm correct with a general approach to solving these lattice path problems using the commonly known reflection proof and the Catalan numbers. If we want to see how many paths we ...
81 views

### Catalan numbers in numerical sequences

How to show that the number of sequences of the form ($a_1$, $a_2$, ..., $a_n$) when $\sum_{k=1}^i(a_k)$ >= $i$ for each $i$ and $\sum_{k=1}^n(a_k)$ = $n$ is equal to the corresponding Catalan ...
22 views

### Counting Paths in the XY Plane (Discrete math) [duplicate]

I need help with the following mathematical task: A particle moves in the xy-plane according to the following rules: U: (m, n) → (m+1, n+1) L: (m, n) → (m+1, n-1) where m and n are integers. I need ...
109 views

### $n$- transposition permutations in $S_{2n}$ which decompose a $2n$-cycle into $n+1$ cycles

I was learning about Catalan numbers online. I have understood the combinatorial argument, recurrence relation and generating function based proofs of Dyck words and Dyck paths. Let $S_{2n}$ be the ...
394 views

58 views

### Let $a_n$ denote the number of circular words of length $2n + 1$ over the alphabet A = {0,1} in which exactly $n$ zeroes occur.

I started studying on discrete mathematics and I came across the following "advanced question" in my textbook: Let $a_n$ denote the number of circular words of length $2n + 1$ over the ...
81 views

### How to count pairs with Catalan distribution

Say I have a set of $n$ pairs, such that I have a total of $2n$ elements. I arrange them in pairs following a Catalan distribution, i.e. if I lay them in a 1D line, I have no crossing (See the ...
1 vote
94 views

### Catalan numbers, paths on a grid

I'm struggling to understand the concept of the idea. Some questions "push" me to use the reflection method which is hard for me to imagine and understand. I prefer to look at it as a ...
110 views

### Modify the lattice path for Catalan Number

It is known that $C_{n}$ ($n$-th Catalan number) is the number of monotonic lattice paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal. A monotonic ...
216 views

### A series sum involving Catalan numbers

I was trying to compute $$\sum_{k=0}^{n} \left(-\frac{1}{2}\right)^k \, \binom{2k}{k} \, \frac{k}{k+1} = \sum_{k=0}^n \left(-\frac12\right)^k k C_k$$ (where $C_k$ is the $k^{\rm th}$ Catalan number) ...
345 views

### Number of balanced bracket sequences with given prefix and suffix

I've been trying to solve the following problem: Find the number of balanced bracket sequences of size $N+M+K$ which start with a prefix of $N$ continuous opening brackets and end with a suffix of $M$ ...
51 views

51 views

### Find coefficient in series expansion of $x^2C^3(x)$

I need to find the $n$-th coefficient of the expression $P(x)=x^2C^3(x)$ where $C(x)$ is the generating function for the Catalan numbers: $$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$ I'm trying to solve the ...
89 views

### A problem about diagonal lattice path [duplicate]

The problem I am facing is: Suppose we have a diagonal lattice path which is defined over a $x-y$ coordinate plane. We can go either from $(i,j)$ to $(i+1,j+1)$ or from $(i,j)$ to $(i+1,j-1)$. Then ...
111 views

### Verification of $(m+1)| \binom{2m}{m}$ and interpretation

While examining the central binomial coefficients, I noticed that $(m+1)$ always seemed to divide $\binom{2m}{m}$. I would like to confirm that a short proof I have found, using Hall's theorem, is ...
201 views

359 views

### Conjecture: $\frac1\pi=\sum_{n=0}^\infty\left((n+1)\frac{C_n^3}{2^{6n}}\sum_{k=0}^n(-1)^k{n\choose k}{\frac{(n-k)(k-1)}{(2k-1)(2k+1)}}\right)$

Let $C_n$ denote the $n$-th Catalan number defined by $$C_{n}={\frac {1}{n+1}}{2n \choose n}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\quad \left(n\geqslant 0\right).$$ Next, we define ...
1 vote
69 views

### Analytic formula for $E(\rho):=\sum_{m=0}^\infty \mu_m(\rho)/m!$, with $\mu_m(\rho) := \sum_{k=0}^{m-1}\dfrac{\rho^k}{k+1}{m \choose k}{m-1\choose k}$

Let $\rho \in (0,\infty)$ and for any integer $m \ge 1$, define $\mu_m \ge 0$ by $$\mu_m := \sum_{k=0}^{m-1}\frac{\rho^k}{k+1}{m \choose k}{m-1\choose k}.$$ Finally define $E \ge 0$ by  E := \sum_{...
643 views

### Intuitive Explanation for Number of Dyck Paths Never Going Above Diagonal of a Rectangle

Suppose we have a an $a\times{}b$ rectangle whose bottom-left corner is at $(0,0)$ and whose upper-right corner is at $(b,a)$. Let $a$ and $b$ both be positive integers, and let $b\geq{}a$. If $a$ and ...
124 views

### How is the diagonal constraint in lattice path needed for the Catalan proofs?

I have been reading about the Catalan numbers and how they are they appear in many problems such as: lattice paths valid pair of parenthesis mountains with up/downstrokes non-crossing handshakes ...
1 vote
74 views

### Counting all possible pairs of parenthesis

If we want to count how many possible pairs $n$ of parenthesis we have when $n = 1$ then I think the way to count is $2 \choose 1$ since if we have $2$ symbols and we pick $one$ position to place $1$ ...
129 views

### Why are the catalan numbers giving the unique/correct patterns from all the combinations?

I am reading about catalan numbers and they are considered to represent the number of valid pair of parentesis, mountains etc. Although the number checks out correct when comparing against specific ...
41 views

### How do we handle the factorials in the binomials/choice numbers?

Apparently the following is a known equality: $\frac{1}{n + 1} {2n \choose n} = \frac{2n!}{n!(n + 1)!} = \frac{1}{2n + 1}{2n + 1 \choose n}$ but I can't really figure out how to produce the equality. ...
I was solving this problem: Given a coin that lands on heads with $p$ probability, what is the probability that a series of coin flips will end with exactly one more head than tail? For instance, H ...