Questions tagged [binomial-coefficients]
Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
4,846 questions
4
votes
0answers
39 views
New results on Identical Binomial Coefficient?
Are there any nontrivial identical binomial coefficients found other than:
$$ {16 \choose 2}={10 \choose 3}=120 \\ {21 \choose 2}={10 \choose 4}=210 \\ {56 \choose 2}={22 \choose 3}=1540 \\ {120 \...
4
votes
1answer
37 views
Combinatorial proof for $\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$
I am trying to give a combinatorial proof for: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$
Where $p$ and $n$ are natural numbers.
We could easily see that if $p=n$ this reduces ...
2
votes
3answers
37 views
$\sum_{m=0}^N \frac{1}{m+1}{N\choose m}p^m (1-p)^{N-m}=\frac{1-(1-p)^{N+1}}{(N+1)p}$
While reading a journal article, I noticed an equation which looked like the sum of the average binomial coefficient.
But, I have no idea how equation was derived.
$$\sum_{m=0}^N \frac{1}{m+1}{N\...
0
votes
0answers
17 views
Issue w/ extracting coefficients from generating function using IDTFT
This q will make use of these 3 DTFT pairs...
$$
\require{extpfeil}\Newextarrow{\xleftrightarrow}{15,15}{0x2194}
\begin{array}{rcl}
\alpha x_1[n] + \beta x_2[n] & \xleftrightarrow{\mathscr{F}} &...
0
votes
1answer
18 views
Sum of dependent Binomial distributions
In one of my classes, we stated that if $X_i$ are independent Bernoulli random variables with p proportion of success, then the distribution of the sum $\sum X_i$ is Binomial(n,p). I already proved ...
0
votes
1answer
24 views
Find the summation of given expression
I am trying to solve the following question which is Ex3 from Arthur Engel, Problem Solving strategies. Here is the question: $\sum_{k=1}^n k^3 {n \choose k}$ and asks to find the sum. I am sincerely ...
4
votes
2answers
62 views
Estimating $\sum\limits_{d\mid n}{d+a\choose b}$
Is there any way of estimating a sum like
$$\sum_{d\mid n}{d+a\choose b},$$
for positive integers $a$ and $b$? For example, in the OEIS we find that
$$\begin{align*}
\sum_{d\mid n}{d+1\choose 2}
&...
-1
votes
1answer
29 views
Prove that the binomial coefficient is composite [on hold]
Let $n > 3$ and $k$ be integers, with $1 < k < n-1$. Prove that the binomial coefficient is composite.
2
votes
2answers
47 views
Generating function of binomial coefficients
We want to evaluate the sum $$\sum_{L=0}^{\infty}\frac{1}{2}L(L+1)x^L$$
From this set of notes (page 2, equation 8) we find the formula $$\sum_{n=0}^{\infty}\binom{n}{k}y^n = \frac{y^n}{(1-y)^{n+1}}$$...
1
vote
1answer
44 views
Is my proof of $\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + … + \binom{m}{r}\binom{n}{0}$ right?
As the title says, I was requested to prove
$\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + ... +\binom{m}{r}\binom{n}{0}$
I was requested to do this using the following ...
4
votes
3answers
97 views
Help on proof of $\binom{n}{0}^2 + \binom{n}{1}^2 + … + \binom{n}{n}^2 = \binom{2n}{n}$
The proof is required to be made through the binomial theorem. I will expose the demonstration I was tought, and forward my questions after exposing it. You'll see question marks like this one (?-n) ...
2
votes
1answer
33 views
Proving $\binom{2n}{n} + \binom{2n}{n+1}= \frac{1}{2} \binom{2n+2}{n+1}$ using a combinatorial argument
I have to prove $\binom{2n}{n} + \binom{2n}{n+1}= \frac{1}{2} \binom{2n+2}{n+1}$
using a combinatoric argument.
My work: on the LHS I can see that I can interpret the first two terms as choosing the ...
1
vote
2answers
48 views
Sum of alternating binomial-coefficient-type series
Let $D,n\in \mathbb N$ with $0<D<n$, and $y>0$ is a real number.
Question: Is there a closed-form for the following alternating sequence
\begin{equation}
\sum_{k=0}^D (-y)^k {n\choose k}?
\...
-1
votes
0answers
56 views
Closed form for $\sum_{j=t}^{2t}\sum_{k=0}^{t}{2t \choose t}{t\choose k}{j \choose k}{k \choose j-t}\cdots$ [closed]
We manage to figure the closed form for this sum $(1)$
$t\ge2$
$$\sum_{j=t}^{2t}\sum_{k=0}^{t}{2t \choose t}{t\choose k}{j \choose k}{k \choose j-t}\frac{j^2(-1)^j}{(t+1)(2k-1)(2j-2k-1)}=3\cdot2^{2t-...
1
vote
0answers
84 views
Summing Up Binomial Coefficients [duplicate]
$$
\frac{\sum_{r=0}^{24}\binom{100}{4r}\binom{100}{4r+2}}{\sum_{r=1}^{25}\binom{200}{8r-6}}
$$
I tried this problem using Complex number approach and arrived at the solution. When I tried the ...
3
votes
3answers
66 views
Find the binomial coefificient of $x^8$ in $(1+x^2-x^3)^9$
I was trying to solve it using the multinomial theorem.
I was trying to find which combinations could give me such $x^8$
and I came to the conclusion that it only occours when i take
$(x^2)^4$ or $(...
0
votes
1answer
25 views
Proof using a binomial coefficient
Given that a, b, c ∈ N and a ≥ b ≥ c, prove that $\binom{a}{c}\binom{a-c}{b-c}=\binom{a}{b}\binom{b}{c}$.
To start, we know that $\binom{a}{c} = \frac{a!}{c!(a-c!)}=\frac{a!}{(a-c!)c!}=\binom{a}{a-c}$...
3
votes
2answers
103 views
Closed form for $\sum_{j=0}^{n}{n \choose j}{j \choose \lfloor \frac{j}{2}\rfloor}a^{n-j}$ [on hold]
Where $\lfloor \rfloor$; floor function
Consider this sum $(1)$,
$a\ge2$
$$\sum_{j=0}^{n}{n \choose j}{j \choose \lfloor \frac{j}{2}\rfloor}a^{n-j}=F(n,a)\tag1$$
We manage to figure out the sum ...
0
votes
2answers
37 views
Are there ‘product expressions’ for sequences of binomial coefficients similar to the ‘product expression’ for the central binomial coefficients?
If we want a central binomial coefficient, for n greater than zero we have a ‘nice’ expression $${2n \choose n} =\prod_{k=1}^{n}{(4-\frac{2}{k})}$$ which is term-wise rational and produces each ...
0
votes
0answers
65 views
What is $\sum_{k=1}^m\left[2^k\begin{pmatrix} n \\ k \end{pmatrix}\right]^2$?
The equations
$$ \sum_{k=1}^m\begin{pmatrix} n \\ k \end{pmatrix}^2 \quad \text{and} \quad \sum_{k=1}^m\left[2^k\begin{pmatrix} n \\ k \end{pmatrix}\right]^2$$
popped up in some of my calculations, ...
2
votes
2answers
45 views
What is $a_0+a_2+ \cdots+a_{20}$ if $(1-x+x^2)^{10}=a_0+a_1x+\cdots+a_{20}x^{20}$?
$$(1-x+x^2)^{10}=a_0+a_1\cdot x +a_2\cdot x^2 + a_3\cdot x^3 + \cdots + a_{20}\cdot x^{20}$$
$$\implies a_0 + a_2 +a_4 +a_6 + \cdots+ a_{18} + a_{20}=?$$
I know how to expand binomials of $(a+b)^...
0
votes
1answer
12 views
$p^\alpha Cj$ is divisible by $p$
Let $p$ be a prime. For $1\leq j \leq p^\alpha -1$, the binomial coefficient $p^\alpha Cj$ is divisible by $p$.
How?
I know that for $\alpha=1$ the result is true.But how can we generalize it?
0
votes
0answers
15 views
An odd-power identity involving convolution - reference request
Let be a power function $f_{r,M}(s)$ defined for every $s$ within the finite set $M$ as follows
$$
f_{r,M}(s)=
\begin{cases}
s^r, \ &s\in M,\\
0, \ &\mathrm{otherwise}.
\end{cases}
$$
Let a ...
0
votes
2answers
60 views
Bessel function identity
I was trying to find this identity of Bessel function
$$e^{-2i\gamma t} J_{\left|n\right|}(2\gamma t) = e^{\large \frac{\pi i}{2}} \sum_{k=|n|}^{\infty} \frac{(-i\gamma t)^k}{k!}\binom{2k}{k-n}$$
on ...
5
votes
5answers
305 views
Quickest way to find $a^5+b^5+c^5$ given that $a+b+c=1$, $a^2+b^2+c^2=2$ and $a^3+b^3+c^3=3$
$$\text{If}\ \cases{a+b+c=1 \\ a^2+b^2+c^2=2 \\a^3+b^3+c^3=3}
\text{then}\ a^5+b^5+c^5= \ ?$$
A YouTuber solved this problem recently and, though he spent some time explaining it, took over 40 ...
0
votes
1answer
40 views
In how many ways can 6 children be divided into 3 pairs if the order of pairs does not matter?
In how many ways can $6$ children be divided into $3$ pairs if the order of pairs does not matter?
In my book, the answer is only :
$$\frac{^6C_2\cdot^4C_2\cdot^2C_2}{3!}=\frac{1}{6}\cdot90=15$$
I ...
1
vote
1answer
21 views
What is the probability of getting two pair (ex: two 3's, two 7's and a ace) from a random 5 card poker hand?
I know this question has been asked several times. But I appraoched the problem in a different way and it leads me to a different answer. My apprach is as follows:
$$
\frac{\binom{13}{3}\binom{4}{2}\...
1
vote
1answer
57 views
How can I find the sum of squares of binomial coefficient and fibonacci numbers $ \sum_{k=0}^{n} \left[ \binom{n}{k}F_k \right]^2 $
In this topic (Binomial coefficient and fibonacci numbers), it can be easily seen the sum of binomial coefficient and fibonacci numbers is
$$
\sum_{k=0}^{n} \binom{n}{k}F_k = F_{2n}.
$$
I have also ...
-2
votes
1answer
40 views
Efficient and accurate approximatiion of logarithm of binomial coefficients
I am searching for an efficient and accurate way to approximate the logarithm of binomial coefficients since I have to deal with extremely large numbers in C++. Using Stirling approximation, I am able ...
3
votes
3answers
81 views
Simplify the sum $ \sum_{i=0}^{k}(-1)^i i \binom{n}{i} \binom{n}{k-i}$
How to deal with combinatoric interpretation (or just solving it in algebraic way) when we have $(-1)^i$ factor in our sum?
Example task:
Simplify the sum:
$$ \sum_{i=0}^{k}(-1)^i i \binom{n}{i} \...
2
votes
3answers
81 views
Prove that $x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$
Prove that for every $x,n \in \mathbb{N}$ holds
$$x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$$
This is so called MacMillan Double Binomial Sum, see Mathworld - Power, ...
1
vote
1answer
89 views
Are there any power identities which don't belong to this list?
The problem of finding expansions of monomials, binomials etc. is classical and there is a lot of beautiful solutions have been found already, the most prominent examples are
Binomial Theorem, ...
3
votes
2answers
78 views
If $C_0, C_1, C_2, .., C_n$ are the binomial coefficients in the expansion of $(1+x)^n$
If $C_0, C_1, C_2,...,C_n$ are the binomial coefficients in the expansion of $(1+x)^n$, prove that:
$$C_{r}.C_{n} + C_{r+1}.C_{n-1} +......+ C_{n}.C_{r} = C(2n, n+r) =\dfrac {(2n)!}{(n-r)! (n+r)!}$$
...
0
votes
1answer
20 views
Find the coefficient of a term in the expansion of an algebraic expression
The coefficient of $x^3$ in the expansion of (1 + 2$x$ + 3$x^2$)$^6$ is equal to twice the coefficient of $x^4$ in the expansion of $(1 - a x^2)^5$.
Find all possible value of constant $a$.
I am ...
0
votes
2answers
71 views
Pascal triangle with more numbers to add
I've found a way to make variants of Pascal's Triangle, by changing the number of values from the previous row to add up.
In this triangle I add three numbers.
...
0
votes
0answers
35 views
Distribute m=17 cards to n=7 entities
Every entity must receive at least 2 cards and all cards have to be distributed. Only the cards and not the entities are distinguishable. My approach was as follows:
Since every entity has to receive ...
3
votes
2answers
77 views
Verify the coefficient of $x^n$ from expansion is $\binom{2n+1}{n}$
So... after 20 years I decided to mess with math again... And I now I feel I am either completely off, or missing a more explicit explanation on this one, can anyone give me a hand?
Verify that the ...
0
votes
0answers
21 views
$\displaystyle {q \choose m} = 0$, for all $m = 1, …, q-1$. [duplicate]
Let $F$ a field with $\operatorname{char}F\mid q$, then $\displaystyle {q \choose m} = 0$, for all $m = 1, ..., q-1$.
Comments: I'm trying to decompose q into product of primes.
1
vote
1answer
22 views
General Leibniz's rule, why cases k=0 and k=n are separated from the sum?
1) Firstly, I don't understand why cases $n=0$ and $k=n$ are seperated from the sum?
2) Then if we put k=1 then why n on the top of the sum symbol still stays the same instead of changing to $n+1$?
...
1
vote
1answer
15 views
Some clarifications about Pascal's rule needed.
I have attached a screenshot of the proof of Pascal's rule and highlighted parts I don't understand.
1) why $(n-(k-1))$ on numerator is without factorial? I understand, that $(n-(k-1))$ is lesser ...
3
votes
1answer
50 views
How do you prove that $\binom{n}{d} = \Theta(n^d)$?
I am stuck on proving that that $\binom{n}{d} = \Theta(n^d)$ for any positive fixed integer d. I tried using the fact that if this is true, it means that for some integers c$_1$ and c$_2$, $c_1n^d \le ...
0
votes
0answers
24 views
Evaluating a sum involving multinomial coefficient
$$S(p,x,y)=\sum_{n=1}^{\infty}(1-p)^{n-1}\sum_{a+b\le n,0\le b<a}\binom{n}{a,b,n-a-b}x^ay^b(1-x-y)^{n-a-b}$$
I am unable to simplify the sum. Mathematica doesn't help either. Any help will be much ...
2
votes
4answers
75 views
coefficient $x ^ n$ in development
The advisor asks to verify that the coefficient of
$$x^n$$
in the development of:
$$(1+x)^{2n}+x(1+x)^{2n−1}+x2(1+x)^{2n−2}+......+x^n(1+x)^n$$
is equal to
$$\binom{2n+1}{n}$$
I tried for summations ...
-2
votes
2answers
60 views
Find the coefficient of $x^n.$ [closed]
How do you recommend that I find the coefficient of $x^n$ given the expansion of
$$(1+x)^{2n}+ x(1+x)^{2n-1} + x^2(1+x)^{2n-2}+ \dots + x^n(1+x)^n?$$
I already tried a few different ways ...
7
votes
1answer
92 views
Combinatorial proof of $\binom{nk}{2}=k\binom{n}{2}+n^2\binom{k}{2}$
This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good ...
1
vote
1answer
34 views
Proof of the following combinatorial identity
Prove
$$\sum_{m\le i\le k-l} \binom{k-i-1}{l-1} \binom{i-1}{m-1} = \binom{k-1}{m+l-1}$$
where $m$, $l$, $i$, $k$ are positive integers and $k\ge m+l$.
Is this related to Vandermonde's identity?
0
votes
1answer
40 views
Binomial equality [closed]
The advisor asks to verify that the coefficient of $$x ^ n$$ in the development of:
$$(1+x)^{2n}+x(1+x)^{2n-1}+x^2(1+x)^{2n-2}+......+x^n(1+x)^n$$
is equal to
$$\binom{2n+1}{n}$$
I tried for ...
1
vote
3answers
71 views
Proving $\sum_{m=0}^n\binom{n}{m}^2 \binom{m}{n-k}=\binom{n}{k}\binom{n+k}{k}$
How can I prove this?
$$\sum_{m=0}^n\binom{n}{m}^2 \binom{m}{n-k}=\binom{n}{k}\binom{n+k}{k}$$
$$ 0\le k \le n $$
I developed the expressions, but they are not the same. I do not know if it will be ...
0
votes
0answers
9 views
probability for maximal result of m randomly generated numbers, solve binomial
I need to solve the following problem:
we generate m random numbers where each: $\forall n, n\in [2,20] $
find the probability function of variable $X$ where $X= max(n_1 , n_2 ...,n_m )$
Now, I ...
0
votes
0answers
25 views
Coefficients for the result of multiplying n different binomials
I have the roots of a n degree polynomial, supossing all of the roots have multiplicity 1, I can get the original polynomial by multiplying the following binomials: $(z-z_0)*(z-z_1)*...*(z-z_n)$ where ...
