All Questions
37
questions
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
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
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
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
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.$$
...
- 2,381
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 ...
- 13
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 ...
- 3
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) ...
- 51
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 ...
- 2,466
0
votes
1
answer
156
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,609
2
votes
1
answer
136
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,609
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,609
9
votes
6
answers
797
views
How to find the sum $\sum_{k=1}^{\lfloor n/2\rfloor}\frac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}$
Let $n$ be positive integer, find the value
$$f(n)=\sum_{k=1}^{\lfloor n/2 \rfloor}\dfrac{2^{n-2k}\binom{n-2}{2k-2}\binom{2k-2}{k-1}}{k}. $$
I have found
$$ f(2)=1, \quad f(3)=2, \quad f(4)=5, \quad f(...
- 93.6k
4
votes
0
answers
145
views
Find bound for polynomial with binomial coefficients
I need to find a good, computable upper bound for the expression
$$\sum_{k=0}^m x^k \binom{n+k}{k}$$
as a function of $x$, $n$ and $m$, and where $0<x< 1/2$ is real, and $0<n\leq m$ are ...
4
votes
0
answers
106
views
Reference request for an identity involving Catalan numbers
I am wondering if a bijective proof of the following identity involving Catalan generating functions has appeared anywhere in the literature. (It's not difficult to simply verify it for the functions ...
- 4,175