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

learn more… | top users | synonyms

2
votes
0answers
19 views

Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where $$ D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( ...
2
votes
0answers
38 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
27 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
30 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 ...
0
votes
1answer
37 views

Binomial theorem, verify ${\frac12 \choose n+1} = 1/(n+1){n-\frac12 \choose n}(-1)^n(1/2)$ [closed]

I need to verify ${\frac12 \choose n+1} = 1/(n+1){n-1/2 \choose n}(-1)^n(1/2)$ and then verify $${2n \choose n}(1/(2^{2n}))={n-1/2 \choose n}$$ Please help!
3
votes
2answers
71 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
39 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 ...
0
votes
1answer
93 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
38 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$ ...
7
votes
3answers
229 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
326 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
78 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
172 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
33 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
44 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)))))) = ...
-1
votes
1answer
31 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
52 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
66 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
3answers
108 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
158 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
50 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
55 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
54 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
44 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
73 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
39 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
132 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
89 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
34 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
105 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
109 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
104 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
295 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
36 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 ...
10
votes
2answers
464 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)} ...
8
votes
1answer
87 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
191 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
93 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
65 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. ...
9
votes
3answers
349 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
139 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
68 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
48 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
90 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
101 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). ...
0
votes
1answer
138 views

Ways to color an octagon's vertices with three colors?

In how many ways can we color the 8 vertices of an octagon each red, green, or blue, so that no two adjacent vertices are the same color? I think there should be something to do with Catalan numbers ...
3
votes
1answer
133 views

How many arrangements of the digits 1,2,3, … ,9 have this property?

How many arrangements of the digits 1,2,3, ... ,9 have the property that every digit (except the first) is no more than 3 greater than the previous digit? (For example, the arrangement 214369578 has ...
2
votes
2answers
69 views

Catalan numbers, Condition that $\sum_{k=1}^n c_k=1 \mod 3$ using Lucas theorem

Catalan numbers are $c_n=\frac{1}{n+1}{\binom {2n}{n}}$. Prove that $\sum_{k=1}^n c_k\equiv 1 \mod 3 \iff$ The digit $2$ appears in the ternary representation of $n+1$. I was shown the solution ...
3
votes
1answer
265 views

Catalan Numbers Staircase bijection

I need to give a bijective proof for the following problem (via R. Stanley Catalan Addendum). ($k^8$) tilings of the staircase shape $(n, n − 1, \dots , 1)$ with $n$ rectangles. For example, when $n ...
3
votes
1answer
118 views

Finding relatives of the series $\varphi =\frac{3}{2}+\sum_{k=0}^{\infty}(-1)^{k}\frac{(2k)!}{(k+1)!k!2^{4k+3}}$.

Consider $\varphi=\frac{1+\sqrt{5}}{2}$, the golden ratio. Bellow are series $(3)$ and $(6)$ that represent $\varphi$ $$ \begin{align*} \varphi &=\frac{1}{1}+\sum_{k=0}^{\infty}\cdots&(1)\\ ...