Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
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 ...