Articles of catalan numbers

Number of positive integer walks from 0 to b.

It is well known that the number of walks of length $m=2k+1$ starting at $0$ and ending at $0$ of step size $\pm 1$ and always nonnegative is the number of Dyck paths from $(0,0)$ to $(k,k)$ i.e. the $k^{th}$ Catalan number $C_k$. The following seems like it should be well known but I have […]

Number of Dyck Paths Bounded by $M$

A Dyck path of length $2k$ is a sequence $\{s_j\}_{j=1}^{2k}$ of non-negative integers such that $|s_{j+1} – s_j| = 1$ for all $j = 1,…,2k$ and $s_0 = s_{2k} = 0$. The number of Dyck paths of length $2k$ is given by the nice formula $$C_k = \frac{1}{k+1}\begin{pmatrix} 2k\\k\end{pmatrix}.$$ ($C_k$ is the $k$-th Catalan number.) […]

Finding the number of monotonic paths not crossing the diagonal

For great diagrams relating to the Catalan number and the number of monotonic paths not crossing the diagonal, see this: So why is the number of monotonic paths not crossing the diagonal the Catalan number? I understand that through the “reflection method”, we arrive at $2n \choose n$ – $2n \choose n-1$ which is […]

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 $2n$?

Catalan's constant and $\int_{0}^{2 \pi} \int_{0}^{2 \pi} \ln(\cos^{2} \theta + \cos^{2} \phi) ~d \theta~ d \phi$

According to my book (The Nature of computation, page 691): $$\int_{0}^{2 \pi} \int_{0}^{2 \pi} \ln(\cos^{2} \theta + \cos^{2} \phi) ~d \theta ~d \phi= 16 \pi^2 \left(\frac{C}{\pi}- \frac{\ln2}{2}\right),$$ where $C$ is Catalan’s constant. I have tried to derive this expression by looking at integral representations of $C$, but I have not been able to perform the […]

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$ I don’t know how to explain the bijection between this and the plane binary tree with $2n+1$ […]

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 there

Hard binomial sum

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!

Catalan number – combinatoric

Alice and bob are playing cards. for each round of the game, player can win 1 card if he or she won the round, otherwise, he or she loses $1$. It’s a $30$ rounds game, and player can hold negative amount of cards which he or she owes to the other player. the game result […]

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 dolla bill the cashier has and down lines for each one he gave as change.. attempting to […]