Skip to main content

Questions tagged [catalan-numbers]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
78 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 ...
Rus May's user avatar
  • 2,209
1 vote
0 answers
50 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}$?...
alteredpulse's user avatar
8 votes
1 answer
210 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=...
maxwelldecoherence's user avatar
2 votes
3 answers
85 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 ...
user avatar
1 vote
1 answer
95 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 $...
Soheil's user avatar
  • 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 ...
Quick_Fix's user avatar
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$ : $$...
Allison's user avatar
  • 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 ...
Email's user avatar
  • 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 ...
fern-gossow's user avatar
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-...
Tung Nguyen's user avatar
  • 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. ...
Lukas Kröger's user avatar
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 ...
MattSH's user avatar
  • 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 $\...
Mods And Staff Are Not Fair's user avatar
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 ...
ynjuan's user avatar
  • 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. ...
ynjuan's user avatar
  • 51
0 votes
0 answers
85 views

Catalan Numbers: Sequence of -1 and 1 that sums to 0 with conditions

There is a relatively simple bijection between 0-sum sequences of 1 and -1 where the sum of all partial sequences is nonnegative and Dyck paths - this is very easy to count as a Catalan number. ...
C Smith's user avatar
  • 11
1 vote
0 answers
50 views

Lattice Paths $C_{n}$ & $C_{n-1}$

I'm trying to see if I'm correct with a general approach to solving these lattice path problems using the commonly known reflection proof and the Catalan numbers. If we want to see how many paths we ...
Ziggy's user avatar
  • 147
3 votes
1 answer
105 views

Catalan numbers in numerical sequences

How to show that the number of sequences of the form ($a_1$, $a_2$, ..., $a_n$) when $\sum_{k=1}^i(a_k) \geq i$ for each $i$ and $\sum_{k=1}^n(a_k)$ = $n$ is equal to the corresponding Catalan number (...
noname's user avatar
  • 133
0 votes
0 answers
24 views

Counting Paths in the XY Plane (Discrete math) [duplicate]

I need help with the following mathematical task: A particle moves in the xy-plane according to the following rules: U: (m, n) → (m+1, n+1) L: (m, n) → (m+1, n-1) where m and n are integers. I need ...
Bryan C's user avatar
  • 39
3 votes
1 answer
141 views

$n$- transposition permutations in $S_{2n}$ which decompose a $2n$-cycle into $n+1$ cycles

I was learning about Catalan numbers online. I have understood the combinatorial argument, recurrence relation and generating function based proofs of Dyck words and Dyck paths. Let $S_{2n}$ be the ...
Nothing special's user avatar
7 votes
0 answers
498 views

Finding a closed form for the series $\sum_{n=0}^{\infty}\frac{\binom{2n}{n}^3}{64^n(n+1)^k}$ for $k=1,2,3,4$

Context: This question is related to Calculate $\sum_{n = 0}^\infty \frac{C_n^2}{16^n}$ and Is there a closed form for a give infinite sum?. We have also: $$\sum_{n=0}^{\infty}\frac{\binom{2n}{n}^3}{...
User's user avatar
  • 323
1 vote
1 answer
218 views

Binary string such that always at least as many 0s as 1s

Problem: Find the number of binary strings of length $10$ with $5$ ones and $5$ zeros such that, at any given point in the string (reading from left to right), there has appeared at least as many $0$s ...
Martin Westin's user avatar
3 votes
2 answers
117 views

Bijection between the set of coin tosses with an equal number of $H$'s and $T$'s and the set where $H$'s and $T$'s are never equal

Let $D_n$ be the set of $2n$ coin tosses where the number of $H$'s and $T$'s are never equal as you read from left to right. For example, $$D_2 = \lbrace TTTT, TTTH, TTHT, HHTH, HHHT, HHHH \rbrace.$$ ...
Alex's user avatar
  • 2,391
1 vote
0 answers
75 views

Geometrical/Combinatorial interpretation of $ \pi = \frac{27}{4 \sqrt 3} \sum_2^∞ \frac{1}{C(k)} $

I found this question on here, but no real answer was given. Is there a geometrical or combinatorial interpretation of this result? $ \pi = \frac{27}{4 \sqrt 3} \sum_2^∞ \frac{1}{C(k)} $ Where $ C(k) $...
user967210's user avatar
0 votes
0 answers
75 views

Catalan number's combinatoric proof [duplicate]

prove a combinatoric proof the identity: $ \sum_{k=0}^{n} $$\frac{1}{k+1}\binom{2k}{k}\binom{2n-2k}{n-k} = \binom{2n+1}{n} $ I tried using Catalan numbers: and one of the formulas for them: $C_{n} = $...
yahel amity's user avatar
0 votes
0 answers
55 views

Formal Power Series for Recursion where Successor is Linear Combination of all Predecessors

I am trying to solve a recursion of the form \begin{equation*}a_n=\sum_{j=1}^{n-1} k_{j,n} \cdot a_j + d_n \end{equation*} where $k_{j,n}$ and $d_n$ are constants depending on $j,n$ and $n$, ...
Antigone's user avatar
  • 115
5 votes
1 answer
153 views

A curious identity for powers of the generating function of the Catalan numbers.

For a power series $\displaystyle f(x)=\sum_{n\geq 0}a_n x^n$ let $\displaystyle[f(x)]_r=\sum_{n\geq r} a_n x^n.$ Let $\displaystyle c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the ...
Johann Cigler's user avatar
0 votes
0 answers
39 views

Balanced binary sequence with odd length.

I am facing an equal problem to this but I can't seem to have an algorithm that would allow me to count it. The problem: Let X(n) be the set of all possible balanced binary sequences, where 0's ...
study.isLove's user avatar
2 votes
1 answer
286 views

Finding the Formula for the Catalan Numbers and Motzkin Numbers

I have derived the following generating function for the Catalan numbers: $$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$ Now I know my next step is to use the extended binomial theorem to expand $$\sqrt{1-4x}=(1+(-...
Moh's user avatar
  • 111
2 votes
1 answer
70 views

Equivalent classes in monotonic lattice paths and Catalan numbers

I have already understand the basic proof of Catalan numbers through monotonic lattice paths. However, I am know figuring out the specific case: if the two paths are symmetric about a diagonal line (...
Erus Izumi's user avatar
5 votes
1 answer
101 views

Catalan interpretation

I have question and I think the answer is equal with Catalan numbers. The question as follows: The number of the sequence $a_0a_1a_2\cdots a_na_{n+1}$ of integers with $a_i\geq 2, a_0=a_{n+1}=1$ and $...
d.y's user avatar
  • 649
2 votes
1 answer
146 views

How to evaluate $\sum_{i=0}^n i^2 C_{i-1} C_{n-i-2}$?

I'm evaluating the sum and I've gone through things below: Consider $C_{-2}=0,C_{-1}=-1 \\$ where $C_n$ stands for the nth Catalan number $$ S_n=∑_{i=1}^ni^2 C_{i-1} C_{n-i-2}=∑_{i=0}^ni^2 C_{i-1} C_{...
lyx's user avatar
  • 49
1 vote
0 answers
49 views

Dyck paths without centered tunnels

This is from Stanley's Catalan Numbers, problem 36: I have difficulty understanding the problem: there is no $L$, $L$'s endpoints lie on $P$ (what is $P$?) and every point of $L$ lies on or below $D$,...
Haoran Chen's user avatar
1 vote
1 answer
74 views

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 ...
Haoran Chen's user avatar
0 votes
0 answers
39 views

How to prove $\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$? [duplicate]

How to prove the following identity? $$ \sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1 $$ where $C_k$ is the $k$th Catalan number, $C_n=\frac{1}{k+1}\binom{2k}{k}$. This question is similar to this but ...
bananana's user avatar
0 votes
1 answer
90 views

Probability / Permuations: Expected Number of Games Till Bust

You bet 1 dollar in a game in which the win probability of each round is 0.55. As long as you don't go bust (have $0 left), you could bet up to 100 times. You start with 4 dollars in the bank. What is ...
lavam's user avatar
  • 3
0 votes
1 answer
112 views

Let $a_n$ denote the number of circular words of length $2n + 1$ over the alphabet A = {0,1} in which exactly $n$ zeroes occur.

I started studying on discrete mathematics and I came across the following "advanced question" in my textbook: Let $a_n$ denote the number of circular words of length $2n + 1$ over the ...
MathStarter's user avatar
4 votes
1 answer
88 views

How to count pairs with Catalan distribution

Say I have a set of $n$ pairs, such that I have a total of $2n$ elements. I arrange them in pairs following a Catalan distribution, i.e. if I lay them in a 1D line, I have no crossing (See the ...
J.Agusti's user avatar
  • 155
1 vote
1 answer
244 views

Catalan numbers, paths on a grid

I'm struggling to understand the concept of the idea. Some questions "push" me to use the reflection method which is hard for me to imagine and understand. I prefer to look at it as a ...
X4J's user avatar
  • 1,052
0 votes
1 answer
198 views

Modify the lattice path for Catalan Number

It is known that $C_{n}$ ($n$-th Catalan number) is the number of monotonic lattice paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal. A monotonic ...
1Spectre1's user avatar
  • 377
5 votes
3 answers
288 views

A series sum involving Catalan numbers

I was trying to compute $$\sum_{k=0}^{n} \left(-\frac{1}{2}\right)^k \, \binom{2k}{k} \, \frac{k}{k+1} = \sum_{k=0}^n \left(-\frac12\right)^k k C_k$$ (where $C_k$ is the $k^{\rm th}$ Catalan number) ...
physicist's user avatar
4 votes
2 answers
665 views

Number of balanced bracket sequences with given prefix and suffix

I've been trying to solve the following problem: Find the number of balanced bracket sequences of size $N+M+K$ which start with a prefix of $N$ continuous opening brackets and end with a suffix of $M$ ...
User1234's user avatar
0 votes
2 answers
55 views

I am trying to understand a certain proof of Catalan numbers and I do not understand a math behind one part

The proof got that $$ \frac{1}{k+1}\frac{(2k)!}{(k!)^2}=\frac{1}{k+1}{2k \choose k} $$ Which indeed is the formula for Catalan numbers but I do not understand how: $$ \frac{(2k!)}{(k!)^2}={2k \choose ...
Mihailo's user avatar
  • 73
0 votes
1 answer
49 views

Compute how many ways to get to (n,n) from (0,0) you must cross x=y only once at (k,k+1)

In the question we have a cat in $(0,0)$. The cat can only go right or up. The cat wants to reach $(n,n)$, but must go through one of the points above $(x=y)$. Meaning a point $(k,k+1)$. Compute how ...
DanaN's user avatar
  • 43
3 votes
1 answer
88 views

Catalan Numbers as placing objects into boxes

Let $a_n$ be the number of ways of placing $n$ indistinguishable objects into $n$ distinguishable boxes called $B_1$, $B_2$, ..., $B_n$, such that the following hold: There is at most $1$ object in $...
beans's user avatar
  • 31
4 votes
1 answer
193 views

Product of Inverse Hankel Matrix

Consider $H_n$, the $n\times n$ Hankel matrix of the Catalan numbers starting from $2$: $$H_n = \begin{bmatrix} 2 & 5 & 14 & 42 & 132\\ 5 & 14 & 42 & 132 & 429\\ 14 &...
yanjunk's user avatar
  • 219
0 votes
1 answer
52 views

Find coefficient in series expansion of $x^2C^3(x)$

I need to find the $n$-th coefficient of the expression $P(x)=x^2C^3(x)$ where $C(x)$ is the generating function for the Catalan numbers: $$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$ I'm trying to solve the ...
Daniel Checa's user avatar
0 votes
0 answers
94 views

A problem about diagonal lattice path [duplicate]

The problem I am facing is: Suppose we have a diagonal lattice path which is defined over a $x-y$ coordinate plane. We can go either from $(i,j)$ to $(i+1,j+1)$ or from $(i,j)$ to $(i+1,j-1)$. Then ...
End points's user avatar
3 votes
1 answer
128 views

Verification of $(m+1)| \binom{2m}{m}$ and interpretation

While examining the central binomial coefficients, I noticed that $(m+1)$ always seemed to divide $\binom{2m}{m}$. I would like to confirm that a short proof I have found, using Hall's theorem, is ...
legionwhale's user avatar
  • 2,466
6 votes
1 answer
264 views

Combinatorial proof for a Catalan number identity with an alternating sum.

Define the function $$ T_a(x) := 1/(a + 1/x). \tag1 $$ It is easy to check that $$ T_{a+b}(x) = T_a (T_b(x)). \tag2 $$ Specialize this equality to get $$ x = T_ 0(x) = T_ 1(T_{-1}(x)) = T_{-1}(T_ 1(x))...
Somos's user avatar
  • 36.1k

1
2 3 4 5
11