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

learn more… | top users | synonyms

1
vote
1answer
34 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
20 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
35 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
46 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
137 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
32 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
40 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
40 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
29 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
0answers
31 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
96 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
69 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*} ...
2
votes
0answers
40 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=c$. Therefore, $z_1=c^2+c$, $z_2=c^4+2c^3+c^2+c$, etc. I have a function $f(n,x)$ ...
1
vote
1answer
162 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
80 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
133 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 ...
4
votes
2answers
80 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
60 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
280 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
108 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
59 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
43 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
77 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
94 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
95 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
112 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
63 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
228 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
112 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
128 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
272 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
179 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
100 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
133 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 ...
2
votes
1answer
654 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
69 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
216 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
101 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 ...
2
votes
1answer
205 views

A variation on counting Balanced Brackets

While counting the number of balanced bracket expressions of length $2n$, the constraint is that for every prefix substring: $$\text{[number of occurrences of (]} - \text{[number of occurrences of )]} ...
1
vote
2answers
112 views

Counting votes, as long as one has more votes all the way through.

Two competitors won $n$ votes each. How many ways are there to count the $2n$ votes, in a way that one competitor is always ahead of the other? One competitor won $a$ votes, and the other won $b$ ...
0
votes
1answer
178 views

Problem with proving Catalan number

This is how my professor derived it: Taking the case of all valid arrangements of $n$ '(' and $n$ ')', he says that for every invalid arrangement, there will be a ')' at some $k^{th}$ position where ...
1
vote
1answer
44 views

A Catalan-like counting of walks of length $n$ on $\mathbb{Z}$

I would like to count the number of walks of length $n$ on $\mathbb{Z}$ starting at $0$, where in each step you move either one left or one right, such that you never land on a negative integer (i.e. ...
2
votes
1answer
147 views

Important numbers in Combinatorics

I recently went through some important numbers like the Stirling and Bell number for calculation of partitions /equivalence relations. I was wondering if someone can help me get a list of important ...
6
votes
1answer
268 views

What does the $q$-Catalan Numbers count?

I had completed a paper describing the $q$-Catalan numbers, which is the $q$-analog of the Catalan numbers. The $n$-th Catalan numbers can be represented by: $$C_n=\frac{1}{n+1}{2n \choose n}$$ and ...
1
vote
0answers
61 views

planar walks and catalan numbers

prove that following numbers are equal: (unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (0,1) or (1,0), ending at the same point and only intersecting at the ...
2
votes
1answer
97 views

Catalan's number with a twist

We all know that $$C_n = \frac{1}{n+1} {2n \choose n} $$ But what if I want to calculate the same property of catalan, but with number of zeros is $s$ and number of ones is $t$ when $s\neq t$? As ...
1
vote
2answers
166 views

Catalan number interpretation

I have a $2 \times n$ chessboard where numbers are increasing from left to right and top to bottom. I want to show that the number of arrangements is the $nth$ catalan number. for example one such ...
0
votes
1answer
151 views

Catalan numbers in programming

I've heard that Catalan numbers are nowadays used in many applications. But how are they really helpful in programming?