All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
2
votes
1
answer
35
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 ...
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 ...
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-...
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 \...
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 ...
0
votes
1
answer
34
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?
...
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} \...
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}$?...
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 ...
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$ ...
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 ...
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 ...
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.
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}-\...
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
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 \...
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
$$...
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 $...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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{...