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

learn more… | top users | synonyms

0
votes
1answer
32 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
66 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
30 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
84 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
35 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$ ...
4
votes
2answers
191 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
306 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
76 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
166 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
32 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
42 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
28 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
47 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
58 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 ...
1
vote
0answers
157 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
46 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
47 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
52 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
37 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 ...
1
vote
1answer
38 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
124 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
86 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
32 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
2answers
268 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 ...
8
votes
1answer
83 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
179 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
91 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
63 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
331 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
63 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
46 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
99 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
114 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
120 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
67 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
249 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
116 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)\\ ...
3
votes
1answer
130 views

Recurrence $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ for non-crossing matchings

The number of non-crossing matchings of sides of $2n$-gon (i.e. the number of ways to connect sides pairwise by non-intersecting paths) is $n$’th Catalan number, $\text{Cat}_n$. How to prove ...
1
vote
1answer
314 views

Catalan Numbers: lattice paths with n+1 steps

I had this questions that I was having trouble with: Show that $C_n$ counts the number of (unordered) pairs of lattice paths with n+1 steps each subject to the conditions: i)starting at ...
1
vote
1answer
203 views

Catalan numbers - number of ways to stack coins

How many ways are there to stack coins on top of the other (2D stack) without any coin falling down ? Here's an example for $n=3$: Now this is most likely just like the monotonic path of Catalan ...
1
vote
2answers
114 views

Catalan number basic question - combinatorics

I have a question regarding catalan numbers: 1) Find the number of sequences $a_1 \leq ... \leq a_n$ where $a_i \in \mathbb N$ and $0 \leq a_i \leq i-1$ for all $i \in \{1,2,...,n\}$ For example: ...
1
vote
1answer
142 views

A self-convolution formula that counts bracket expressions

Problem: Consider an alphabet of size $m+2$, consisting of the two bracket symbols $\ [ \ ] \ $ plus $m$ non-bracket symbols ($m \ge 0$). Define $f_m(n)$ to be the number of length-$n$ strings on this ...
3
votes
1answer
777 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
1
vote
0answers
72 views

number of ways to arrange

There are N 1s and N 0s We have to arrange them in a row such that at no position in this row the number of 0s from the beginning exceed the number of 1s from the beginning. Also the number of ...
3
votes
2answers
237 views

Dyck paths with $k$ peaks

There are $n$ $1$'s and $n$ $0$'s. We have to arrange them in a row such that at no position in this row the number of $0$'s from the beginning exceed the number of $1$'s from the beginning. Also the ...
1
vote
2answers
103 views

Circular orientation of $n$ identical red balls and $n + 1$ identical black balls

I encountered a question as follows: In how many ways may $n$ identical red balls and $n + 1$ identical black balls be arranged in a circle (This number is called a Catalan number)? While trying to ...