Tagged Questions

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

32 views

Number of ways to pair off $2n$ points such that no chords intersect

For $n \geq 0$ evenly distribute $2n$ points on the circumference of a circle, and label these point cyclically with the numbers $1, 2 . . . , 2n$ Let $h_n$ be the number of ways in which these $2n$ ...
55 views

A series related to Catalan numbers

Recall the definition of Catalan numbers: $$C_n=\frac1{n+1}\binom{2n}n=\frac{2^n(2n-1)!!}{(n+1)!}.\tag1$$ Now consider the following series with a parameter $n\in\mathbb N^+$: ...
30 views

Recurrence relation of Catalan Numbers.

Form a recurrence relation for catalan numbers, which is the number of ways to paranthesis a product of n+1 matrices. I know the proof for this using Dyck Paths as a defintion of Catalan Numbers. I ...
39 views

Number of pathsin a grid with restrictions

Please help, I am stuck with this example. Prove that the Catalan number $C_n$ equals the number of lattice paths from $(0,0)$ to $(2n, 0)$ using only upsteps $(1, 1)$ and downsteps $(1, -1)$ that ...
37 views

Let ${a_n}$ be a sequence of real numbers. The backwards differences of this sequence are defined recursively:

Let ${a_n}$ be a sequence of real numbers. The backwards differences of this sequence are defined recursively: The first difference $∇a_n$ is an new sequence defined by:$∇a_{n} = a_{n} - a_{n-1}$ ...
54 views

Prove the following two statements about the Catalan numbers $C_n$

Prove the following two statements about the Catalan numbers $C_n$, $$C_n \ge 2^{n-1}$$ and $$C_n \ge \frac{4^{n-1}}{n^2}$$ for all all positive integers $n\ge1$. Which result is more precise. ...
42 views

321-avoiding permutations and RSK

I am reading through a book on enumeration and I came across a weird statement: Using RSK (Robinson-Schensted-Knuth Correspondence), one can show that 321-avoiding permutations are Catalan objects. ...
61 views

Prove that ${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$

(a) Prove that $${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$$ (b) Let {$a_n$} be a sequence with the property that ${\sum _{k=0}^n}a_ka_{n-k}= 1$. Calculate the generating function of ...
44 views

Derive Euler's formula for the Catalan numbers

Derive Euler's formula for the Catalan numbers, $$C_n = \frac{2\times 6\times 10\times \cdots \times (4n - 2)}{(n + 1)!}$$ and note that (n+1)Cn = (4n - 2)Cn-1 I'm not sure at all where to go with ...
17 views

Consider the problem of stacking coins in the plane. Prove that the number of coin configurations satisfies the Catalan recurrence [duplicate]

Consider the problem of stacking coins in the plane such that the bottom row consists of $n$ consecutive coins. Prove that the number of coin configurations satisfies the Catalan recurrence. I ...
81 views

Finding the number of lattice paths

Find the number of lattice path of length $2n$ that starts on $(0, 0)$ such that for all the points $(x, y)$ in the path, $x < y$. So pretty much all the points besides the origin are strictly ...
56 views

93 views

Prove $2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31>3^{16}$

I recently came across the following problem: If $C_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th catalan number, then prove that for all $n\ge 17$: $$C_n>3^n$$ How the induction step works is ...
40 views

97 views

Why 312 Avoiding?

I have recently had the chance to attend a nice talk in Combinatorics, and once the speaker alluded to the famous 312-avoiding pattern problem, I was reminded of the following question I have had ...
199 views

Hard binomial sum [closed]

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!
41 views

Prove that a sequence can be enumerated using Catalan numbers

This problem is taken from R.P. Stanley’s Enumerative Combinatorics. Give bijective arguments to show that sequences of $n$ $1$'s and $n$ $-1$'s in which the sum of the first $i$ terms is ...
50 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)))))) = ...
46 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 ...
109 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 ...
113 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 ...
217 views

42 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 ...
172 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 ...
132 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) ...