Questions tagged [catalan-numbers]

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

Filter by
Sorted by
Tagged with
11 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1,527
1 vote
0 answers
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$ ...
user avatar
  • 1,527
2 votes
1 answer
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 ...
user avatar
  • 1,527
0 votes
1 answer
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. ...
user avatar
  • 1,527
0 votes
0 answers
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, ... ...
user avatar
  • 441
0 votes
1 answer
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 ...
user avatar
4 votes
0 answers
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 ...
user avatar
  • 41
3 votes
1 answer
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 ...
user avatar
  • 133
2 votes
1 answer
44 views

Calculating the Moments of the Marchenko-Pastur Distribution

I'm trying to follow a proof of the Marchenko-Pastur theorem. In particular I'm trying to show that the kth moment of the Marchenko-Pastur distribution: $$ a_k = \int_{(1-\sqrt{\gamma})^2}^{(1+\sqrt{\...
user avatar
  • 194
1 vote
1 answer
76 views

Solve Summation of Catalan Convolution?

Can someone help me solve this. Wolfram alpha says it converges to But actually, I have no idea, how to solve it.
user avatar
0 votes
1 answer
58 views

Generating function of $f(n) = C_n - \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$

I have combinatorially found this recurrence for a class of Dyck paths: $$f(n) = C_n - \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$$ where $C_n$ is the $n$-th Catalan Number. Now I want to write the generating ...
user avatar
2 votes
0 answers
37 views

How to find lattice path using catalan numbers? [closed]

I don't understand how to use the Catalan numbers in order to find a path from (0,0) to (x,y) without going over a certain function and while stepping in a specific point. for example: find the ...
user avatar
1 vote
1 answer
90 views

Find the generating function of $f(n) = \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k}$

I want to find the generating function of $f(n) = \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k}$, where $C_k$ is the $k$-th Catalan number. So, using the definition of an ordinary generating function: $$...
user avatar
7 votes
2 answers
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 1,111
1 vote
0 answers
166 views

Find the number of 0,1 sequence with length 2m

Suppose a sequence {$a_n$} with $2m$ terms, including $m$ terms equal to $1$ and m terms equal to $0$. Such a sequence is defined as normal if For arbitrary $k \leq 2m$, the number of terms equal to $...
user avatar
  • 11
0 votes
1 answer
63 views

Number of ways to group $n$ operands

My textbook claims there are... Two ways to group $3$ operands, i.e. $(a_1+a_2)+a_3$ and $a_1+(a_2+a_3)$; Five ways to group $4$ operands, i.e.... $((a_1+a_2)+a_3)+a_4$, $(a_1+(a_2+a_3))+a_4$, $a_1+(...
user avatar
0 votes
0 answers
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 ...
user avatar
7 votes
5 answers
416 views

How to find the sum $\sum_{k=1}^{\lfloor n/2\rfloor}\frac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}$

Let $n$ be positive integer, find the value $$f(n)=\sum_{k=1}^{\lfloor n/2 \rfloor}\dfrac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}. $$ I have found $$ f(2)=1, \quad f(3)=2, \quad f(4)=5, \quad f(...
user avatar
2 votes
1 answer
85 views

Non-crossing partitions without singletons

A partition of $[n]$ is non-crossing if whenever four distinct elements $1\le a < b < c < d \le n $ are s.t. $a, c$ are both in one block and $b, d$ are both in another one, then the two ...
user avatar
0 votes
2 answers
45 views

Generating function and integer sequence that arise from this function

I am looking for the power series arising from the generating function $f(x)$ that solves the following equation: $\alpha^{2}x^{3}+3\alpha x^{2}f(x)+3xf(x)^{2}=\beta$ for some $\alpha,\beta\in \mathbb{...
user avatar
4 votes
2 answers
288 views

Alternative proof of an intereting identity of Catalan's Numbers and central binomial coefficients

Some time ago i got from Polya's Urn Scheme that for the n-th Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ and the central binomial coefficient takes place the identity $$\sum_{n = 0}^\infty\frac{...
user avatar
  • 615
0 votes
1 answer
77 views

Finding Recurrence

Let be $C_k$, $k^{th}$ Catalam's number and $$f(n)=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}C_k\text{.}$$ I want to prove the following recurrence: $$f(n+1)+(-1)^{n}=f(0)f(n)+f(1)f(n-1)+\cdots+f(n)f(0)\text.{...
user avatar
  • 89
1 vote
0 answers
60 views

Non-crossing Partition

I'm trying to solve following problem, and I got stuck. Let be $[n]=\{1,...,n\}$. Def. A partition $\pi$ of $[n]$ is called non-crossing, if $a$ and $b$ belong to one block and $x$ and $y$ to another, ...
user avatar
  • 89
2 votes
0 answers
27 views

Self-composition of extended Motzkin numbers vs. doubled Catalan numbers

I am looking for a combinatorial proof (or a reference to such) of the following fact related to Catalan and Motzkin numbers. Consider the extended Motzkin number sequence, where the $n$th term ($n\ge ...
user avatar
5 votes
1 answer
204 views

Riordan numbers recurrence

Let be $C_n$ the $n^{th}$ Catalan's number. Well, I have the following relation: $$f(n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}C_k\text{.}$$ I would like to know, if there is a way to obtain the ...
user avatar
  • 89
3 votes
1 answer
81 views

Probability of hitting time conditional on the last step of Simple random walk.

I have a trouble proving the below result: Let $\left(S_{n}\right)_{n \geq 0}$ be a simple random walk defined by $p(1)=p$ and $p(-1)=q$ where $p+q=1$ Let $k$ be a positive integer. Prove: $$ P_{0}\...
user avatar
1 vote
0 answers
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)$$...
user avatar
  • 11
0 votes
1 answer
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})$ ...
user avatar
  • 1
2 votes
1 answer
106 views

Why should there necessarily be a right parenthesis with equal left and right parentheses before it, in an illegal sequence of parentheses?

From this answer, proving the formula $\binom{2n}{n}-\binom{2n}{n+1}$ for the number of "legal" (ie, "balanced" or "properly matched") sequences of parentheses of length $...
user avatar
5 votes
0 answers
131 views

Simple proof that the Catalan numbers are integers

As the Catalan numbers are defined as $$C_n = \frac{1}{n+1} \binom{2n}{n},$$ it is not immediately clear that they are integers. To show that they are, there's a relatively basic approach involving ...
user avatar
2 votes
0 answers
70 views

Generating function for the squared Catalan numbers

The squares of the Catalan numbers: 1, 1, 4, 25, 196, 1764... are given in OEIS A001246. In the OEIS entry two ordinary generating functions for the series are given in terms of elliptic integrals/...
user avatar
0 votes
0 answers
36 views

Probability problem based on Catalan number

I was trying to solve the following problem: $n$ boys and $n-1$ girls stand in a queue. The probability that the number of boys ahead of every girl is at least one more than the number of girls ahead ...
user avatar
  • 631
0 votes
1 answer
61 views

Expressing the Catalan numbers as a function of the Taylor series of $e^{-x}$

Is there a known way of expressing the Catalan numbers or the generating function of the Catalan numbers as a function of the Taylor series of $e^{-x}$ i.e. $e^{-x}=1-x+\frac{x^2}{2}-\frac{x^3}{6}+\...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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.$
user avatar
1 vote
2 answers
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 ...
user avatar
  • 2,098
0 votes
0 answers
32 views

Proof $\sum_{k=0}^n \frac{1}{k+1}\binom{2k}k \binom{2n-2k}{n-k}=\binom{2n+1}n$ With Catalan Numbers [duplicate]

I need to prove that $\sum_{k=0}^n \frac{1}{k+1}\binom{2k}k \binom{2n-2k}{n-k}=\binom{2n+1}n$ with catalan-numbers. $\sum_{k=0}^n \frac{1}{k+1}\binom{2k}k \binom{2n-2k}{n-k} = \sum_{k=0}^n C_k\cdot C_{...
user avatar
  • 31
0 votes
0 answers
57 views

Number of pair of paths of length $n + 1$ starting at $(0, 0)$, ending at the same point, having no common points and going only up and to the right

I am interested in finding a reccurence relation between the number of pairs of paths which: \begin{align} & \text{1) Both starting and $(0, 0)$ and have length $n$} \\ & \text{2) Have no ...
user avatar
2 votes
1 answer
61 views

Correlation between number of paths and Catalan numbers.

I was recently introduced to the set of Catalan numbers, which are of the form $\prod_{i = 2}^n \frac{n + i}{n}$. The first few Catalan numbers (which I might as well mention are all integers) are: 1, ...
user avatar
0 votes
1 answer
125 views

Lattice paths that don't touch the diagonal

Consider a coordinate system. Suppose we want to calculate the number of lattice paths from (0,0) to (P,Q); P>Q such that none of those lattice paths ever touch the line y=x, which indirectly tells ...
user avatar
0 votes
0 answers
63 views

Diagonal Lattice path

So, considering a coordinate system. Suppose we want to calculate the number of lattice paths from (0,0) to (P,Q); P>Q such that none of those lattice paths ever touch the line y=x, which ...
user avatar
4 votes
0 answers
94 views

Find bound for polynomial with binomial coefficients

I need to find a good, computable upper bound for the expression $$\sum_{k=0}^m x^k \binom{n+k}{k}$$ as a function of $x$, $n$ and $m$, and where $0<x< 1/2$ is real, and $0<n\leq m$ are ...
user avatar
5 votes
1 answer
146 views

Integrality of a modified Catalan recurrence relation

How can it be proved that the sequence $(a_{n})_{n\geq0}$ satisfying the recurrence $$(n+1)a_{n} - r(r-1)(r(n-1)+1)a_{n-1}=0\quad a_{0}=1 \quad r \geq 2 \in \mathbb{N}$$ is always a sequence of ...
user avatar
1 vote
1 answer
149 views

Is this a valid bijection from this set of permutations to the set of bracket nestings of order $n$?

I'm trying to prove that the set of permutations of $[n]$ which do not contain a decreasing subsequence of order $\geq 3$ is equal to the $n^{th}$ Catalan Number. One of the many things that the ...
user avatar
0 votes
1 answer
52 views

How do I arrive at the integral representation of Catalan Numbers using Mellin Transform

I have been trying to understand how to obtain the integral representation of the Catalan numbers using Mellin transformations and get stuck when I obtain the inverse Mellin transformation.
user avatar
  • 11
2 votes
1 answer
74 views

Unlabelled trees and Catalan numbers

Show that the number of unlabelled trees with $n$ vertices is at the most $(n-1)^{\text{th}}$ Catalan number. I tried to find a surjection but it does not seem to be the right way.
user avatar
  • 996
1 vote
0 answers
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?
user avatar
  • 11
4 votes
0 answers
93 views

Reference request for an identity involving Catalan numbers

I am wondering if a bijective proof of the following identity involving Catalan generating functions has appeared anywhere in the literature. (It's not difficult to simply verify it for the functions ...
user avatar

1
2 3 4 5
9