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

learn more… | top users | synonyms

4
votes
2answers
45 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
44 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. ...
4
votes
2answers
165 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 ...
1
vote
1answer
79 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
50 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
34 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
41 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 n(1,-1) down ...
0
votes
0answers
31 views

Find the Catalan numbers numbers in [2n] so that each row and column is increasing

I am doing this homwwork question. The Catalan numbers Cn count the number of 2*n arrays containing the numbers in [2n] so that each row and column is increasing.Enumerate all such arrays for n = 4. ...
1
vote
1answer
75 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
43 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
70 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
60 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
152 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
0answers
76 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
113 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 ...
0
votes
0answers
79 views

Is there a formula for this sequence?

The following Mathematica program: ...
1
vote
1answer
181 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
126 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
74 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
106 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 ...
1
vote
1answer
223 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
62 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 ...
2
votes
2answers
170 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
87 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
125 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
96 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
0answers
68 views

Catalan Numbers and Powers of 2

I'm wondering if there are identities relating the Catalan numbers to powers of 2. For example, I've found that ...
0
votes
1answer
128 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
41 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
128 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
233 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
52 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
91 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
137 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
115 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?
7
votes
2answers
2k views

Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $ However ...
5
votes
1answer
227 views

Counting Balanced Brackets with a twist

I have $n$ "1"s written as a sum: $1+1+1+\dots+1$, and proceed to add some brackets to the sum. Call the modified sum "good" if the brackets are balanced and not redundant*. [Since in fact placing any ...
2
votes
1answer
97 views

Theta asymptotic for $\binom{2m}{m}$ [duplicate]

Show that $\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right)$ without using Stirling's approximation.
0
votes
2answers
165 views

How to show $\binom{2p}{p} \equiv 2\pmod p$?

how to prove $\forall p$ prime : $\binom{2p}{p} \equiv 2 \pmod p$ we have: $\binom{2p}{p} = \frac{2p (2p-1)(2p-3)...1}{p!p!}$ but how to continue?
0
votes
1answer
144 views

Bijection for Catalan Number

How can I show that this maps to
8
votes
5answers
364 views

Show that that $\lim_{n\to\infty}\sqrt[n]{\binom{2n}{n}} = 4$

I know that $$ \lim_{n\to\infty}{{2n}\choose{n}}^\frac{1}{n} = 4 $$ but I have no Idea how to show that; I think it has something to do with reducing ${n}!$ to $n^n$ in the limit, but don't know how ...
5
votes
2answers
110 views

An Intuitive Partition for the Catalan numbers

The nth Catalan number, $C(n)$ counts the number of binary strings with n $0$'s and n $1$'s such that any initial substring has at least as many $0$'s as $1$'s. I know that the formula for the nth ...
2
votes
2answers
300 views

Proof on Catalan numbers

In the book I'm using on Catalan numbers, the author gives a scenario in order to develop the formula for Catalan numbers. The scenario is that a boy has an empty jar. Every day he either puts in a ...
2
votes
2answers
480 views

Proof of Catalan numbers on a circle

Question: Letting 2n be the number of points on a circle, prove that the number of ways to join these points, with non-intersecting lines, into pairs is equal to the Catalan numbers. I'm having ...
5
votes
1answer
276 views

Evaluate $\sum_{n=1}^{\infty} \frac{(2n)!}{2^{2n}(n!)^2 (2n-1)}$

How to evaluate the series $$S = \sum_{n=1}^{\infty} \frac{1}{2^{2n}(2n-1)} \binom{2n}{n}$$ The original question was to show that for $$ a_n=\left(\frac{ 2n-3 }{ 2n }\right)a_{n-1} , a_1 = \frac 1 ...
1
vote
1answer
526 views

What are Catalan numbers?

I have read the Wikipedia article for Catalan number and a number of other websites, but still couldn't understand it. Please explain it in simple terms, or using some examples. Thanks in advance!
5
votes
3answers
369 views

$n$-ary trees with $k$-internal nodes - Catalan numbers

It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got ...
3
votes
2answers
401 views

Generalizing the Catalan Numbers

Preliminaries There are many equivalent definitions of the Catalan Numbers. I'll use this one: A Dyck Word is a string consisting on $n$ X's and $n$ Y's such that no initial segment of the string ...
1
vote
1answer
289 views

Given algorithm which prints $n$-th string of nested parentheses, find a reverse algorithm

We have the following balanced brackets permutations of length $4\cdot 2$ in lexicographical order: ...
4
votes
1answer
160 views

$N^\text{th}$ (in lexicographical order) term of balanced brackets string

We have the following balanced brackets permutations of length $4\cdot2$ in lexicographical order: ...