# Tagged Questions

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

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 ...
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 ...
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 ...
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 \sum_{k = 0}^K C_k \...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$...
128 views

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$$ ...