Questions tagged [catalan-numbers]
For questions on Catalan numbers, a sequence of natural numbers that occur in various counting problems.
488
questions
1
vote
0
answers
27
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 ...
- 147
3
votes
1
answer
81
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)$ >= $i$ for each $i$ and $\sum_{k=1}^n(a_k)$ = $n$ is equal to the corresponding Catalan ...
- 51
0
votes
0
answers
22
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 ...
- 39
3
votes
1
answer
109
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 ...
- 766
7
votes
0
answers
394
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}{...
- 397
1
vote
1
answer
77
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 ...
- 520
3
votes
2
answers
68
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.$$
...
- 2,306
0
votes
0
answers
23
views
Non-Negative Partial Sums and Double Factorial
Consider a sequence, $s$, with elements $1$ and $-1$, of length $2k$, $k > 0$, with sum zero and non-negative partial sums, so that:
\begin{align}
\sum_{i=1}^{2k} s_{i} &= 0 \\
p_j = \sum_{i=1}^...
- 352
1
vote
0
answers
71
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) $...
- 571
0
votes
0
answers
65
views
Catalan number's combinatoric proof
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} = $...
- 53
0
votes
0
answers
49
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$, ...
- 105
4
votes
1
answer
112
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 ...
- 1,299
0
votes
0
answers
33
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 ...
- 23
2
votes
1
answer
103
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+(-...
- 111
2
votes
1
answer
54
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 (...
- 119
5
votes
1
answer
89
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 $...
- 649
2
votes
1
answer
105
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_{...
- 29
0
votes
0
answers
34
views
(Code implementation of) Gosper's algorithm for sums (of catalan numbers) that are dependent on end-point
I'm working on my understanding of Catalan numbers and recurrence relations in general. In trying to prove they satisfy a certain recurrence relation, I wanted to find a telescoping sequence to ...
- 1
1
vote
0
answers
42
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$,...
- 627
1
vote
1
answer
44
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 ...
- 627
0
votes
0
answers
35
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 ...
- 13
0
votes
1
answer
76
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 ...
- 3
0
votes
1
answer
58
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 ...
- 45
4
votes
1
answer
81
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 ...
- 147
1
vote
1
answer
94
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 ...
- 865
0
votes
1
answer
110
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 ...
- 377
5
votes
3
answers
216
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) ...
- 51
4
votes
2
answers
345
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$ ...
- 41
0
votes
2
answers
51
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 ...
- 73
0
votes
1
answer
43
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 ...
- 43
3
votes
1
answer
69
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 $...
- 31
4
votes
1
answer
125
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 &...
- 164
0
votes
1
answer
51
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 ...
- 501
0
votes
0
answers
89
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 ...
- 427
3
votes
1
answer
111
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 ...
- 2,165
6
votes
1
answer
201
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))...
- 33.8k
1
vote
0
answers
114
views
Is there a way to find the integer solutions of $x^2 = y^3 + 1$ with elementary NT [duplicate]
I am a 14 year old that started preparing for the youth Balkaniad. I stumbled on some questions that will be way easier if only I knew how to solve this( I am not allowed to use Catalans in the ...
- 347
6
votes
1
answer
176
views
The relation of the Bernoulli numbers to the Catalan numbers
The Bernoulli numbers $B_n$ are the backbone of calculus, and according to B. Mazur, they "act as a unifying force, holding together seemingly disparate fields of mathematics."
The Catalan ...
- 815
0
votes
0
answers
59
views
Products of Catalan Numbers
The catalan numbers are extremely well known, with several bijections and a known generating function. But what about products of catalan numbers?
If we define the sequence $P(x) = \prod_{i=0}^x C(i)$,...
- 502
2
votes
0
answers
139
views
Proof of equating coefficients validity in Catalan number formula derivation?
Kindly find below the $5^{th}$ proof of Catalan formula from Wikipedia. After obtaining $2$ formulas for $B_{n+1}-C_{n+1}$, in this case why is it valid to say that $2B_i-C_i={2i+1\choose i}$? ...
- 205
1
vote
2
answers
224
views
Factors of central binomial coefficient
The central binomial coefficient $\binom{2n}{n}$ is divisible by $n+1$, as seen from the
identity
$$\binom{2n}{n} = (n+1)\binom{2n}{n} -(n+1)\binom{2n}{n+1}.$$
In fact the Catalan numbers
$$C_n=\frac{...
- 370
11
votes
2
answers
359
views
Conjecture: $\frac1\pi=\sum_{n=0}^\infty\left((n+1)\frac{C_n^3}{2^{6n}}\sum_{k=0}^n(-1)^k{n\choose k}{\frac{(n-k)(k-1)}{(2k-1)(2k+1)}}\right)$
Let $C_n$ denote the $n$-th Catalan number defined by
$${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\quad \left(n\geqslant 0\right).}$$
Next, we define ...
- 375
1
vote
1
answer
69
views
Analytic formula for $E(\rho):=\sum_{m=0}^\infty \mu_m(\rho)/m!$, with $\mu_m(\rho) := \sum_{k=0}^{m-1}\dfrac{\rho^k}{k+1}{m \choose k}{m-1\choose k}$
Let $\rho \in (0,\infty)$ and for any integer $m \ge 1$, define $\mu_m \ge 0$ by
$$
\mu_m := \sum_{k=0}^{m-1}\frac{\rho^k}{k+1}{m \choose k}{m-1\choose k}.
$$
Finally define $E \ge 0$ by
$$
E := \sum_{...
- 9,230
11
votes
1
answer
643
views
Intuitive Explanation for Number of Dyck Paths Never Going Above Diagonal of a Rectangle
Suppose we have a an $a\times{}b$ rectangle whose bottom-left corner is at $(0,0)$ and whose upper-right corner is at $(b,a)$. Let $a$ and $b$ both be positive integers, and let $b\geq{}a$. If $a$ and ...
- 501
0
votes
1
answer
124
views
How is the diagonal constraint in lattice path needed for the Catalan proofs?
I have been reading about the Catalan numbers and how they are they appear in many problems such as:
lattice paths
valid pair of parenthesis
mountains with up/downstrokes
non-crossing handshakes
...
- 1,581
1
vote
0
answers
74
views
Counting all possible pairs of parenthesis
If we want to count how many possible pairs $n$ of parenthesis we have when $n = 1$ then I think the way to count is $2 \choose 1$ since if we have $2$ symbols and we pick $one$ position to place $1$ ...
- 1,581
2
votes
1
answer
129
views
Why are the catalan numbers giving the unique/correct patterns from all the combinations?
I am reading about catalan numbers and they are considered to represent the number of valid pair of parentesis, mountains etc.
Although the number checks out correct when comparing against specific ...
- 1,581
0
votes
1
answer
41
views
How do we handle the factorials in the binomials/choice numbers?
Apparently the following is a known equality:
$\frac{1}{n + 1} {2n \choose n} = \frac{2n!}{n!(n + 1)!} = \frac{1}{2n + 1}{2n + 1 \choose n}$
but I can't really figure out how to produce the equality.
...
- 1,581
0
votes
0
answers
40
views
The intuitive correspondence between the multiplication schemes (or triangularizations) and -1s 1s sequences.
I am reading Richard A. Brualdi 's book Introductory Combinatorics (5th Edition).
In p.273, the author introduced the correspondence between the multiplication schemes for the n numbers a1, a2, ... ...
- 535
0
votes
1
answer
88
views
Infinite Catalan Sum involving polynomials
I was solving this problem:
Given a coin that lands on heads with $p$ probability, what is the probability that a series of coin flips will end with exactly one more head than tail? For instance, H ...
- 424