Questions tagged [binomial-coefficients]
Coefficients involved in the Binomial Theorem. $ \dbinom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
6,902
questions
3
votes
3
answers
87
views
Evaluating $\sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k}$
So far I've been able to determine that if $n, r, s$ are nonnegative integers, then
$$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = \begin{cases}
0 &\qquad\text{ if } r+s < n, \\...
- 1,924
1
vote
1
answer
38
views
A combinatorial proof of a binomial coefficient summation identity. [duplicate]
$$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$
This is the exercise 3.3.6 of the book Invitation to Discrete Mathematics.
The answer in book is
Let M be an m-...
6
votes
4
answers
172
views
Inequality involving sums with binomial coefficient
I am trying to show upper- and lower-bounds on
$$\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i)$$
(where $n\geq 1$) in order to show that it basically grows as $O(n)$.
The upper-bound is easy to ...
- 124
1
vote
1
answer
85
views
Determinant of matrix with binomial coefficient elements equal to $\binom{2n-1}{n}$
Given an $n \times n$ matrix $A_n$ with elements $a_{ij}=\binom{n+i-1}{j}$, $1 \le i \le n$, $1 \le j \le n$, I noticed that its determinant $\lvert A_n \rvert$ seem to satisfy:
$$\lvert A_n \rvert = \...
- 1,869
3
votes
1
answer
38
views
Proving by Induction a Combinatorial Binomial
I'm currently stuck trying to prove that for all items in the sequence $\binom{n+1}{2}$, for all $n\geq 1$, that $\binom{n+1}{2}=\sum \limits _{i=0}^ni$.
My first assumption is to solve for my base ...
- 41
-1
votes
0
answers
38
views
Simplifying $ \sum_{k=1}^n\binom n{k-1}\frac{x^{k+n}y^{n-k+1}}k. $ [closed]
I want to simplify this binomial expression:
$$
\sum_{k=1}^n\binom n{k-1}\frac{x^{k+n}y^{n-k+1}}k.
$$
I tried to simplify it but it's pretty hard . So if someone can help with a hint or solution.
0
votes
1
answer
40
views
When $\text{ord}_n(p)/m = \text{ord}_{n/m}(p)=1$
$\newcommand\ord{\text{ord}}$
For integers $n,m,p$, suppose $m$ and $n$ share the same prime divisors with $m$ dividing $n$, and suppose $\text{gcd}(p,n)=1$.
I want to show that $\ord_n(p)/m=\ord_{n/m}...
- 211
-1
votes
1
answer
60
views
Finite summation including binomial coefficients [closed]
I'm trying to solve the summation below, but I can't get a nice algebraically reduced equation.
$$\sum_{k=1}^{2n} (-1)^{k-1}\frac{1}{\binom{2n}{k}} $$
I have tried to convert this into $\sum_{k=1}^{n}\...
- 11
-1
votes
1
answer
33
views
Number of ones in the dyadic expansion of m [closed]
I was going through a paper where I stuck on a combinatorial argument as follows
I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$.
As the author suggests it is ...
- 1,660
0
votes
0
answers
27
views
If there are closed form for $\sum\limits_{m=i}^\infty \frac{2}{(2m-1)(2m-1)!}\binom{2m-1}{m-i}$
If there are closed form for $$\sum\limits_{m=i}^\infty \frac{2}{(2m-1)(2m-1)!}\binom{2m-1}{m-i},$$ where $m,i$ are positive integers. I have tried defining the generating function $$\sum\limits_{i=1}^...
- 33
-1
votes
1
answer
49
views
Could someone please step me through the process of answering the Probability question?
Suppose that three unbiased dice are rolled. Find the probability that at least two of the three dice have a face value of five or more. Give your answer to two decimal places.
I understand there are ...
- 21
3
votes
3
answers
104
views
Prove that $\binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m$ for $m\in \mathbb{N}\backslash \{0,1\}$
Prove the following inequality for every $m\in \mathbb{N}\backslash \{0,1\}$:
$$ \binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m.$$
By some computational arguments, the inequality seems to be true and in ...
- 125
0
votes
2
answers
41
views
Expected number of pairs with Hamming distance $d$ for a sample of $k$ random bit strings of length $n$
Say we were to uniformly sample $k$ times from a bit string with length $n$. What is the expected number of pairs with a Hamming distance $d$? In the limit of Hamming distance 0, I realize this ...
- 31
1
vote
2
answers
28
views
Upper bound for binomial coefficients tighter than $(ne/k)^k$
In Shiryaev's book problems in probability, an upper bound for binomial coefficients is shown in section 1.2.1:
$$\binom{m+n}{n}\le(1+m/n)^n(1+n/m)^m.$$
It seems that this bound is sharper than the ...
- 11
0
votes
3
answers
94
views
Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$
Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$
The first differences between the terms are:
$1,2,4,8,15,26,42...$
The second differences (the differences between the ...
- 8,409
4
votes
2
answers
135
views
Question from isi previous years
(a) Show that $\left(\begin{array}{l}n \\ k\end{array}\right)=\sum_{m=k}^{n}\left(\begin{array}{c}m-1 \\ k-1\end{array}\right)$.
(b) Prove that
$$
\left(\begin{array}{l}
n \\
1
\end{array}\right)-\...
- 429
3
votes
2
answers
56
views
Find $100$th number $k$ such that there is no $n$ for which $n$! ends in $k$ zeroes.
$24! = 620,448,401,733,239,439,360,000$ ends in four zeroes, and $25! =
15,511,210,043,330,985,984,000,000$ ends in six zeroes. Thus, there is no integer
$n$ such that $n!$ ends in exactly five zeroes....
- 906
2
votes
3
answers
207
views
+500
Asymptotic for a binomial sum
Is it possible to derive an asymptotic expression as $n \to \infty$ for the following sum:
$$S_n(a,x) = \sum_{k=1}^n \binom{n}{k} \frac{k!^2 x^k}{k \cdot (a)_k} $$
$(a)_k$ is the rising factorial (...
- 30.2k
1
vote
0
answers
30
views
Lower bounding a exponential/binomial expression
I have been struggling to lower bound the following expression
\begin{equation}
f(N):= \frac{1}{N}\sum_{i=1}^N \frac{1}{2^N} \sum_{k=1}^{i} 2^{i-k} \binom{N+k-2}{k-1} ,
\end{equation}
with some simple ...
- 198
-2
votes
0
answers
42
views
Find Sum of (-1)^r × nCr/r
Find $\sum_{r=1}^n (-1)^r × \frac{1}{r} \binom{n}{r}$
How to find this? I tried doing it by taking $x$ common from the expansion and then integrate it using by parts but that didn't go well. Please, ...
3
votes
1
answer
45
views
Proving $\sum_{k=0}^{n-m}(-1)^k{n-m\choose k}\frac{k}{k+m}=-{n\choose m}^{-1}$
So apparently we can calculate the value of this series as
$$\sum_{k=0}^{n-m}(-1)^k{n-m\choose k}\frac{k}{k+m}=-\frac{m!(n-m)!}{n!}=-{n\choose m}^{-1}$$
But I'm curious to prove this holds.
So I ...
- 301
1
vote
0
answers
23
views
Probability of extracting 1 Red ball from a urn and then k Red balls at the sequent extraction
I'm struggling with a quite basic probability problem, and my knowledge in this field is not very deep, so I would appreciate some help. Here is the problem.
Problem formulation
We have some balls in ...
- 11
5
votes
3
answers
81
views
How do you calculate combinations with fractions (eg, "$\frac13$ choose $2$")? [closed]
I was given "$\frac13$ choose $2$" and asked to compute. I checked the answer and it's $-\frac19$, but I have no clue how to arrive at this answer.
How do you deal with fractions in the ...
- 59
1
vote
3
answers
64
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 ...
user1052435
0
votes
0
answers
18
views
Upper bound on a binomial sum
Consider the following binomial series.
\begin{equation}
\frac{1}{2^{n}a^{n}}\sum_{i=0}^{k}{{n}\choose{i}} a^{i},
\end{equation}
where $k = n - \text{poly}(\log n),$ and $a > 1$ is a constant.
I am ...
- 481
1
vote
1
answer
42
views
proving an inequality based on double products and binomial
Iv been trying to prove the following inequality: let $a_1,\ldots,a_n$ be a non-increasing sequence, i.e., $a_1\geq a_2\geq \cdots \geq a_n\geq 0$ such that $\sum_i a_i=m$. Then, prove that
$$\prod_{i=...
- 524
1
vote
1
answer
43
views
Proving a combinatorial identity related to convolution of central binomial coefficients
I'm trying to calculate the coefficient values for $f(x) = \sum_{k=0}^n {n \choose k}^2 (1+x)^{2n-2k}(1-x)^{2k}$. TL;DR I don't know where to begin in order to prove:
$$\sum_{k=0}^r (-4)^k{n \choose k}...
- 23
0
votes
2
answers
39
views
A different upper bound for the binomial coefficient
I need to prove the following statement:
If $3\leq k < t$ then
\begin{equation*}
\binom{t}{k} < 2^{t-1}-k+1.
\end{equation*}
I was given the hint to prove it by induction over $t$ with $k$ ...
- 13
0
votes
0
answers
40
views
How do I prove this binomial identity by just using symmetric property and reversing the upper index?
$$
\sum_k\binom{l}{m+k}\binom{s+k}{n}(-1)^k=(-1)^{l+m}\binom{s-m}{n-l},l\ge0,\{l,n,m\}\subset\mathbb{N},\{s\}\subset \mathbb{R}
$$
P.S.
Please use these identities below to prove it
Symmetric ...
- 1
0
votes
1
answer
30
views
How is the diagonal constraint in lattice path needed for the Catalan proofs?
I have been reading about the Catalan numbers and how they are they appear in many problems such as:
lattice paths
valid pair of parenthesis
mountains with up/downstrokes
non-crossing handshakes
...
- 1,507
2
votes
0
answers
42
views
Sum of factorials in 3D symmetrical random walk $\sum_{k=0}^n\binom{n}{k}^2\binom{2(n-k)}{n-k}$
I'm trying to prove that in a tridimensional symmetrical random walk all states are transient. Since it's an irreducible Markov chain, I only have to prove it for a generic state, since they are all ...
- 162
0
votes
0
answers
26
views
Order of $m+1$ in the multiplicative group of integers modulo $n$
I'm trying to figure out in what cases of $n$ and $m$ the following isomorphism holds.
$$
\mathbb{Z}_n^\times/\left<1+m\right>\cong\mathbb{Z}_m^\times
$$
I'm considering the restriction that $n$ ...
- 211
0
votes
1
answer
31
views
Simplifying $(x-1)\cdot(x-3)\cdots (x-(n-2))$ in terms of binomial coefficients.
Can we write the following product in terms of binomial coefficients ?
$(x-1)\cdot(x-3)\cdots (x-(n-2))$.
i.e the the product take up odd numbers.
- 3
2
votes
1
answer
112
views
Why are the catalan numbers giving the unique/correct patterns from all the combinations?
I am reading about catalan numbers and they are considered to represent the number of valid pair of parentesis, mountains etc.
Although the number checks out correct when comparing against specific ...
- 1,507
0
votes
1
answer
39
views
How do we handle the factorials in the binomials/choice numbers?
Apparently the following is a known equality:
$\frac{1}{n + 1} {2n \choose n} = \frac{2n!}{n!(n + 1)!} = \frac{1}{2n + 1}{2n + 1 \choose n}$
but I can't really figure out how to produce the equality.
...
- 1,507
0
votes
0
answers
17
views
Show that $\binom{r}{k}(p-\frac{k}{n})^k(q-\frac{(r-k)}{n})^{r-k} < q_k < \binom{r}{k}p^kq^{r-k}(1-\frac{r}{n})^{-r}$
Show that $$\binom{r}{k}\left(p-\frac{k}{n}\right)^k\left(q-\frac{r-k}{n}\right)^{r-k} < q_k < \binom{r}{k}p^kq^{r-k}\left(1-\frac{r}{n}\right)^{-r}$$
$q_k$ is given by $$\begin{align}q_k&=\...
- 123
0
votes
1
answer
78
views
The lower bound about the binomial coefficient
From easy computation we can get
\begin{align*}
{n\choose{\ell}}=\frac{n}{\ell}\cdot\frac{n-1}{\ell-1}\cdots\frac{n-(\ell-1)}{1}\geq\frac{n^{\ell}}{\ell^{\ell}},
\end{align*}
where the last inequality ...
- 1,396
22
votes
0
answers
602
views
A curious identity on $q$-binomial coefficients
Let's first recall some notations:
The $q$-Pochhammer symbol is defined as
$$(x)_n = (x;q)_n := \prod_{0\leq l\leq n-1}(1-q^l x).$$
The $q$-binomial coefficient (also known as the Gaussian binomial ...
- 2,865
2
votes
1
answer
38
views
Prove that each number $a$ in a Pascal's triangle decreased by $1$ is equal to the sum of the numbers within the parallelogram bounded by the sides of
Prove that each number $a$ in a Pascal's triangle decreased by $1$ is equal to the sum of the numbers within the parallelogram bounded by the sides of the triangle and the diagonalsgoing through $a$ (...
- 539
1
vote
0
answers
30
views
Existing summation approach for computation of combination?
Recently, I bumped into an interesting approach to alternately calculate the combinations. But I am not sure if there is such theory already existing for generic combinations with arbitrary factorials....
- 613
0
votes
1
answer
36
views
Arithmetic triangle and choices
In regards to the arithmetic triangle:
1
1 1
1 2 1 etc
we know that it is a way to calculate the binomial coefficients or number of choices $C(n,r)$.
...
- 1,507
0
votes
1
answer
53
views
Triangle of Fibonacci
I was reading in a book a presentation about the arithmetic triangle of Fibonacci (to me it also looks like the pascal triangle).
The figure presented is as follows:
The text says:
Having arranged ...
- 1,507
0
votes
0
answers
50
views
Show that $\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n$ [duplicate]
I am trying to show that $$\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n.$$
I try $n=0$:
$$
\sum_{k=0}^0 2^{-k}{k+n \choose k}=2^0{0 \choose 0}=1=2^0,
$$
and $n=1$:
$$
\sum_{k=0}^1 2^{-k}{k+n \choose k}=1+ 2^...
- 1,008
0
votes
2
answers
50
views
Probability of 2 specific people ending up in a random group of 3 people?
18 people are being randomly selected into groups of 3. Bob and Alice want to know the chance that they would be selected to be in the group together. My first thought was to find all groups where ...
- 113
2
votes
1
answer
80
views
Show that $\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}$
I am trying to show that $$\sum_{k=1}^nk {n \choose 2k+1}=(n-2)2^{n-3}.$$ When approaching these types of problems I always try to compute a few small, specific values myself just to get a better ...
- 1,008
0
votes
0
answers
74
views
Given $n\geq 0, j\geq 1.$ How many solutions to: $\sum_{i=1}^j x_i=n,$ where $x_i\geq 0$ and $x_i$ are all different?
Given $n\in\mathbb{N}\cup\{0\},\ j\in\mathbb{N}.$ How many solutions are there to: $\sum_{i=1}^j x_i=n,$ where $x_i\in\mathbb{N}\cup\{0\}$ for all $i\in\{1,\ldots,j\}$ and $x_k\neq x_l$ if $k\neq l\ ?$...
- 12k
0
votes
2
answers
57
views
Can this Sum be reduced? It is calculating the expected value of a poker hand when you "Run it multiple times" for the last card.
There is a scenario in poker (Texas Hold'em) where if two players go "all in", they have the option to deal the remaining cards multiple times and it results in multiple pots that they could ...
- 103
0
votes
0
answers
29
views
Expansion of factorial as linear combination of binomial coefficients [duplicate]
Let $k \leq n$ be positive integers. I would like a proof of the following identity:
$$
n!=\sum_{k=0}^n \binom{n}{k} (-1)^{n-k} k^n.
$$
EDIT: For context, I am using this to verify the below ...
- 433
6
votes
1
answer
178
views
Are there any simple simplifications of $\sum_{n=k}^N \binom{n}{k}^2$?
As the title states, is there any simplification to $\sum\limits_{n=k}^N \binom{n}{k}^2$? I found this which sums the squares of the "rows" of a pascal triangle, but here I'm trying to sum ...
- 1,731
2
votes
1
answer
50
views
If $(1+x+x^2)^n=a_0+a_1x+a_2x^2+\dots+a_{2n}x^{2n}$ then prove that $a_0^2-a_1^2+a_2^2-a_3^2+\dots+(-1)^{n-1}a_{n-1}^2=\frac12a_n(1-(-1)^na_n)$
If $(1+x+x^2)^n=a_0+a_1x+a_2x^2+\dots+a_{2n}x^{2n}$ then prove that $a_0^2-a_1^2+a_2^2-a_3^2+\dots+(-1)^{n-1}a_{n-1}^2=\frac12a_n(1-(-1)^na_n)$
My Attempt:
Replacing $x$ by $-x$ in the given ...
- 5,256