Stack Exchange Network

Stack Exchange network consists of 174 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
1answer
39 views

Sum of exponential terms and binomial

I would like to calculate the following expression with large $m$: $$\sum^{m}_{q=1} \frac{(-1)^{q+1}}{q+1} {{m}\choose{q}} e^{-\frac{q}{q+1}\Gamma}.$$ But, due to the binomial, the computer gets ...
3
votes
1answer
41 views

Binomial sum having positive and negative terms

Find $\displaystyle \binom{n}{0}-\binom{n}{1}\frac{1}{4}+\binom{n}{2}\frac{1}{7}+\cdots \cdots $ What I tried: the sum is $$\sum^{n}_{r=0}(-1)^r\binom{n}{r}\frac{1}{3r+1}$$ $$\sum^{n}_{r=0}(-1)^r\...
0
votes
1answer
32 views

Closed-form expression for Poisson-Binomial series

I'm interesting in knowing whether there is a closed-form expression for the following series: $\displaystyle\sum_{n\geq1}\frac{1}{n!}\lambda^n e^{-\lambda} \left[{n \choose k}z^k(1-z)^{n-k} \right] $...
1
vote
3answers
75 views

How can I find the coefficient of $x^6$ in $(1+x+\frac{x^2}{2})^{10}$ efficiently with combinatorics?

To find the coefficient of $x^6$ in $(1+x+\frac{x^2}{2})^{10}$, I used factorization on $(1+x+\frac{x^2}{2})$ to obtain $\frac{((x+(1+i))(x+(1-i)))}{2}$, then simplified the question to finding the ...
2
votes
0answers
24 views

Limit of a ratio of two similar binomial coefficients with two variables

Consider two rational numbers $a, b > 0$. What can be said of the following limit as a function of $a, b$, where $x$ and $y$ are natural numbers? $$ L = \lim_{(x,y)\to\infty}\dfrac{ \...
-4
votes
1answer
28 views

Highest Number of Pascal's Triangle [on hold]

What's the highest number in a Pascal's line if the sixth and fifteenth numbers are equal? a) $48\ 620$ b) $184\ 756$ c) $352\ 716$ d) $92\ 378$
0
votes
3answers
43 views

value of $f(2019)$ in binomial expression

if $\displaystyle f(n)=\mathop{\sum}_{i>j\geq 0}\binom{n+1}{i}\binom{n}{j}.$ Then value of $f(2019)$ is what i try $\displaystyle f(n)=\binom{n+1}{1}\binom{n}{0}+\binom{n+1}{2}\bigg(\binom{n}{0}+\...
2
votes
0answers
22 views

Proof of the orthogonality of a given matrix which involves binomial coefficients

I'm reading a paper (see pages 6 and 7 pf the pdf) which claims that a given $n+1$-dimensional square matrix $C$ is orthogonal. The $kj^{th}$ element of this matrix is given by: $$C_{kj}=2^{-\frac{n}{...
1
vote
0answers
29 views

How is the Combinatorial proof derived? [duplicate]

Could somebody explain how this statement is derived? $${m+1\choose{k+1}} = \sum_{i=0}^{m-k} {k+i\choose{k}}$$ This is similar to $\binom{m+1}{k+1}=\sum_{i=0}^m \binom{i}{k}$ but I am stuck as ...
2
votes
2answers
50 views

How to show ${np\choose p} \equiv n\pmod p$ , where $p$ is prime [duplicate]

Show that ${np\choose p} \equiv n\pmod p$ , where $p$ is prime. I tried using various theorems like Fermat or Wilson but I am unsuccessful until now.
1
vote
0answers
24 views

How to apply binomial theorem for selection of N numbers from 2 sets with size N with non-repeating index [closed]

A=[2,4,6,8,10] B=[1,3,5,7,9] A and B are the two sets having equal number of roots with size of set=N,here N=5 I want to calculate total sum of products for following:: 1] I want to select N elements ...
2
votes
2answers
44 views

Infinite binomial sum

Let $\displaystyle\pi_{lr}\left(p\right) := {l \choose r}p^{r}\left(1 - p\right)^{l - r}\quad$ ( i.e., the binomial probability with parameters $\displaystyle l$ and $\displaystyle r$ ). I'...
0
votes
1answer
38 views

Is this the correct notation for a binomial coefficient? [on hold]

I need to show the number of ways in which a specific pattern of 1s and 0s can occur. An important factor is that they always have to be paired. For example, with n=2 there are 2 combinations: 10, 01 ...
0
votes
1answer
22 views

How to prove $\sum_{1 < k < n}\binom{n-k}{1}\binom{k-1}{t+1} = \binom{n}{t+3}$?

How to prove $\sum_{1 < k < n}\binom{n-k}{1}\binom{k-1}{t+1} = \binom{n}{t+3}$? I encountered this in a book and don't know how they did this. Here $t$ is a constant.
1
vote
2answers
74 views

Prove by induction: $C(2n, 2) = 2C(n, 2) + n^2$

Show that if $n$ is a positive integer, then $C(2n, 2) = 2C(n, 2) + n^2$. Here, $C(a, b)$ means the binomial coefficient $\dbinom{a}{b}$. Prove this by induction. Here is my calculation: $n$ ...
2
votes
2answers
77 views

Rigorous or not?

I want to prove $$T(n,k)=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(T(n-1,k)+T(n-1,k-1))=\binom{n}{k}\binom{n-k}{\left\lfloor\frac{n-k}{2}\right\rfloor}$$ First we know only that $$T(n,k)=0, n&...
1
vote
1answer
64 views

Prove that $4^n>{2n\choose n}$

$(4)^n$> ${2n\choose n}$ I have attempted to prove this by placing it as $(4)^n$=$(1+1)^n$ with another square like $2^{2n},$ since I can't write it properly; then I used the formula for ${2n\choose ...
1
vote
1answer
27 views

Is the following equation valid for a binomial coefficient?

From my notes on the binomial series I deduced a formula for the value of a binomial equation using product notation: $ {n \choose r} = {\frac {\prod_{\lambda=0}^r(n-\lambda)} {r!}}$ I believe this ...
0
votes
2answers
38 views

Summation of hypergeometric probability multiplied by some factor

I am not sure how to prove the following: $$\sum _{s=0}^{k}{\frac {{j\choose k-s}{n-j\choose s}s}{{n\choose k}}}=-{\frac { \left( -n+j \right) k}{n}}$$ I know if the factor $s$ is omitted, the sum ...
3
votes
0answers
73 views

Sum of binomial coefficient with both the upper and lower index being multiple of 4

There is a nice proof on MSE which shows that for $n \ge 1$, $$ \sum_{k = 0}^{n}{4n \choose 4k} = {1 \over 4}\left[\left(-1\right)^{n}\, 2^{2n + 1} + 16^{n}\right] $$ I wonder if there is a more ...
0
votes
0answers
14 views

remainder in double sum having binomial coefficients

find the remainder when $\displaystyle \sum^{2014}_{r=0}\sum^{r}_{k=0}(-1)^k(k+1)(k+2)\binom{2019}{r-k}$ is divided by $64$ what i try $$\sum^{2014}_{r=0}\sum^{r}_{k=0}(-1)^k(k+1)(k+2)\binom{2019}{...
0
votes
2answers
37 views

Simplifying an expression with binomial coefficients and powers of $2$

$$\binom{n}{0} \cdot 2^n + \binom{n}{1} \cdot 2^{n-1} + \binom{n}{2} \cdot 2^{n-2} + \dots + \binom{n}{n} \cdot 2^{n-n}$$ Anyway to simplify this such that it can become of 'closed' form (i.e. a ...
1
vote
2answers
64 views

Formula for partial sum of binoms: $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom nk \binom mk$

I am dealing with some expressions containing combinatoric numbers. Does anybody know a formula for this? $$\displaystyle\sum_{k=0}^{\left\lfloor \dfrac{n}{2} \right\rfloor} \binom{n}{k}\binom{m}{k}$$...
1
vote
1answer
25 views

find the coefficient of the term when the expression is expanded.

$a^2x^3$: $(a + x + c)^2(a + x + d)^3$ I am considering to list all cases of $a^nx^m$ from both expansion that sum of n=2, sum of m=3. Like in the first case: $a^0x^0$ from first expansion and $a^2x^...
1
vote
5answers
36 views

Find the coefficient of x in the expansion of $(2x^2+x-3)^8$.

This is a question from IB past papers. I factorized the equation to (2x+3)(x-1) and I tried finding the coefficients, but I got a wrong answer. Maybe I have forgotten how to solve it. Can someone ...
3
votes
3answers
60 views

How to show $\sum_{i=1}^{\lceil L/2\rceil}\frac{\binom{2i-2}{i-1}}{i}2^{-2i}=1/2-2^{-L-1}\binom{L}{(L-1)/2}$?

By numerical evaluation, it seems that the following identity holds. For any odd positive integer $L$, $$\sum_{i=1}^{\lceil L/2\rceil}\frac{\binom{2i-2}{i-1}}{i}2^{-2i}=1/2-2^{-L-1}\binom{L}{(L-1)/2}.$...
0
votes
1answer
24 views

Inclusion-Exclusion Number of Sets

Derive and prove a general formula for the number of elements which are in an odd number of the sets $A_1,A_2,...,A_n$, written in terms of $|A1|$, $|A2\cap A7|$, $|A3\cap A4\cap A9|$, etc., possibly ...
1
vote
2answers
72 views

Determine the co-efficient of $x^{97}$ in the expansion of $(1-x)^{135}(1+x+x^2)^{135}$.

Determine the co-efficient of $x^{97}$ in the expansion of $(1-x)^{135}(1+x+x^2)^{135}$. I know to use the binomial theorem, but I am having a difficult time simplifying. Any help is appreciated, ...
-1
votes
0answers
39 views

Finding the sum of series that is a combination [duplicate]

I have to find the sum of this combination. Any help please? $$\sum_{k=0}^n \binom{2n}{k}$$
1
vote
1answer
32 views

the value of $\sum^{3m}_{r=0}(-1)^r\binom{6m}{2r}$ is

the value of $\displaystyle \sum^{3m}_{r=0}(-1)^r\binom{6m}{2r}$ is what i try opening sum $$\binom{6m}{0}-\binom{6m}{2}+\binom{6m}{4}-\binom{6m}{6}+\cdots +(-1)^{3m}\binom{6m}{6m}$$ $$(1+x)^{6m}=\...
0
votes
5answers
83 views

Proving Pascal's identity $ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

I'm trying to prove Pascal's identity, no luck so far. I have an answer which seem to include some unexplained shifts that I don't get. What needs to be proved: $$ \binom{n}{k} + \binom{n}{k+1} = \...
-1
votes
2answers
121 views

ratio of binomial expression

sum of expression $$\large\frac{\sum^{r}_{k=0}\binom{n}{k}\binom{n-2k}{r-k}}{\sum^{n}_{k=r}\binom{2k}{2r}\bigg(\frac{3}{4}\bigg)^{n-k}\bigg(\frac{1}{2}\bigg)^{2k-2r}}(n\geq 2r)$$ $(a)\;1/2\;\;\;\;\;\;...
1
vote
2answers
52 views

Is $2\binom{d}{k} \le \binom{2d}{k}$ true?

I am quite certain that $2\binom{d}{k} \le \binom{2d}{k}$ holds for every positive integers $k,d$, where $1 \le k \le d$. Is there a simple proof? A combinatorial proof ? An immediate combinatorial ...
0
votes
1answer
91 views

Sum of series having binomial coefficients [duplicate]

Prove that $\displaystyle \sum_{r=0}^n {n+r\choose r} \frac{1}{2^{r}}= 2^{n}$ what i try $$\binom{n}{n}+\binom{n+1}{1}\frac{1}{2}+\binom{n+2}{2}\frac{1}{2^2}+\binom{n+3}{3}\frac{1}{2^3}+\cdots +\...
1
vote
1answer
36 views

natural number values of $(x,y)$ in binomial coefficients

Find natural number $(x,y)$ in $\displaystyle \frac{x!}{y!(x-y)!}=2019$ what i try $\displaystyle \frac{x!}{y!(x-y)!}=2019=3\cdot 673$ pairs are $(2019,1),(2019,2018)$ How to find other natural ...
0
votes
0answers
43 views

By considering expansions of (1+(1+x))^n and (2+x)^n, show that

(nCr)(rCr) + (nCr+1)(r+1Cr) + (nCr+2)(r+2Cr) + ... + (nCn)(nCr) = (nCr)2^(n-r) I have expanded both initial binomial expansions, but am unsure where to continue from here.
6
votes
2answers
67 views

Is it valid to define $\binom{n}{n+k} = 0$

Is it valid to define $$\binom{n}{n+k} = 0$$ where $k$ is an integer in $\{k < -n\}\cup\{k > n\}$ ? I couldn't find anything on this notation via a quick google search, but I ran into it in ...
3
votes
1answer
84 views

Alternating shifted central binomial sum with Cauchy weights

My question is how can one show that $$\lim_{n \to \infty} \frac{1}{\binom{2n}{n}}\sum_{k=1}^n (-1)^k \binom{2n}{n+k}\frac{x^2}{x^2+\pi^2k^2} = \frac{1}{2}\Big(\frac{x}{\sinh(x)}-1\Big) $$ I find ...
2
votes
0answers
32 views

Parity of some binomial coefficients

Consider for fixed integer $n>1$ the binomial coefficients $\binom{n-1+2^j}{n+1-2^j}$ for $j>0.$ It seems that precisely one of these numbers is odd. Is there a simple proof of this fact?
4
votes
3answers
181 views

Is there a simple combinatoric interpretation of this identity? [duplicate]

I came across an exercise in which we are asked to prove the identity: $${2n\choose n}=\sum_{k=0}^n{n\choose k}^2$$ The exercise gives the hint: $$\left(1+x\right)^{2n}=\left[(1+x)^n\right]^2$$ It'...
-1
votes
1answer
27 views

Inequality in binomial coefficient [closed]

How to prove $$\binom{2n+x}{n} \binom{2n-x}{n} \leq\binom{2n}{n}^2$$ I tried by expanding. But then not able to proceed.
0
votes
0answers
44 views

Proving Pascal's Triangle and Hockey-Stick Identity using Combinatorics [duplicate]

How would I prove the following using a combinatorial proof? (a) Show that this identity is in Pascal's Triangle: $$\sum_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n}, ∀n ∈ \mathbb{N}$$ (b) Prove the ...
1
vote
1answer
59 views

More about odd numbers in Pascal's triangle

Do you have any references to this interesting result? I could not find any... The total number of odd numbers in the first $2^n$ rows of Pascal's triangle is $3^n$, $n>=0$. It's easy to prove by ...
2
votes
1answer
49 views

On the parity of the coefficients of $(x+y)^n$.

The coefficients of $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ are $1$, $3$, $3$ and $1$. They are all odd numbers. Which of the following options has coefficients that are also all odd numbers? $(\text A) \ \...
2
votes
2answers
103 views

Concerning the identity in sums of Binomial coefficients

Let be the following identity $$\sum_{k=1}^{n}\binom{k}{2}=\sum_{k=0}^{n-1}\binom{k+1}{2}=\sum_{k=1}^{n}k(n-k)=\sum_{k=0}^{n-1}k(n-k)=\frac16(n+1)(n-1)n$$ As we can see the partial sums of binomial ...
1
vote
1answer
40 views

Why is this sum simplified to this value?

We need to find the number of pairs $i,j$ such that $1\le i < j \le 90.$ and $j - i > 10$. My approach would be to count the total number of pairs which satisfy the first condition, i.e. $90\...
0
votes
1answer
21 views

Limit of a sum with binomial term, where terms do not add up to 1

I am trying to compute the limit of the following sum involving a binomial term, where $\mu\in[0,1]$ and $\theta\in[0,1]$: $ \displaystyle \lim_{t \to \infty} (1-\mu)(1-\theta) \displaystyle \sum_{r=...
5
votes
2answers
62 views

Show that the cardinal of $ A := \left\{ k \in \mathbf{Z} | 0 \leq k \leq n \text{ and } \binom{n}{k} \text{ is odd} \right\} $ is a power of 2 [duplicate]

Let $ A := \left\{ k \in \mathbf{Z} | 0 \leq k \leq n \text{ and } \binom{n}{k} \text{ is odd} \right\} $. I must show that the cardinal of $A$ is a power of 2. I have tried to show that there ...
1
vote
3answers
60 views

Summation of combination of binomial coefficient

Is there any way to find: $$\sum_{i=0}^n {\binom{n}{i}i^k}$$ I know that we can find it for small k by using binomial theorem by differentiating both sides and then multiplying both sides by x and ...
0
votes
0answers
42 views

Are the path grid problem and Mason's Gain Formula fundamentally interconnected?

While working on a more computationally efficient solution for a path grid problem (according to this formulation: https://www.codeabbey.com/index/task_view/paths-in-the-grid ), I found an interesting ...