Questions tagged [catalan-numbers]
For questions on Catalan numbers, a sequence of natural numbers that occur in various counting problems.
503
questions
1
vote
1
answer
77
views
Deriving the generating function for the Catalan triangle
I'm hoping for help in deriving the two-variable generating function for the Catalan triangle, also known as a truncated version of Pascal's triangle. There are a few variations floating around, so to ...
- 2,209
1
vote
0
answers
47
views
Find the number of lattice paths weakly under a slope $y = \mu x$
How many lattice paths are there from an arbitrary point $(a,b)$ to another point $(c,d)$ that stay weakly (i.e. it can touch the line) under a slope of the form $y = \mu x$, with $\mu \in \mathbb{N}$?...
- 11
8
votes
1
answer
208
views
Generating function for the products of pairs of Narayana numbers
The Narayana numbers OEIS sequence A001263 are given by:
$$\operatorname{N}(n, k) = \frac{1}{n} {n \choose k} {n \choose k-1},$$
and have the generating function:
$$G(z,t) = \sum_{n=1}^\infty \sum_{k=...
2
votes
3
answers
84
views
What is the number of lattice paths of length 16 from the point (0,0) to (8,8) that go through (4,4) but don't go through (1,1), (2,2), (3,3)
what is the number of lattice paths of length 16 from $(0,0)$ to $(8,8)$ that go through $(4,4)$, don't go through $(1,1), (2,2), (3,3)$, and don't go over $y=x$?
Here's what I tried:
since we can't ...
user1136752
1
vote
1
answer
93
views
Why Catalan Numbers are the general solution of this combinatorics problem?
This is a problem of this year's $AMC$ $8$ math competition,
Buzz Bunny is hopping up and down a set of stairs, one step at a time. In how many ways can Buzz start on the ground, make a sequence of $...
- 6,794
2
votes
1
answer
93
views
Why does the number of permutations of these sequences with non-negative partial sums have such a simple closed form (m choose n)?
I've been thinking about a problem, and I think that I have a solution, and I'm not sure why it works. Looking for an intuitive (or just any) explanation.
The problem
Choose an integer $k>1$. For ...
- 61
0
votes
1
answer
104
views
Generating Functions for Recursive String Compositions with Parenthetical Constraints
Consider $S$ the following recursively defined set; $S$ contains the empty string and, for any strings $a$ and $b$ in $S$, the string $(a b)$ is also in $S$. Here are the first few elements of $S$ :
$$...
- 195
1
vote
0
answers
99
views
Counting the number of possible sequences increasing by no more than one [closed]
Count the number of sequences of integers $a_1, a_2, \dots, a_n$ such that
$$
a_1 = 0
\quad\text{and}\quad
0 \leq a_{i+1} \leq a_i + 1
\quad\text{for}\quad
1 \leq i < n.
$$
At first, I was ...
- 61
3
votes
1
answer
57
views
Combinatorial explanation of Catalan asymptotics
It is well-known that the Catalan numbers have an asymptotic approximation
$$C_n\sim \frac{4^n}{\sqrt{\pi}n^{3/2}}.$$
I am curious about combinatorial interpretations of this formula, rather than a ...
- 83
1
vote
0
answers
50
views
What is the difference between counting plane tree and binary tree by Catalan numbers? [duplicate]
Problems: Prove that the number of plane trees with $(n+1)$ vertices is $n-th$ Catalan number $C_n$.
For this problem: I have found a solution in a post on Mathstack Prove that number of non-...
- 1,238
5
votes
1
answer
165
views
Passenger entrance/exit combinations
In question is:
The number of possible ways a vehicle with capacity $K$ can pickup and
drop off $n$ passengers in a single tour, while each passenger has an
individual pickup and dropoff location.
...
- 53
1
vote
0
answers
27
views
I want to count the multiplicity of specific peak sets occurring in a standard shifted tableau with some restrictions. Possibly using path counting?
Ok first some definitions:
Let a shifted diagram of some strict partition $\lambda$ be a Young tableau whose $i^{th}$ row is shifted $i-1$ spaces to the right, (I use french notation, and start ...
- 31
1
vote
2
answers
205
views
Which closed form expression for this series involving Catalan numbers : $\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{4^nn^2}\binom{2n}{n}$
Obtain a closed-form for the series: $$\mathcal{S}=\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{4^nn^2}\binom{2n}{n}$$
From here https://en.wikipedia.org/wiki/List_of_m ... cal_series we know that for $\...
5
votes
1
answer
129
views
Prove: $\sum_{i=0}^{n-1} C_i\binom{2(n-i)-1}{n-i} = \binom{2n}{n+1}$
I am working on the following problem:
Given that all of the legal paths (ones which do not cross over the line $y = x$) from $(0,0)$ to $(n,n)$ must begin with a move to the right and end with a move ...
- 51
0
votes
0
answers
49
views
How to compute the number of illegal lattice paths from $(0,0)$ to $(n,n)$ without reflection?
I am currently pondering over the problem of the number of lattice paths:
All of the legal paths (ones which do not cross over $y=x$) must begin with a move to the right and end with a move upwards. ...
- 51