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

learn more… | top users | synonyms

3
votes
0answers
59 views

A recursion formula related to *Catalan numbers*

When I was working on a problem related to Catalan Number, I deduced the following recursion formula: \begin{equation} a_{l,r}=a_{l-1,r}+a_{l-1,r-1}+a_{l-1,r-2}+\ldots+a_{l-1,l-1},\\ where \quad r \ge ...
4
votes
1answer
57 views

In how many ways we can move from $(0,0)$ to $(10,10)$ without crossing the line where y=x.

Suppose you are in $(0,0)$ you have to go to $(10,10)$ without crossing the line where y = x. You can only move upwards or rightwards. I have noticed that it is only asking the $10th$ Catalan number. ...
3
votes
3answers
48 views

Finding the number of sequences with $0 \leq a_m \leq 3m$

Problem: Let $\alpha, \beta$ be non-negative numbers. Suppose the number of strictly increasing sequences $a_0, a_1, a_2 \cdots a_{2014}$ satisfying $0 \leq 3m$ is $2^{\alpha}(2\beta+1)$. Find ...
0
votes
1answer
36 views

A formal proof of how the following equation computes the nth catalan number?

$t(0)=1$ $t(n+1)=\sum_{i=0}^n t(i)*t(n-i)$ $ ,n>=0$ nth Catalan number is given by :- $t(n)=2nCn/(n+1) $ I tried breaking the latter formula into a Summation of pairs, but it did not work. My ...
2
votes
1answer
38 views

Catalan numbers derivation (quadratic part)

When deriving the Catalan numbers using generating functions, eventually you reach the step: $C(x) = 1 + xC(x)^2$ which means $xC(x)^2 - C(x) + 1 = 0$ Which, through the quadratic formula, means ...
3
votes
1answer
32 views

Derivation of Catalan numbers

Trying to go through the proof. Let $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ with $C_0 = 1$. $$ G(x) = \sum_{n=0}^{\infty} C_n x^n \\ G(x) = \sum_{n=0}^{\infty} (\sum_{k=0}^{n-1} C_k C_{n-1-k}) x^n \\ ...
0
votes
1answer
13 views

Trouble understanding noncrossing partitions

I am trying to understand what a non-crossing partition means. I was reading a paper and it states A partition is noncrossing if there do not exist four distinct elements $$a < b < c < d$$ ...
0
votes
1answer
43 views

Catalan Numbers vs Bell Numbers

I did a lot of research on Catalan Numbers and I came across one interesting fact that the nth Catalan numbers never exceeds the nth Bell number. I know that the nth bell numbers counts the number of ...
0
votes
1answer
33 views

Catalan Number for unequal $m$ and $n$

The Catalan numbers can be interpreted as the number of paths on an $n\times n$ grid that are never above the diagonal. I am trying to figure out the generalization where the paths are on an $n\times ...
2
votes
1answer
31 views

Number of Dyck Paths Bounded by $M$

A Dyck path of length $2k$ is a sequence $\{s_j\}_{j=1}^{2k}$ of non-negative integers such that $|s_{j+1} - s_j| = 1$ for all $j = 1,...,2k$ and $s_0 = s_{2k} = 0$. The number of Dyck paths of length ...
0
votes
1answer
44 views

Catalan Numbers: Number of Lattice Paths from $(0,0)$ to $(a,b)$, $a>b$

The question is to find number of lattice paths from $(0,0)$ to $(a,b)$, $a>b$, such that for any point $(x,y)$ along the path, we have that $x\geqslant y$ Ive been trying to find some way to ...
3
votes
1answer
118 views

Number of Dyck paths with maximal odd sequence of $(1,-1)$ ending on the $x$-axis

A Dyck path from $(0,0)$ to $(2n+2,0)$ is a lattice path with steps $(1,1)$ and $(1,-1)$, never falling below the $x$-axis. Find the number of Dyck paths from $(0,0)$ to $(2n+2,0)$ such that ...
3
votes
3answers
209 views

How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?

Question: How to prove the following identity? $$ \sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m. $$ I'm also looking for the generalization of this identity like $$ ...
3
votes
0answers
41 views

Proving that the Catalan numbers are integers . [duplicate]

So the nth catalan numbers is given by $$C_n = \frac{1}{n+1} {2n \choose n}$$ I want to prove now that $n+1$ divides ${2n \choose n}$ so I try to do it the following way $${2n \choose n} = ...
1
vote
2answers
43 views

Catalan numbers generating function

I know that the generating function for the Catalan numbers sequence$$1 + 2x + 5x^2 + 14x^3 + ....$$ is $$C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$ But I want to know why do choose $$C(x) = \frac{1 - ...
1
vote
1answer
42 views

Finding the generating function for the Catalan number sequence

I know that generating function for the Catalan number sequence is $$f(x) = \frac{1 -\sqrt{4x}}{2x}$$ but I wan to prove it. So the sequence for the Catalan numbers is $$1,1,2,5,14....$$ as we all ...
0
votes
0answers
25 views

Groups and Catalan Numbers

I was reading a book about Catalan Numbers (Thomas Koshy Catalan numbers with applications) And I was reading through that example. Find the number of n-element multisets $\{a_1 ,a _2 , . . . , ...
1
vote
1answer
46 views

Is there a unique definition of Catalan numbers?

So I am studying Catalan numbers, and I see there is no one single definition of Catalan numbers . However, I was wondering how can you explain the Catalan number formula combinatorically ? so the ...
1
vote
1answer
90 views

Confused about Catalan number equation

Why is the Catalan number $$C_{n+1} = C_0 C_n+C_1C_{n-1}+\cdots+C_{n-1}C_1+C_nC_0,$$ and not $$C_{n+1} = C_0C_{n+1} + C_1C_n +\cdots+ C_nC_1 + C_{n+1}C_0 ?$$ In the latter formula, $0+(n+1) = 1+n = ...
2
votes
1answer
56 views

Number of ways to pair off $2n$ points such that no chords intersect

For $n \geq 0$ evenly distribute $2n$ points on the circumference of a circle, and label these point cyclically with the numbers $1, 2 . . . , 2n$ Let $h_n$ be the number of ways in which these $2n$ ...
6
votes
1answer
70 views

A series related to Catalan numbers

Recall the definition of Catalan numbers: $$C_n=\frac1{n+1}\binom{2n}n=\frac{2^n(2n-1)!!}{(n+1)!}.\tag1$$ Now consider the following series with a parameter $n\in\mathbb N^+$: ...
1
vote
1answer
46 views

Recurrence relation of Catalan Numbers.

Form a recurrence relation for catalan numbers, which is the number of ways to paranthesis a product of n+1 matrices. I know the proof for this using Dyck Paths as a defintion of Catalan Numbers. I ...
2
votes
2answers
43 views

Number of pathsin a grid with restrictions

Please help, I am stuck with this example. Prove that the Catalan number $C_n$ equals the number of lattice paths from $(0,0)$ to $(2n, 0)$ using only upsteps $(1, 1)$ and downsteps $(1, -1)$ that ...
1
vote
2answers
54 views

Let ${a_n}$ be a sequence of real numbers. The backwards differences of this sequence are defined recursively:

Let ${a_n}$ be a sequence of real numbers. The backwards differences of this sequence are defined recursively: The first difference $∇a_n$ is an new sequence defined by:$∇a_{n} = a_{n} - a_{n-1} $ ...
1
vote
1answer
58 views

Prove the following two statements about the Catalan numbers $C_n$

Prove the following two statements about the Catalan numbers $C_n$, $$ C_n \ge 2^{n-1} $$ and $$ C_n \ge \frac{4^{n-1}}{n^2} $$ for all all positive integers $n\ge1$. Which result is more precise. ...
2
votes
1answer
45 views

321-avoiding permutations and RSK

I am reading through a book on enumeration and I came across a weird statement: Using RSK (Robinson-Schensted-Knuth Correspondence), one can show that 321-avoiding permutations are Catalan objects. ...
1
vote
1answer
61 views

Prove that ${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$

(a) Prove that $${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$$ (b) Let {$a_n$} be a sequence with the property that ${\sum _{k=0}^n}a_ka_{n-k}= 1$. Calculate the generating function of ...
0
votes
1answer
48 views

Derive Euler's formula for the Catalan numbers

Derive Euler's formula for the Catalan numbers, $$ C_n = \frac{2\times 6\times 10\times \cdots \times (4n - 2)}{(n + 1)!} $$ and note that (n+1)Cn = (4n - 2)Cn-1 I'm not sure at all where to go with ...
0
votes
0answers
18 views

Consider the problem of stacking coins in the plane. Prove that the number of coin configurations satisfies the Catalan recurrence [duplicate]

Consider the problem of stacking coins in the plane such that the bottom row consists of $n$ consecutive coins. Prove that the number of coin configurations satisfies the Catalan recurrence. I ...
3
votes
1answer
167 views

Finding the number of lattice paths

Find the number of lattice path of length $2n$ that starts on $(0, 0)$ such that for all the points $(x, y)$ in the path, $x < y$. So pretty much all the points besides the origin are strictly ...
1
vote
1answer
59 views

Binomial transform of Catalan numbers formula

How to prove that OEIS A007317 Binomial transform of Catalan numbers $a_{n}: 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, .. (n = 1, 2, ..)$ has a recurrence formula: $(n+2)a_{n+2} = (6n+4)a_{n+1} - ...
6
votes
1answer
65 views

$\frac{2n\choose n}{n+2}\not\in\mathbb N$ and $n\neq3k+1$ and $n\neq4k+2$

Are there any natural numbers $n\not\equiv1\bmod3$, and $n\not\equiv2\bmod4$, so that $~\dfrac{\displaystyle{2n\choose n}}{n+2}\not\in\mathbb N$ ? Since $C_n=\dfrac{\displaystyle{2n\choose ...
2
votes
3answers
98 views

Prove $ 2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31>3^{16} $

I recently came across the following problem: If $C_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th catalan number, then prove that for all $n\ge 17$: $$ C_n>3^n $$ How the induction step works is ...
2
votes
1answer
53 views

The sum of infinite convergent series where every term is a geometric series term multiplied with reciprocal of square root of n

I´ve got the following infinite sum which - determined by the ratio test - is convergent for $\{p\in\mathbb{R}\ |\ p>1\}$ $$\left(\frac{1}{2\sqrt{\pi}}\right)\cdot\sum\limits_{n=1}^\infty ...
1
vote
1answer
49 views

How is Schroeder's generalized parentheses sequence (A001003) actually used to generated parentheses expressions?

The sequence A001003 counts the "number of ways to insert parentheses in a string of n+1 symbols". What I'm trying to figure out is how to generate the expressions with parentheses (in code). For ...
0
votes
1answer
31 views

Isomorphic relation between Catalan representations

There is an unanswered question at MathOverflow: Intersecting Family of Triangulations This article at Wikipedia explains the concept of non-intersecting partitions of a polygon: Catalan number So ...
5
votes
5answers
182 views

What is the probability of winning a best of $1, 3, 5, \cdots$ to infinity?

A shady casino organizes a simple game with rules that follow: 1 die is rolled. If it lands on an even, the house wins. If it lands on an odd, the player wins. However, if the player loses he may ...
0
votes
1answer
47 views

Solving recurrence similar to Catalan number recurrence

Today i was solving a dynamic programming problem that is matrix chain multiplication and i come up with a recurrence, i tried for n=4 but :(. How can I solve this recurrence? It is similar to the ...
3
votes
0answers
78 views

Is there an advantage in using continued fractions for Catalan or Fibonacci-Lucas primality tests?

I am studying the basic theory about continued fractions and also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci ...
15
votes
3answers
276 views

Prove a combinatorial identity

Prove the combinatorial identity $$ \sum_{n_1+\ldots+n_m=n} \;\; \prod_{i=1}^m \frac{1}{n_i}\binom{2n_i}{n_i-1}=\frac{m}{n}\binom{2n}{n-m}, \enspace n_i>0,i=1,\ldots,m $$ I "discovered" this ...
3
votes
0answers
101 views

Is it 3-D Catalan numbers?

I am studying Catalan numbers recently but I think that how about 3-D Catalan? So that I imagine following situation ; A man travel through the path-way parallel to $ x, y, z $ axis from O ...
2
votes
0answers
68 views

A Mellin Transform of a generating function

I am trying to find the Mellin transform of the function $$ G(z) = \sum_{k \ge 1} C_k\left( 1- \exp \left( \frac{-z}{4^k} \right )\right), $$ where $C_k$ denotes the $k$-th Catalan number ($C_k = ...
1
vote
0answers
34 views

What is the asymptotic value of MAX $(a+b)!(c+d)!b/(a!b!c!d!(b+d))$ if $a+b+c+d=n$?

What is the asymptotic value of $$\max\ \frac{(a+b)!(c+d)!b}{a!b!c!d!(b+d)}, \quad \textrm{if}\ \ a+b+c+d=n?$$ Is it $\approx 2^n/n$? Is it related to the asymptotic value of the Catalan numbers?
2
votes
1answer
55 views

Permutation At A Railway Track

Engines numbered 1, 2, ..., n are on the line at the left, and it is desired to rearrange(permute) the cars as they leave on the right-hand track. An engine that is on the spur track can be left ...
4
votes
2answers
96 views

Counting sequences using Catalan Numbers

Count the number of sequences $a_{1},...,a_{2015}$ such that: $a_{i}\in \{-1,1\}$, and $\sum _{i=1} ^ {2015} a_{i}=7$, and $\sum _{i=1} ^{j} a_i >0$ for every $1\leq j\leq 2015$ I assume we have ...
0
votes
0answers
132 views

A binary plot of the Catalan numbers and the pseudo-Fibonacci series that can be found inside. Why do they appear?

I was trying to find in Internet a binary plot of the Catalan numbers, and I did not find anyone... so I did it by myself and here it is (about 2000 elements): There are not clear patterns inside ...
1
vote
1answer
123 views

How to derive Catalan Number equation? [closed]

I am looking for a way to derive the Catalan Number equation: $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ from: $$ C_0 = 1,\qquad C_{n+1}=\sum_{i=0}^{n} C_i\, C_{n-i}\,.$$
0
votes
0answers
47 views

Generalization of Catalan numbers

I am looking for some kind of function describing the number of non-crossing partitions similar to those described by the Catalan numbers. Let's say $C_3$ would be the third Catalan number. $C_3=5$ ...
8
votes
3answers
403 views

Identity with Harmonic and Catalan numbers

Can anyone help me with this. Prove that $$2\log \left(\sum_{n=0}^{\infty}\binom{2n}{n}\frac{x^n}{n+1}\right)=\sum_{n=1}^{\infty}\binom{2n}{n}\left(H_{2n-1}-H_n\right)\frac{x^n}{n}$$ Where ...
2
votes
1answer
439 views

How to deal with this double summation?

I'm stuck with the proof of this result: $$2^n = \sum_{t=-\frac{n-1}{2}}^{\frac{n-1}{2}} \binom{n+1}{\frac{n+1}{2} + t} \sum_{k=\vert t \vert}^{\frac{n-1}{2}} \binom{\frac{n-1}{2}+k}{k} ...