Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

0
votes
0answers
57 views

Estimation for sum over binomial coefficients

I am trying to show that a certain procedure for resource allocation is approximately efficient. For this I need to show that $$ \lim_{n\rightarrow \infty} \left(\frac{1}{e}\right)^n\sum_{c=2}^n ...
1
vote
3answers
165 views

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean ...
0
votes
7answers
151 views

Calculating $\displaystyle\sum_{i=1}^{n} \binom{i}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
0
votes
1answer
23 views

Strictly increasing maps

For $p\ge n$, how many strictly increasing maps from $N^*_n$ to $N^*_p$ do exist, where $N^*_n = \{1, 2, \dots, n\}$ is the set of the first $n$ integers greater than 0 ? My answer: uncountable many. ...
0
votes
0answers
41 views

Moment generating function with binomial coefficients

I am trying to calculate a moment generating function, and I have obtained the following result: \begin{equation} ...
7
votes
2answers
153 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
3
votes
2answers
114 views

how to prove $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ without induction?

$$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$$ how to prove it without induction? I tried with several way but I failed anybody help me ?
3
votes
2answers
87 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
0
votes
1answer
40 views

Binomial Theorem Identity

Using the binomial theorem, derive the following identity: $\dbinom{n}{0} - \dbinom{n}{1} \frac{1}{2} + \dbinom{n}{2} \frac{1}{4} - ... \pm \dbinom{n}{n} \frac{1}{2^n} = \frac{1}{2^n}$ It is easy to ...
3
votes
0answers
39 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
2
votes
1answer
43 views

Try to solve Binomial Distribution

I just got a problem related to binomial distribution as following. Which value of $k$ makes $\left(\begin{matrix}n \\ k\end{matrix} \right)p^k(1-p)^{n-k}$ as large as possible? I've spend hours ...
1
vote
3answers
63 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
8
votes
2answers
244 views

Computing the last non-zero digit of ${1027 \choose 41}$?

I am working on the following problem: Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + ...
2
votes
1answer
196 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
2
votes
1answer
104 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
3
votes
3answers
120 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
1
vote
1answer
98 views

Least common multiple in binomial expansion

If I sum the terms of a binomial expansion, which would be the least common multiple of all the denominators? Say $\displaystyle \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n}$ ...
3
votes
1answer
105 views

A generalization of the Vandermonde's convolution

I need to find a closed formula for the following sum: \begin{equation} \sum_{i=0}^{n}i^{k}\left(\begin{array}{c} n\\ i \end{array}\right)\left(\begin{array}{c} n^{2}-n\\ c-i \end{array}\right) ...
3
votes
3answers
264 views

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$?

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$? How can we calculate this expression ? I've applied the binomial theorem formula and got $91$ terms but I am not sure if it is right ...
1
vote
1answer
35 views

What is the coefficient of x^9 y^16 in the expansion of (7x+21y)^25

binomial(n, k) x^(n-k) y^k Given newtons binomial theorem. I believe the answer is n = 25 k = 16 ...
0
votes
1answer
24 views

Binomial Coefficients-Squares

A discrete random variable $X$ takes value $0,1,2, \ldots n$ with frequency $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Find the variance. I have calculated the mean as such ...
1
vote
1answer
29 views

Binomial Identity/Coefficient Question

So I know that the coefficient of $[x^n]$ is computed by using: $\left( \sum_{j=0}^n a_j b_{n-j} \right)$ = $[x^n]A(x)B(x)$ How is this formula used to make computations, for example, how do I ...
0
votes
5answers
243 views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
0
votes
2answers
79 views

Prove the identity $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$

I need to prove the following identity: $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$ I know that - $\sum_{k=0}^{n}{n \choose k}2^{k}=3^{n}$ but don't know ...
5
votes
2answers
613 views

Proving $\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}$

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
9
votes
4answers
350 views

Evaluate a finite sum with four factorials

Given positive integers $k, m, n$ such that $1 \leq k \leq m \leq n$. Evaluate $$ \sum^{n}_{i\mathop{=}0}\frac{1}{n+k+i}\cdot\frac{(m+n+i)!}{i!(n-i)!(m+i)!}$$ Any hints? I'm stuck on ...
2
votes
2answers
113 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
0
votes
1answer
80 views

Can this summation be simplified?

I got something like $$ a_{n} = {1 \over 4^{n + 1}}\sum_{k = 0}^{\left\lfloor n/2\right\rfloor} {n + 1 \choose 2k + 1}\left(-3\right)^{k} $$ Could this be simplified more?
2
votes
0answers
87 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
-1
votes
1answer
25 views

Limit of a binomial sequence is Poisson? [closed]

Let X be a sequence of random variables with binomial distribution $\mathcal{B} (n, \lambda /n)$, where $\lambda > 0$. Show that $$ \lim_{n \to \infty} \mathbb{P}[X_n = k] = e^{-\lambda} ...
1
vote
1answer
56 views

A combinatorial identity?

Is there a combinatorial identity for the following: $$\sum_{k=0}^{i}\binom{n}{k} $$ for arbitrary integers $n, i$ with $n > i$? If so, what is this identity called?
-1
votes
1answer
31 views

Binomials (a) 8!/6! (b) 10!/9!

I don't know the exact formula to use for this expansion I have tried to use multiple equations so therefore there must be one you can use.
5
votes
2answers
110 views

Prove that $\sqrt{8}=1+\dfrac34+\dfrac{3\cdot5}{4\cdot8}+\dfrac{3\cdot5\cdot7}{4\cdot8\cdot12}+\ldots$

Prove that $\sqrt{8}=1+\dfrac34+\dfrac{3\cdot5}{4\cdot8}+\dfrac{3\cdot5\cdot7}{4\cdot8\cdot12}+\ldots$ My work: $\sqrt8=\bigg(1-\dfrac12\bigg)^{-\frac32}$ Now, I suppose there is some "binomial ...
1
vote
1answer
42 views

Problem with raising parentheses to powers

Simply math question, lets say I have $(2x^2)^3$.Is this equal to $8x^6 , 2x^5, 2x^6$, or $8x^5$ ? It is a simple problem but what confuses me is do if I multiply the coefficient separately from the ...
2
votes
1answer
59 views

Question about balls in urns

Suppose there are $n$ balls in an urn, and $r$ of them are red. I select $m$ balls from this urn at random. What is the probability that at least $k$ of them are red? $m$ must be less than $n$, but ...
0
votes
2answers
35 views

Get polynomial function from 3 points

I need to understand how to define a polynomial function from 3 given points. Everything I found on the web so far is either too complicated or the reversed way around. (how to get points with a given ...
0
votes
3answers
82 views

Finding the Coefficient of X^9 in (1+x^3+X^8)^10

This is solved by the following approach e1 takes values 0 3 8 e2 takes values 0 3 8 .. .. .. . and finally it is said that we get 9 when we take ai=3.And the answer become 10c3. Can someone ...
4
votes
1answer
64 views

Verification of a Combinatorial Identity

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity? ...
3
votes
2answers
120 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
5
votes
7answers
314 views

If $x+\dfrac{1}{x}=5$, find the value of $x^5+\dfrac{1}{x^5}$.

If $x>0$ and $x+\dfrac{1}{x}=5$, find the value of $x^5+\dfrac{1}{x^5}$. Is there some other way to do find it? $$ \left(x^2+\frac{1}{x^2}\right)\left(x^3+\frac{1}{x^3}\right)=23\cdot 110. $$ ...
1
vote
1answer
94 views

Solving Binomial Coefficients with Double Counting

I have a problem that I am trying to solve two different ways. The problem is: The following equality holds, for a positive integer $n$: $$\dbinom{2n}{2} = 2\dbinom{n}{2} + n^2$$ Show that ...
1
vote
2answers
56 views

To provide a combinatorial argument for a combinatorics equality.

Prove that, $${n \choose m}+2{n-1 \choose m}+\ldots+(n-m+1){m \choose m}={n+2 \choose m+2}$$ My work: I thought it would be better to use combinatorial argument than trying to provide a rigorous ...
0
votes
0answers
36 views

Can this binomial coefficient term be simplified?

Can this be simplified? $$\binom{n}{k}\binom{k}{j}2^{-k}$$ assuming $k \le n$ and $j \le k$? I've tried expanding it in to factorials, but other than a $k!$ term, nothing seems obvious. ...
2
votes
3answers
54 views

$2^n$ choose something

Let $m$ be a positive integer, and let $n=2^m$. Prove that the numbers $$ \binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1} $$ are all even. -Source: ASMP sample problems Counting Strategies number ...
2
votes
2answers
62 views

Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways: I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for ...
1
vote
2answers
150 views

DICE - Rolling at least *k* on *n* six-sided dice - with a twist!

I am putting together a table of dice probabilities for a project I am working on and have found myself intimidated by a little "special case" I'm trying to work with. For determining the probability ...
3
votes
1answer
42 views

Bounding one binomial coefficient with another

For given $n$ and $m$, I am interested in finding an expression for the smallest $r$ such that the following holds: ${r \choose m} \geq \frac{1}{2} {n \choose m}$. Is such an expression, or at least ...
0
votes
1answer
87 views

Closed form of $n!\sum_{k=3}^{n-1}{{n-2}\choose{k-1}}$

$n$ is given, and it takes part in the following formula. $$n!\sum_{k=3}^{n-1}{{n-2}\choose{k-1}}$$ Is there a nicer way for expressing it? Without the summation sign?
3
votes
1answer
121 views

How find this sum of binomial coefficients $\sum_{k=0}^{n}k\binom{n+k}{k}2^k$

How Find this sum $$\sum_{k=0}^{n}k\binom{n+k}{k}2^k$$ My idea: since $$\binom{n+k}{k}k=\dfrac{(n+k)!}{n!(k-1)!}$$ and I have other idea: Consider $$f(x)=\sum_{k=0}^{n}\binom{n+k}{k}x^k$$ then ...
0
votes
1answer
57 views

$n \choose m$ as number of bijections

I saw that my former question came from a certain exercise so I'll just write it down here: It's to proof that the number of $m$-element subsets in an $n$-element set is $n \choose m$. A hint is ...