Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [catalan-numbers]

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

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).

The $n$th Catalan number is given directly in terms of binomial coefficients by $$ C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ for }n\ge 0. $$

497 questions
5
votes
1 answer

Upper bounds for a sequence of integers defined recursively

Given $\alpha\geq0$ we consider the sequence $$ C_k=k^\alpha\sum_{j=0}^{k-1}C_jC_{k-1-j} $$ with $C_0=1$. I'm interested in upper bounds (in terms of $\alpha$) for such a sequence. I know that when $\alpha=0$ the previous sequence reduces to the…
guacho
  • 1,414
4
votes
5 answers

Using the Catalan numbers

Here's a question we got for homework: A soccer match between team A and team B ends with a 9-9 tie. It is know that at some point of the game team A had the lead and that later on it was team B who had it. How many series's of 18 goals can…
yotamoo
  • 2,753
2
votes
1 answer

Recursion and Catalan Numbers

Consider the sequence defined by $$ \begin{cases} r_0=1\\ r_1=3\\ r_n=6r_{n-1}-9r_{n-2} & \text{if }n\ge 2 \end{cases} .$$ Find a closed form for $r_n$. Your response should be a formula in terms of $n$, and should not contain terms such as…
WolverineA03
  • 277
2
votes
1 answer

Number of binary trees with n unlabeled node

I found a proof about the number in this site. In that site the author says that the number of all possible binary trees with n labeled nodes is equal to the number of ways one can make n-1 edges from n nodes. Since each node can have 2 or less…
David Johns
  • 139
1
vote
1 answer

Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps

From Stanley's Catalan Numbers, problem 28: Left factors $L$ of Dyck paths such that $L$ has $n-1$ up steps. I don't understand what this means. If after a sequence of ups, there are equal number or fewer downs, then for $n=4$, I got $13$ paths, not…
Haoran Chen
  • 659
1
vote
1 answer

Number of specific functions $f:[2n]\to[2n]$ are Catalan Numbers

Let $$f:[2n]\to[2n]$$ $[2n]=\{1,...,2n\}$. Furthermore, $\\ f(x)\ne x, f(f(x))=x$ And $\forall xx$ follows $f(x)f(y)$ I have to proof that for the number of those functions we have $a_n=C_n$, where $C_n$ are the…
newbie
  • 647
1
vote
1 answer

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!
Vishnu Vivek
  • 1,441
1
vote
1 answer

Number of tourist paths

Please, would someone give me a hint to this exercise? Tourist path is refracted line from point (0,0) to (2n,0), created from 2n line segments, where every line segment is determined by vector (1,1) or (1,-1). Show that number of paths, which…
Mafi
  • 19
1
vote
0 answers

What is the asymptotic value of MAX $(a+b)!(c+d)!b/(a!b!c!d!(b+d))$ if $a+b+c+d=n$?

What is the asymptotic value of $$\max\ \frac{(a+b)!(c+d)!b}{a!b!c!d!(b+d)}, \quad \textrm{if}\ \ a+b+c+d=n?$$ Is it $\approx 2^n/n$? Is it related to the asymptotic value of the Catalan numbers?
baban
  • 11
0
votes
1 answer

Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal

I am in the process of understanding the Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal. RUU-RRRRUUU is one way where diagonal trespasses. Now, the complement is taken of the right…
Splendid Digital Solutions
  • 69
0
votes
1 answer

How to find the total number of ways one can reach (5,5) from (0,0)

The total number of ways one can reach $(5,5)$ from $(0,0)$ is $^{10}C_5$ as per a tutorial I am following. I know there are $5$ rights and $5$ ups. So there are 10 steps. But why it is choose $5.$
Splendid Digital Solutions
  • 69
0
votes
1 answer

catalan numbers - counting sequances with sum of 0

I need help in prooving that the cardinal number of the following set is $C_{n}$: The set of all sequences $a_{1}, a_{2}, .., a_{n} \in \mathbb{Z} \\ s.t \\ a_{1}+a_{2}+....+a_{n} = 0$ and for every $1 \leqslant i \leqslant n$ , $ a_{i}\geq -1$ and…
Mika Li
  • 13
0
votes
0 answers

Forbiden paths in Catalan numbers

I am trying to solve the next problem: Find all the possible combinations of roads that do not cross each other given a number of towns. First I started permuting all combinations with low numbers to figure it. The possibilities was: 6 towns: 5…
Marcos Fernandez Ramos
  • 101
0
votes
0 answers

Combinations of Catalan numbers with restrictions

I have to pair numbers in a circle without crossing chords. This: Image example The way to solve this is Catalan Numbers where n = nodes/2 The problem comes with some restrictions. I have to calculate the number of possible combinations without…
dvil
  • 1
0
votes
1 answer

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 all bad paths are deflected into a different target…
Val
  • 1