# Questions tagged [catalan-numbers]

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

450 questions
Filter by
Sorted by
Tagged with
486 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 ...
30 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
53 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$ ...
112 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 ...
39 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. ...
24 views

### The intuitive correspondence between the multiplication schemes (or triangularizations) and -1s 1s sequences.

I am reading Richard A. Brualdi 's book Introductory Combinatorics (5th Edition). In p.273, the author introduced the correspondence between the multiplication schemes for the n numbers a1, a2, ... ...
60 views

### Infinite Catalan Sum involving polynomials

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

### How to prove number of permutations obtained by a deque is C(2(n-1),n-1)?

Given a sequence$\{1,2,\dots,n\}$,you can insert the elements one by one via both ends of the deque(double-ended queue).Then you can pop elements out of the two ends until the deque is empty.At last ...
65 views

### Generalized Catalan number satisfying recursive definition

Wondering if the numbers satisfying the following relationship have a name or known closed-form solution. They show up in enumerating possible configurations of swaps during the execution of a bubble ...
44 views

290 views

### An identity involving Catalan numbers and binomial coefficients.

I stumbled upon the following identity $$\sum_{k=0}^n(-1)^kC_k\binom{k+2}{n-k}=0\qquad n\ge2$$ where $C_n$ is the $n$th Catalan number. Any suggestions on how to prove it are welcome! This came up as ...
95 views

### A recurrence for the number of non-crossing partitions without singletons, using Dyck paths

Let $f(n+1)$ be the number of non-crossing partitions without singletons of $\{1,2,\dots,n+1\}$. There is a well known bijection between the non crossing-partitions (counting also those with ...
1 vote
166 views

32 views

### Monotonic Rectangles using Catalan Numbers

Insert the integers 1,2,...,2n into a 2 by n rectangle of boxes such that the entries are monotonic in rows and columns. How many ways can you do this? Is there a way to prove this without using the ...
416 views

77 views

1 vote
63 views

### Expressing $\log[(2n)!]-\log[n!]-\log[(n+1)!]$ via Stirling's formula and Taylor series

Need explanation on the solution below: Stirlings Formula: $$n! = \sqrt{2\pi n}\left(\frac n e\right)^n\left(1+\frac {1}{12n} + \frac{1}{288n^2}- \frac{1}{51840n^3}+O\left(\frac{1}{n^4}\right)\right)$$...
70 views

### Manipulating Asymptotic Catalan Expansions

I need help explaining the steps below pulled from a proof. Solution: Stirlings Formula: $N! = \sqrt{2\pi N}(\frac N e)^N(1+\frac {1}{12N} + \frac{1}{288N^2}- \frac{139}{51840N^3}+O(\frac{1}{N^4})$ ...
106 views

36 views

### Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal

I am in the process of understanding the Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal. RUU-RRRRUUU is one way where diagonal trespasses. Now, the ...
90 views

### How to find the total number of ways one can reach (5,5) from (0,0)

The total number of ways one can reach $(5,5)$ from $(0,0)$ is $^{10}C_5$ as per a tutorial I am following. I know there are $5$ rights and $5$ ups. So there are 10 steps. But why it is choose $5.$
1 vote
91 views

### Combinatorics proof for number of paths starting from the origin and returning to the origin only at step $2n$.

I have a (one dimensional) random walker, that at each time-step can either step to the right or left, starting from the origin. I wanted to compute the number of paths that this walker can go through ...
32 views

1 vote