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

learn more… | top users | synonyms

1
vote
1answer
23 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
48 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
30 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
95 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*} ...
1
vote
0answers
28 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
129 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
75 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
116 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
67 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
52 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
247 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
86 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
58 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
36 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
59 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 ...
1
vote
1answer
83 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
77 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
106 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
61 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
170 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
80 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
117 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
89 views

Is there a formula for this sequence?

The following Mathematica program: ...
1
vote
1answer
237 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
154 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
96 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
120 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
496 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
67 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
193 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
94 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
152 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
101 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
159 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
140 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
253 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
57 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
93 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
158 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
136 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
3answers
3k 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
255 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
102 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
180 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
151 views

Bijection for Catalan Number

How can I show that this maps to
8
votes
5answers
367 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
119 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
362 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
552 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 ...