All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
2
votes
1
answer
34
views
Connection Between Derivations of Finite and Infinite Binomial Expansion
At first when learning the binomial expansion you learn it in the case of working as a shortcut to multiplying out brackets - anti-factorising if you will. In these cases what you are expanding takes ...
- 432k
0
votes
1
answer
35
views
Binomial identity involving square binomial coefficient [closed]
I want to prove this identity, but I have no idea...
Could someone please post a solution? Thank you.
$$\sum_{k=0}^{n} \binom{-1/2}{n+k}\binom{n+k}{k}\binom{n}{k}= \binom{-1/2}{n}^2$$
(Maybe -1/2 can ...
- 62.3k
3
votes
1
answer
45
views
Steps on solving part b of the bit-string exercise?
This is the exercise:
How many bit strings of length $77$ are there such that
a.) the bit
string has at least forty-six $0$s and at least twenty-nine $1$s, and also
the bit string corresponding to ...
- 109k
2
votes
2
answers
91
views
Compute the value of a double sum
I need some help computing a(n apparently nasty) double sum:
$$f(l):=\sum_{j = \frac{l}{2}+1}^{l+1}\sum_{i = \frac{l}{2}+1}^{l+1} \binom{l+1}{j}\binom{l+1}{i} (j-i)^2$$
where $l$ is even. I'm not ...
- 109k
3
votes
3
answers
65
views
Prove that $\frac{(n + 1)!}{((n + 1) - r)!} = r \sum_{i=r - 1}^{n} \frac{i!}{(i - (r - 1))!}$
I Need Help proving That
$$\frac{(n + 1)!}{(n - r + 1)!} = r \cdot \sum_{i=r - 1}^{n} \frac{i!}{(i - r + 1)!}$$
Or in terms of Combinatorics functions:
$P_{r}^{n+1} = r \cdot \sum_{i = r-1}^{n} {P_{r-...
- 7,679
6
votes
3
answers
610
views
An identity involving binomial coefficients
Prove the following identity
$$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$
where $i = 0,1,\cdots,m$ and $m, n$ are ...
- 62.3k
3
votes
4
answers
3k
views
Binomial coefficients identity: $\sum i \binom{n-i}{k-1}=\binom{n+1}{k+1}$
I am trying to prove
$
\sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1}
$
Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the ...
- 165
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
0
votes
1
answer
42
views
Binomial coefficient inequality ${n+x \choose x} > {{m+q-x} \choose q-x}$
Let $m,n,q$ be positive integers and $0\leq x\leq q$ where $x$ is an integer.
When does the inequality
$$
{n +x \choose x} > {{m+q-x} \choose q-x}
$$
hold?
Using the Hockey-Stick identity,
$$
{n+x \...
- 100k
3
votes
0
answers
162
views
Closed form for $\sum_{k=n}^{2n-1} k(-1)^k \sum_{i=k}^{2n-1} {2n \choose i+1} {i \choose n}$?
I've found this sum:
$$S(n) = \sum_{k=n}^{2n-1} k(-1)^k \sum_{i=k}^{2n-1} {2n \choose i+1} {i \choose n}$$
The inner sum is elliptical iirc, but perhaps the double sum has a nice expression. We can ...
- 78.1k
2
votes
1
answer
72
views
Express Lucas numbers as a sum of binomial coefficients
So here's the question, prove that $$L_n = \sum_{k=0}^{n} \frac{n}{n-k} \binom{n-k}{k}$$
where $L_n$ is the $n$-th Lucas number.
It really resembles the Fibonacci identity: $$F_n = \sum_{k=0}^{n} \...
- 62.3k
0
votes
1
answer
33
views
How to upper bound $\sum_{m=2}^{d-1}\binom{n}{d+1+m} n^{-\alpha 2m} $ [closed]
As I'm saying in the title, I am looking for an upper bound (or an identity) for this:
$$
\sum_{m=2}^{d-1}\binom{n}{d+1+m} n^{-\alpha 2m}
$$
where $\alpha \in [0,\infty)$.
Any ideas/suggestions?
...
- 356
0
votes
0
answers
34
views
Probability involving identical objects. I am not able to understand how the Ncr formula is being applied below for counting identical objects.
Question: A bag contains 5 identical red coins, 6 identical yellow coins and 8 identical blue coins. If 3 coins are picked up randomly from the bag, what is the probability that there is at least one ...
- 47.4k
2
votes
2
answers
64
views
binomial distribution but sometimes the last outcome doesn't matter
Here's the motivation for my question: I'm designing an RPG. To simplify as much as possible, lets say my enemy has $h = 4$ HP and I deal $a = 1$ damage with every attack.
However, there's also a $p$ ...
- 102k
21
votes
6
answers
19k
views
How to show that this binomial sum satisfies the Fibonacci relation?
The Binomial Sum
$$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$
satisfies the Fibonacci Relation.
$$
\mbox{I failed to prove that}\quad
\binom{n-k+1}{k}=...
- 91k