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 ...
• 491
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,527
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$ ...
• 1,527
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 ...
• 1,527
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. ...
• 1,527
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, ... ...
• 441
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 ...
• 41
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 ...
• 133
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 ...
• 25.8k
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,111
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

• 615
77 views

• 225
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)$$...
• 11
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})$ ...
• 1
106 views

• 243
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 ...
• 2,098
32 views

• 996
1 vote
79 views

How do I go from Generating function to Asymptotic formula for Catalan Numbers

The Catalan Numbers wiki page states that you can prove the asymptotic formula using generating functions, and I was wondering how?
• 11