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

learn more… | top users | synonyms

7
votes
1answer
178 views

Closed form for $ S(m) = \sum_{n=1}^\infty \frac{2^n \cdot n^m}{\binom{2n}n} $ for integer $m$?

What is the (simple) closed form for $\large \displaystyle S(m) = \sum_{n=1}^\infty \dfrac{2^n \cdot n^m}{\binom{2n}n} $ for integer $m$? Notation: $ \dbinom{2n}n $ denotes the central binomial ...
1
vote
1answer
37 views

Finding a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$

I'm trying to come up with a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ where $C_n$ is the $n$th Catalan number. I know we can write $(n+2)C_{n+1} = 2(2n+1)C_n$. I also tried to follow ...
0
votes
1answer
30 views

Count Valid Parethensizations

Number of Valid Parenthesizations: Given an integer n, write a function f(n) that counts the number of valid sequences consisting of n parenthesis. Note that “)()(” and “))((” are not valid. ...
0
votes
0answers
21 views

Number of binary trees with n unlabeled node

I found a proof about the number in this site. In that site the author says that the number of all possible binary trees with n labeled nodes is equal to the number of ways one can make n-1 edges ...
2
votes
1answer
18 views

Understanding the proof of catalan numbers using lattice paths

I am trying to understand a proof to come up with the catalan numbers presented in the book "A course in combinatorics" by van Lint and Wilson. The authors say that by reflecting the part of the path ...
0
votes
2answers
101 views

Catalan numbers and triangulation

Assume $C_n$ is the number of triangulations of a polygon with $n+2$ sides. Using a combinatorial proof, show that $(4n+2)C_n=(n+2)C_{n+1}$. I don't even know where to start with this one. I ...
0
votes
1answer
35 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
2
votes
2answers
55 views

Catalan numbers formula derivation

I'm trying to follow a proof of the Catalan numbers being equal to $\frac{1}{n+1} {2n \choose n}$ from the recurrence relation $C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_{1}+C_{n-1}C_0$ Now it's seen ...
1
vote
0answers
23 views

Catalan Number Modulo Prime

What is the fastest method to find the $n$th Catalan number modulo some prime $p$? I was looking at Lucas's method to solve $\binom{2n}{n}$ fast, but not sure if it will work. What is the fastest way ...
0
votes
0answers
24 views

Proof that the number of Dyck Paths that go below the horizon exactly once is Catalan number [duplicate]

Let's say we have a path from $(0,0)$ to $(2n,0)$, that is a special kind of the $Dyck$ $Path$: it steps down to $(k,-1)$ once, or equally said, one line $(1,-1)$ that steps downwards, touches $y = ...
6
votes
2answers
121 views

Catalan's constant and $\int_{0}^{2 \pi} \int_{0}^{2 \pi} \ln(\cos^{2} \theta + \cos^{2} \phi) ~d \theta~ d \phi$

According to my book (The Nature of computation, page 691): $$\int_{0}^{2 \pi} \int_{0}^{2 \pi} \ln(\cos^{2} \theta + \cos^{2} \phi) ~d \theta ~d \phi= 16 \pi^2 \left(\frac{C}{\pi}- ...
1
vote
1answer
41 views

Number of tourist paths

Please, would someone give me a hint to this exercise? Tourist path is refracted line from point (0,0) to (2n,0), created from 2n line segments, where every line segment is determined by vector (1,1) ...
0
votes
1answer
74 views

Bijection and catalan numbers

I am having trouble with bijection and catalan numbers. Here is a sample of a problem I am working with. Give a bijection to show that the following is counted by Catalan numbers. The number of ...
1
vote
1answer
47 views

Catalan number - combinatoric

Alice and bob are playing cards. for each round of the game, player can win 1 card if he or she won the round, otherwise, he or she loses $1$. It's a $30$ rounds game, and player can hold negative ...
1
vote
1answer
42 views

A Finite Combinatorial Sum

It can be proved by induction or telescoping sum that $$\sum_{i=0}^n {2i\choose i}\frac{1}{2^{2i}}=(2n+1){2n\choose n}\frac{1}{2^{2n}}.$$ However, without knowing the right hand side in advance, I ...
0
votes
1answer
41 views

Simplify Summation of combination [duplicate]

how can I simplify this to a phrase without a sigma?! $$ {1\over r+1}{2r \choose r} + \sum_{i=1}^r \left( {i+1\over r+1} {2r-i \choose r-i}{s+i-2 \choose i} \right) $$ thanks!
2
votes
2answers
80 views

Sum of all Products on Catalan numbers

how can I simplify this? let: $$ C_n = {{2n \choose n}\over n+1} $$ find: $$ \sum_{P_1 + P_2 + ... + P_k = r} \left(\prod_{j = 1}^k C_{P_j}\right) $$ thanks!
3
votes
0answers
78 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
66 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
54 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
44 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
45 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
43 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
16 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
51 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
40 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
35 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
57 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
124 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 ...
4
votes
3answers
223 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
42 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
49 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
60 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
29 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
48 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
96 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
222 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$ ...
7
votes
1answer
78 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
63 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
50 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
64 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
69 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
58 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
69 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
54 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
260 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
63 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
67 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 ...