All Questions
60
questions
0
votes
1
answer
128
views
Spivak Exercise, Prove Vandermonde's Identity $\sum_{k=0}^{l}\binom{n}{k}\binom{m}{l-k}=\binom{n+m}{l}$ [duplicate]
Prove that
$$\sum_{k=0}^{l}\binom{n}{k}\binom{m}{l-k}=\binom{n+m}{l}$$
Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$
Proof:
Following Spivak's advice, we have
$\sum_{k=0}^{n}\binom{n}{k}x^k=(...
0
votes
1
answer
66
views
Seeking help to Prove The Recursive Binomial Coefficient Formula
A rich body of research exists on Binomial Coefficients, with the concept finding its roots in Pascal's Triangle. My current investigation focuses on a Recursive Approach for generating these ...
3
votes
0
answers
60
views
Prove combinatoric equation: $\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$
Prove the equation:
$$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$
My solution:
We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that ...
1
vote
1
answer
136
views
Enumerating $m\times n$ binary matrices with constant column sum and at least one non-zero row entry
I have worked out the following, and would appreciate if anyone can verify or suggest improvements.
If the columns should sum up to $k$, then there are $\binom{m}{k}^n$ $m\times n$-matrices with a ...
0
votes
1
answer
99
views
On the proof that $\binom{2n}{2}=2\binom{n}{2}+n^{2}$
I came across this problem and this related problem while browsing through the combinatorics section.
Although both of them have been closed, I find the discussion inside the solutions inside the ...
2
votes
1
answer
102
views
Proving the identity $\sum_{k=0}^{m} \binom{n-k}{m-k}= \binom{n+1}{m}$ .
Today we started talking about generating functions in class. I came across this identity:
$$\sum_{k=0}^{m} \binom{n-k}{m-k}= \binom{n+1}{m}$$
Here is my proof for this identity (If it is wrong please ...
2
votes
1
answer
61
views
Lattice path back at origin explanation
I know this is a very common question but there is something I seem to be misunderstanding. Let $S_n$ be a simple random walk in $\Bbb Z^2$ starting at $0$. I want to count the number of paths of ...
1
vote
0
answers
55
views
An attempt for finding the number of integer solutions with restrictions
How many integer solutions are there to the inequality $y_1 + y_2 + y_3 + y_4 < 184$
My question is about this problem. I tried my own method to solve it. However, I got the wrong answer. The right ...
2
votes
1
answer
129
views
Given $m$ objects of type A and $n$ objects of type B, arrange them such that there are not more than two consecutive objects of type B.
I came across this question on Quora and got interested in solving it.
Being given a number $m$ of objects of type A and a number $n$ of objects of type B, in how many ways can we create a bigger ...
2
votes
2
answers
726
views
Number of ways to invest $\$20,000$ in units of $\$1000$ if not all the money need be spent
Working through a combinatorics section currently and am working on this $2$-part problem. I have solved part $a$ quickly and will provide my work below but am having some trouble with part $b$ and ...
2
votes
2
answers
88
views
Identity for Difference of Sum of Products of Binomial Coefficients
Problem Statement
I recently came across the following equation that I want to prove:
$$
\sum_{i=1}^{n}
\left[
\binom{n+i}{m}-\binom{n-i}{m}
\right]
\binom{2n}{n-i}
=
\sum_{i=1}^{m}\binom{n+i}{m}\...
3
votes
0
answers
75
views
Binomial Coefficients Proof [duplicate]
I want to prove the claim that for all $n\geq 1,$ we have
$${n\choose r} > {n\choose r+1}$$ if and only if
$$n-1 \geq r > \frac{1}{2}(n-1).$$
Assume first that $${n\choose r} > {n\choose r+1}....
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 ...
1
vote
3
answers
177
views
calculate :$2000 \choose 2000$+....+$2000 \choose 8 $+$2000 \choose 5$+$2000 \choose 2$
my attempt:
let's put $2000 \choose 2000$+...+$2000 \choose 1001 $+...+$2000 \choose 8 $+$2000 \choose 5$+$2000 \choose 2$=$A+B$
with $A$=$2000 \choose 2000$+...+$2000 \choose 1001 $
and
$B$=$2000 \...
1
vote
3
answers
75
views
finding a closed formula for $\sum_{k=0}^{n} k{2n \choose k}$
my attempt:
$\sum_{k=0}^{n} k{2n \choose k}=\sum_{k=0}^{2n} k{2n \choose k}-\sum_{k=n+1}^{2n} k{2n \choose k}$
the first term in the right hand side
suppose there are $2n$ poeple, we have to choose a ...