All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
1
vote
0
answers
61
views
Closed expression for $\sum _{m=1}^n{{n+m}\choose n} $ [duplicate]
I was given a problem in University:
Let $n\in \mathbb N $. Find a closed expression for the following sum $\sum _{m=1}^n{n+m\choose n}$.
I expressed binomials ${n+m}\choose {n}$$=\frac{(n+1)(n+2)......
- 571
1
vote
3
answers
146
views
Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$
Is there a closed form of the expression
$$
\sum_{i = 1}^{\left\lfloor\left(n + 1\right)/2\right\rfloor}
i\binom{n - i + 1}{i}
$$
My Attempt:
From what I observe it is a situation where
there are $n/...
- 9,599
4
votes
0
answers
128
views
Calculating $\sum\limits_{k=0}^n\binom{n}{k}/\left(2^k+2^{n-k}\right)$
I am trying to find a closed form for $\sum\limits_{k=0}^n\frac{\binom{n}{k}}{2^k+2^{n-k}}$. I saw on quora that integration can be used to rewrite portions of such equations, and so I attempted this. ...
- 71
2
votes
1
answer
62
views
How to apply Vandermonde's Identity regarding summation bounds ? $\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\binom{-k-j-2}{n-j-k}$
from the answer: Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
this happens from step 4 to 5:
$$
\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\...
- 123
2
votes
2
answers
85
views
Limit of $\sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k$ as $n\to \infty$ (and $k=n$)
Question
Find $\lim_{n\to \infty} P(n,n)$ where
$$
P(n,k) = \sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k.
$$
The origin of this sum is from this question. The ...
- 9,748
2
votes
1
answer
75
views
Prove the following combinatorics equality [duplicate]
$$\mbox{Prove the equality:}\quad
\binom{n}{k + m + 1} = \sum_{j = k + 1}^{n - m}
\binom{j - 1}{k}\binom{n - j}{m}
$$
for $m + k < n$.
I tried to prove this using combinatorics and doing some ...
- 169
4
votes
1
answer
47
views
Combinatorial proof that $\sum_{k=1}^{n} k {2n \choose n+k}=\frac{1}{2}n{2n \choose n}$ [duplicate]
I'd like to find a combinatorial/algebraic proof of the identity:
$$\sum_{k=1}^{n}k{2n \choose n+k}=\frac{1}{2}n{2n \choose n}$$
The only proof of this that I've been able to find on the Internet, ...
- 81
2
votes
4
answers
155
views
A Combinatoric Identity Involving Binomial Coefficients: $\sum^{n}_{r=1} {n \choose r} (-1)^r \frac{2^r-1}{2r}= \sum^{n}_{r=1}\frac{(-1)^r}{2r}$
Recently I came across this combinatoric identity:
$$
\begin{equation}
\sum^{n}_{r=1} {n \choose r} (-1)^r \frac{2^r-1}{2r}
\end{equation} = \sum^{n}_{r=1}\frac{(-1)^r}{2r}
$$
I have verified that ...
- 23
1
vote
1
answer
54
views
Hint for a combinatorial proof of $n! \binom{n-1}{k-1} = \sum_{j=0}^n \overline{s}_{n,j} \tilde{S}_{j,k}$
To clarify notation, we have $\overline{s}_{n,j}$ the unsigned Stirling numbers of the first kind, meaning the number of permutations on an set with $n$ elements that has exactly $j$ cycles. $\tilde{S}...
1
vote
2
answers
204
views
How to prove that for $a,b \in \mathbb{C}$, $\sum\limits_{k=0}^n \binom{a}{k}\binom {b}{n-k}= \binom{a+b}{n}$?
This exercise came from Complex Analysis by Freitag and Busam 1.2.11.
$$\binom{a}{n}:= \prod_{j=1}^n\frac{a-j+1}{j} $$
Show: $\sum\limits_{\nu=0}^{\infty}\dbinom{\alpha}{\nu} z^\nu$ is absolutely ...
- 6,620
0
votes
1
answer
78
views
Expressing a combination as sums of three terms or more, analogous to Pascal's identity
Are there any ways to express binomial coefficients as the sum of three or more terms, similar to how Pascal's Identity breaks a combination into the sum of two terms by relating two adjacent binomial ...
- 11
6
votes
2
answers
267
views
Counting bit strings with given numbers of higher-order bit flips
Background information
Bit flips
Given a bit string, we say that bit flip happens when $0$ changes to $1$ or $1$ changes to $0$.
To find bit flips, we can shift the string by $1$ and xor that new ...
1
vote
3
answers
79
views
Combinatorical identity $\sum_{k = d-i}^d (-1)^{k-d+i} \binom{k}{d-i} \cdot \binom{n}{d-k} = \binom{n-d+i-1}{i}$
How do we proove the following ugly identity of binomial coefficients?
$$\sum_{k = d-i}^d (-1)^{k-d+i} \binom{k}{d-i} \cdot \binom{n}{d-k} = \binom{n-d+i-1}{i}$$
First I thought we could use ...
- 141
0
votes
0
answers
38
views
Understanding the Derivation of a Formula Involving Binomial Coefficients and Factorials
I'm studying a formula that involves binomial coefficients and factorials, and I'm struggling to understand how it was derived.
The image below is a screenshot from the paper. They are taking the ...
- 326
3
votes
2
answers
113
views
An unusual binomial coefficient identity
I derived the following family of binomial coefficient identities rather indirectly for natural $t \ge 2$ (though it seems to hold more generally). I was hoping someone out there might know if this ...
- 51