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

learn more… | top users | synonyms

1
vote
1answer
25 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
23 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
157 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
39 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
60 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
252 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
83 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
53 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
30 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
43 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 ...
3
votes
2answers
83 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
72 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
103 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
42 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
349 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 ...
3
votes
1answer
349 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} ...
2
votes
1answer
85 views

Why 312 Avoiding?

I have recently had the chance to attend a nice talk in Combinatorics, and once the speaker alluded to the famous 312-avoiding pattern problem, I was reminded of the following question I have had ...
3
votes
1answer
181 views

Hard binomial sum [closed]

How to prove this relation? $$\sum_{i=0}^{n}\frac{2^{-2i}\binom{2i}{i}}{n+i+2}=\frac{2^{4n+2}-\binom{2n+1}{n}^2}{(2n+3)2^{2n+1}\binom{2n+1}{n}}$$ That seems difficult!
0
votes
1answer
39 views

Prove that a sequence can be enumerated using Catalan numbers

This problem is taken from R.P. Stanley’s Enumerative Combinatorics. Give bijective arguments to show that sequences of $n$ $1$'s and $n$ $-1$'s in which the sum of the first $i$ terms is ...
1
vote
1answer
46 views

how do I parenthesize the product of abcdef??

This is about catalan number and parenthesizing. a)Determine the list of five 1's and five 0's that corresponds to each of these: (((ab)c)(d(ef))) = (what I did: 1110010110) (a(b(c(d(ef)))))) = ...
0
votes
1answer
37 views

Is bijection important in Catalan monotonic path counting?

Second proof computes Catalan number by removing bad paths (those which touch the forbidden diagonal) from all monotonic paths to compute the number of permitted paths. The proof seems to say that ...
3
votes
0answers
61 views

Number of Lattice Paths from $(0,0) to (n,n)$ without going over $y=x$

This is a question that was asked at the start of the section on Catalan Numbers in my book. I'm having trouble answering it. My Work All of the legal paths (ones which do not cross over $y=x$) must ...
3
votes
1answer
84 views

Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
4
votes
4answers
175 views

Generating series of Catalan numbers

The Catalan numbers may be defined as follows: $C_0=1$ and $$C_{n+1}=\sum_{k=0}^n C_k C_{n-k}\, .$$ One way to compute these numbers is to introduce the generating series $f(x)=\sum_{n\geq 0} C_n ...
1
vote
0answers
163 views

Sum concerning Catalan triangle and binomials

I am trying to prove the following relation. For $k \in \mathbb{N},k \geq 2$ and $i=1,\ldots,k-1$ \begin{equation} {2k-2-i \choose k-1-i}=\sum \limits_{l=0}^{k-1-i} 2^{2l} T(k-2-l,k-1-i-l)-2 \sum ...
1
vote
1answer
59 views

How to calculate variant of geometric series based on sequences of Catalan numbers?

I want to calculate $$\sum_{n=0}^{\infty}\frac{(2n)!}{n!(n+1)!}k^{n+1}C$$ where $0<k<1$ and $C$ and $k$ are some constants, and $0<C$. Is there any possible range of $0<C$ that allows ...
1
vote
2answers
70 views

8th positive odd integer that is an ODD Catalan number? [closed]

The $n^{\text{th}}$ Catalan number is given by the formula $C_n = \frac 1{n+1}\binom{2n}n$. It also satisfies the recurence \begin{align*}C_n &=\sum_{k=0}^{n-1}C_kC_{n-1-k}\\ &= ...
1
vote
1answer
56 views

Prove or disprove this lemma for Catalan Numbers

Prove or disprove that for all non-negative integers $n$ and $r$ with $r+1$ is less than or equal to $n$, $C(n,r+1)=C(n,r)\times\frac{n-r}{r+1}$.
1
vote
1answer
58 views

Proving Lower Bound on Catalan Numbers

I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ...
3
votes
1answer
75 views

Calculating Catalan numbers using Chebyshev's inequality

By using Chebyshev's inequality $P(|X - E[X]| \geq \varepsilon) \leq \operatorname{Var}(X)/ \varepsilon^2$ I want to calculate the following estimation for the Catalan numbers $C_n = \frac{1}{n+1} ...
1
vote
1answer
40 views

Does this sequence of integer products have a name?

Suppose that I have a product of, say, $n=4$ integers starting with one and ending with four $1234=4!=24$. Now I construct all products of four positive integers $1,2,3$ and $4$ with repetition such ...
1
vote
1answer
141 views

Cashier has no change… catalan numbers.. probability question

I think this question uses catalan numbers.. but I don't know exactly how to answer it... its not homework or anything but I need to understand how to do it.. I tried drawing up likes for each 5r ...
2
votes
1answer
103 views

Strong induction on a summation of recursive functions (Catalan numbers)

I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction: $$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$ Some cases: S(0) ...
1
vote
3answers
35 views

Why is $1 \times 3 \times 5 \times \cdots \times (2k-3) = \frac{(2k-2)!}{2^{(k-1)}(k-1)!}$

In order to find out the Catalan numbers from their generating function you have to evaluate the product above. Here is what I thought: \begin{align*} 1 \times 3 \times 5 \times...\times (2k-3) ...
2
votes
3answers
106 views

What is wrong with this calculation of $\binom{\frac{1}{2}}{k}$?

The reason I ask this question is that I want to show that: \begin{equation*} \binom{\frac{1}{2}}{k} = -2\frac{1}{k}\binom{2k-2}{k-1}\left(-\frac{1}{4} \right)^k \end{equation*} \begin{align*} ...
4
votes
0answers
111 views

Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc. I have a function ...
1
vote
1answer
110 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where $C_n$ denotes the number of ways of writing a valid list of open and closed parentheses of length ...
1
vote
2answers
362 views

Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence: $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ I tried ...
1
vote
0answers
39 views

Using singularity analysis to find the main asymptotic term of the Catalan Numbers

Using singularity analysis to find the main asymptotic term of the Catalan Numbers \begin{align} C_n = [z^n]\frac{1-\sqrt{1-4z}}{2z} \end{align} Can someone please explain to me the general concept ...
13
votes
2answers
542 views

Identity with Catalan numbers

How would you prove the following identity $$\sum_{1\ \leq\ j\ <\ j'\ \leq\ n}\ \prod_{k\ \neq\ j,\,j'}^{n} {\left(\, j + j'\,\right)^{2} \over \left(\, j - k\,\right)\left(\, j' - k\,\right)} ...
9
votes
1answer
97 views

Prove that $a_n$ is a perfect square if $n$ is even without generating functions or Taylor series.

Let $a_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$. For example, $a_5 = 6$, since there are six integers with the desired property: $41, 14, 311, ...
3
votes
1answer
244 views

Sum of Catalan numbers

What is $C_1 +C_2 + C_3 +... + C_n$, where each $C_i$ is Catalan number? I want to know if we can bound this sum by some function of $n$. I am looking for an upper bound. For sure it is less than ...
5
votes
2answers
101 views

Average number of Dyck words in a Dyck word

Given a integer $n$, how many Dyck words are a substring of a Dyck word of size $n$, on average? For example, if $n=2$, then Dyck words of size $2$ are : [ ] [ ] [ [ ] ] (1) contains two ...
2
votes
3answers
70 views

are there meaningful binary operations on the set of Catalan objects?

Is it possible to come up with some kind of meaningful closed binary operation $\star$ on sets $C_n$ of Catalan objects? By Catalan objects I mean objects that correspond to a given Catalan number. ...
11
votes
3answers
409 views

Harmonic Numbers series I

Can it be shown that \begin{align} \sum_{n=1}^{\infty} \binom{2n}{n} \ \frac{H_{n+1}}{n+1} \ \left(\frac{3}{16}\right)^{n} = \frac{5}{3} + \frac{8}{3} \ \ln 2 - \frac{8}{3} \ \ln 3 \end{align} where ...
2
votes
2answers
140 views

Verifying Touchard's Identity

$$C_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor}{n\choose 2k}\cdot C_k\cdot 2^{n-2k}$$ where $C_n$ are the Catalan numbers. I think we start by diving both sides by $2^n$, but unsure of where to go from ...
1
vote
1answer
70 views

Catalan numbers with both prefix and suffix

In one of the applications of Catalan number,it calculates the number of Dyck word in which a string consisting of n $X's$ and n $Y's$ such that no prefix of the string has more $Y's$ than $X's$, and ...
0
votes
1answer
54 views

Higher-Order Approximation of Catalan-Numbers

I have a question considering the higher-order approximations of the Catalan-Numbers, following the book Analytic Combinatorics by Flajolet and Sedgewick. First we set $$ C_n = \frac{1}{n+1} ...
1
vote
0answers
97 views

Proof of the Catalan number formula using Dyck walks

In our notes we were given the formula $$C(n)=\frac{1}{n+1}\binom{2n}{n}$$ It was proved by counting the number of paths above the line $y=0$ from $(0,0)$ to $(2n,0)$ using $n(1,1)$ up arrows and ...
1
vote
1answer
107 views

Combinatorics - Possibly catalan number question

How many sequences $a_1a_2...a_{2n}$ are there with the digits $\{-1,1\}$ such that $\forall j: \sum_{i=1}^{j}a_i \geq 0$ ? this is very similar to what we know of catalan numbers (or dyck words). ...