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

learn more… | top users | synonyms

0
votes
2answers
31 views

Trouble deriving the Catalan numbers (near the last step)

The final result should be $C(n) = \frac{1}{n+1}\binom{2n}{n}$, for reference. I've worked my way down to this expression in my derivation: $$C(n) = \frac{(1)(3)(5)(7)...(2n-1)}{(n+1)!} 2^n$$ And I ...
2
votes
1answer
49 views

How to formally use Taylor expansions for $n$th derivatives and generating functions?

When deriving Catalan numbers, the generating function takes on this form: $$C(x) = \frac{1}{2} (1 - \sqrt{1-4x}) = \frac{1}{2} (1 - f(x))$$ where $f(x) = \sqrt{1-4x}$ How does one formally show ...
3
votes
2answers
72 views

Rewriting product to a binomial

I'm currently researching Wigner matrices. I wanted to calculate the moments of its spectral density. The probability density is $$\frac{1}{2\pi} \sqrt{4-x^2} \text{ for } x \in [-2,2] $$ I have ...
2
votes
0answers
65 views

Identity involving the Catalan numbers and binomial coefficients

Let $C_k := \frac{1}{k + 1} \binom{2k}{k}$ be the $k$-th Catalan number and let $K$ be a positive integer. I am looking for an identity or simplification of \begin{equation} \sum_{k = 0}^K C_k \...
2
votes
0answers
30 views

How many triangulations are at least possible for a set of points in 2d?

I'm a little confused, because I thought, there would be C(n-2) triangulations, where C(n) is the n-th catalan number and n the amount of points in the set. But it turns out, that there seems to be ...
1
vote
1answer
29 views

Catalan Sequence on a Circle

A Catalan sequence of length $2n$ is a sequence of $1$'s and $0$'s such that no initial segment of the sequence has more $0$'s than $1$'s. The number of such sequences is given by the Catalan number ...
10
votes
2answers
325 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
40 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
33 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
31 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 ...
3
votes
1answer
21 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
108 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
39 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
59 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 ...
2
votes
0answers
29 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 = -1$...
6
votes
2answers
128 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}- \frac{\ln2}{2}\...
1
vote
1answer
44 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
81 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
49 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
44 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
42 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
87 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
80 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
67 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
55 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
48 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
46 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
53 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
38 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
60 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
126 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 ...
5
votes
3answers
233 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 $$ \sum_{s=k}^{m}...
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} = \frac{(2n)!...
1
vote
2answers
52 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
64 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
49 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
98 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
492 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
83 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^+$: $$S_n=\frac{2\cdot18^n}{...
1
vote
1answer
65 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
56 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
70 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
67 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
70 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 ...