Articles of catalan numbers

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 […]

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 number with up and down instead of up and right but I just don’t get why is […]

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 arrangement with n = 3 could be: $\pmatrix{1 3 4\\ 256}$ I think it would be easiest to […]

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 $H_n=\sum_{k=1}^{n}\frac{1}{k}$. The left side is equal to $$2\log(C(x))=2\log\left(\frac{2}{1+\sqrt{1-4x}}\right)$$ where $C(x)=\sum_{n=0}^{\infty}C_n x^n$ is the generating function of the Catalan numbers.