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 ...
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 ...
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 ...
- 131
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 ...
- 39
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-...
- 179
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 \...
- 25
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 ...
- 1,940
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?
...
- 341
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} \...
- 61
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
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 ...
- 1,050
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$ ...
- 23
3
votes
3
answers
158
views
Iterated rascal triangle row sums
In this manuscript the authors propose the following conjecture (1)
\begin{align*}
\sum_{k=0}^{4i+3} \binom{4i+3}{k}_i &= 2^{4i+2}
\end{align*}
where $\binom{4i+3}{k}_i$ is iterated rascal ...
- 558
2
votes
2
answers
47
views
Given a set of integers, and the number of summations find the resulting frequencies
Given a set $X = \{x_1,x_2,...x_m\}\subset \mathbb{Z}$ and the number of allowed addends $N$. How can I find the frequency of every possible sum?
Example: $X = \{-1, 2\}$ and $N=3$ then every ...
- 389
1
vote
1
answer
38
views
Summation of n-simplex numbers
Gauss proved that every positive integer is a sum of at most three triangular(2-simplex) numbers. I was thinking of an extension related to n-simplex.
Refer: https://upload.wikimedia.org/wikipedia/...
0
votes
0
answers
45
views
Closed form for nested sum involving ratios of binomial coefficients
I ran into the following nested sum of binomial coefficients in my research, but I couldn't find the closed form expression for it. I looked at various sources and still couldn't find the answer. So I ...
3
votes
1
answer
84
views
Combinatorial Proof of the $\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n + 1) 2^{n - 2}$ [duplicate]
How to prove that $$\sum_{k = 1}^{n}k^2\binom{n}{k} = n(n + 1)2^{n -2}$$ in an combinatorial way?
I have a algebraic proof method, but I don't know how to use a combinatorial proof method to do it.
- 31
0
votes
0
answers
43
views
Evaluating Difference of Product of Binomial Coefficients
As part of my project I'm asked to evaluate the positivity of the following difference: $$\binom{l_1+t-1}{l_1}\binom{l_2+m+t-1}{l_2+m}\sum_{j=0}^{t}\binom{t-j+m}{m}\binom{j+l_1}{j}\binom{j+l_2}{j}-\...
- 61
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=(...
- 135
0
votes
0
answers
44
views
Choosing an ordered triplet of non-negative integers $(m_1, m_2, m_3)$ such that $m_1 + m_2 + m_3 = n$.
Define
$$A = \{ (m_1, m_2, m_3) : m_1 \geq 0, m_2 \geq 0, m_3 \geq 0, m_1 + m_2 + m_3 = n\}$$
Given that $n \geq 0$ and $n, m_1, m_2, m_3 \in \mathbb{Z}^+$, then why it is the case that
$$\vert A \...
- 934
0
votes
2
answers
45
views
Trying to prove equivalence of combinatorial formula and nested summations
I’m sorry if this is a dumb problem, but I’m trying to get into mathematics and prove this but I’m only in 9th grade and haven’t found any sources on this:
Prove that $$ {n \choose r} = \overbrace{ \...
4
votes
3
answers
70
views
$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$
Let $n$ and $a$ be natural numbers. How to prove the following for $x \in [0, 1)$?
$$
(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j
$$...
- 9,748
4
votes
1
answer
141
views
What is the name of this combinatorial identity?
In the course of my physics research, I appear to have stumbled onto the following combinatorial identity:
$${dn\choose m}=\sum_{\vec k} {n \choose \vec k}\,\prod_{j=0}^d {d \choose j}^{k_j},$$
where $...
- 1,835
0
votes
2
answers
73
views
Lower Bound on the ratio of binomial coefficients
Let $k,n,m$ be integers such that $k>n>m$. I am interested in providing a tight lowerbound on
$$
A(k,n,m)=\frac{\binom{k-m}{n-m}}{\binom{k}{n}}
$$
This term arises in a probability problem that ...
- 714
5
votes
2
answers
164
views
Estimate a sum of binomial coefficients
I should know this by the time, but: can someone tell me how to rigorously compute the leading order (including the constant) of the following sum:
$$\sum_{ 1\leq k \leq n/3 } {2 k \choose k} {n-2k-1 ...
- 1,363
4
votes
1
answer
78
views
Identity regarding the sum of products of binomial coefficients.
Consider the following toy problem
Person A and Person B have $n$ and $n+1$ fair coins respectively. If they both flip all their coins at the same time, what is the probability person B has more ...
- 3,234
2
votes
1
answer
69
views
Closed form for a sum of binomial coefficients
Let $m,n,r\in\mathbb{N}\cup\{0\}.$ I am interested in finding a closed form for the sum
$$\sum_{i=0}^m{{n+i}\choose{r+i}}.$$
Let $f(m,n,r)$ denote the above sum.
We may make a few trivial observations....
- 2,145
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
1
vote
2
answers
92
views
Alternating sum involving binomial coefficients
I want to prove that
$$
\sum_{i=0}^{n}{n\choose i}
\frac{\left(1 + \alpha i\right)^{n}
\left(-1\right)^{n - i}}{n!} = \alpha^{n}.
$$
This is a guess based on the computations for
$n = 0,1,2,3$.
Do you ...
- 61
0
votes
1
answer
34
views
How to Derive the Binomial Coefficient Upper Bound and Final Inequality in "Scheduling Multithreaded Computations by Work Stealing"?
In the paper Scheduling Multithreaded Computations by Work Stealing under the section "Atomic accesses and the recycling game", it mentions the binomial coefficient approximation:
$$ \binom{...
- 3
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
9
votes
3
answers
339
views
How can I simplify this combinatorics expression?
I got a expression that is related to the combinatorics, and it looks like this:
$$\sum_{k=1}^n \frac{2^{2k-1}}{k}\binom{2n-2k}{n-k}\cdot \frac{1}{\binom{2n}{n}}$$
it is from a question I've been ...
- 93
6
votes
2
answers
221
views
Is this identity I found playing around with generating function with coefficients $I(n) = \int_{0}^\pi \sin^n(x) dx$ useful and or reducible?
Let $I(n) = \int_{0}^\pi \sin^n(x) dx$ , using $\sin^2(x) = 1-\cos^2(x)$ and integrating by parts we get.
$$ \begin{align} I(n) = \dfrac{n-1}{n} I(n-2) \end{align} $$
With $I(0) = \pi$ and $I(1) = 2$ ...
- 61
0
votes
0
answers
52
views
Sum of every $k$th binomial coefficients over upperindex
From the Hockey-Stick Identity, we have for $n\geq r \geq 0$:
$$\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.$$
Now, I am wondering whether an identity exists for any fixed ( $k > 0$ ):
$$\sum_{i=...
- 113
3
votes
5
answers
218
views
Coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
Find the coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
I tried splitting the terms inside the bracket into two parts $1+x+\dots+x^9$ and $x^{10}$, and then tried binomial theorem, but that ...
- 565
2
votes
2
answers
74
views
Correctness of Solution for Forming a Committee with More Democrats than Republicans
I recently encountered a problem and derived a solution, but I am uncertain about its correctness. Here's the problem:
At a congressional hearing, there are 2n members present. Exactly
n of them are ...
- 33