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)

18
votes
6answers
605 views

How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?

How do I prove the following identity directly? $$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$ I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized ...
-1
votes
1answer
52 views

Formula issues when working out chances of getting certain marks [duplicate]

$$P(X = k) = \binom{N}{k} (0.5)^k (0.5)^{N-k} = \binom{N}{k} (0.5)^N$$ Using formula above, I have got the following results for chances for getting certain percentage on a $50$ question paper, each ...
0
votes
3answers
217 views

How to correctly write a binomial distribution for a $50$ questions exam [duplicate]

Using binomial distribution I want to know what is the chance of getting $70\%$ or greater in a $50$ question exam, each question having a true/false option to select from. What is the correct formula ...
1
vote
1answer
387 views

Sum of the first k binomial coefficients for fixed n

I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos. Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} ...
1
vote
2answers
527 views

Probability of getting >70% in exam with 50 yes/no questions

In a paper containing 50 yes/no questions, I am trying to find the probability of getting 70%. Using binomial distribution, $$P(X\ge70\%)=\sum_{k=25}^{50} \binom{50}{k}\left(\frac{1}{2}\right)^{50}$$ ...
16
votes
4answers
567 views

Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$

How can we prove that $$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$ where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$. This inequality is very interesting. I ...
0
votes
1answer
4k views

Probability generating function of the negative binomial distribution.

I am using the definition of the negative binomial distribution from here. This is the same definition that Matlab uses. For convenience, $$P(k) = {r + k -1 \choose k}p^r(1-p)^k ,$$ where $p$ is ...
37
votes
3answers
1k views

Solutions to $\binom{n}{5} = 2 \binom{m}{5}$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says: On National Public Radio, the Weekend Edition program posed the following probability problem: Given a certain number of ...
1
vote
0answers
49 views

is this binomial distribution correct?

I am trying to work out what is the chances of getting the following marks $(100\%, 70\%, 60\%, 50\%)$ in a paper containing $50$ questions, each question containing yes/no options. Using Binomial ...
0
votes
1answer
153 views

Are binomial distribution answers expressed as percentages?

I have a question on an answer to a binomial distribution question. The chances of getting $100\%$ in a test is $8.881784197 \cdot 10^{-16}$. Is that actually a percentage? Making it ...
2
votes
3answers
2k views

Binomial coefficients (1/2, k)

I don't understand questions that involve a binomial expression where you have a fraction choose k or a negative number choose k. I understand and am able to do it when there are no fractions and they ...
0
votes
1answer
81 views

Sample size for Wilsons confidence interval

Consider a story ranking website in which the ranking is crowd sourced from the number of up votes and down votes received by a story. The score is computed as the lower bound Wilson's algorithm. ...
1
vote
3answers
327 views

Sum of the series $\sum_{k=0}^{r}(-1)^k.(k+1).(k+2).\binom{n}{r-k} $

for $n>3$, The sum of the series $\displaystyle \sum_{k=0}^{r}(-1)^k.(k+1).(k+2).\binom{n}{r-k} = $ where $\displaystyle \binom{n}{r} = \frac{n!}{r!.(n-r)!}$ My try:: I have expand the ...
1
vote
2answers
263 views

Prove that $\sum\limits_{i=1}^n 2i\binom{2n}{n-i}= n\binom{2n}{n}$

Let n be a positive integer. Prove that $$\sum_{i=1}^n 2i\binom{2n}{n-i}= n\binom{2n}{n}$$
21
votes
1answer
688 views

A Combinatorial Proof of Dixon's Identity

Dixon's Identity states: $$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c} {a,b,c}$$ A bit of history: The case $a=b=c$ was proved by Dixon in 1891 using ...
2
votes
5answers
2k views

Vandermonde's Identity : Summations with binomial coefficients

(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross. Can someone help me solve this equation? How to prove that ...
1
vote
3answers
86 views

Simplify the Expression $\sum _{ k=0 }^{ n }{ \binom{n}{k}}i^{k}3^{k-n} $

I should simplify the following expression (for a complex number): $$\sum _{ k=0 }^{ n }{ \binom{n}{k}}i^{k}3^{k-n} $$ The solution is $(i+\frac{1}{3})^n$,but i don't quite get the steps. If would be ...
2
votes
0answers
41 views

Characterization of $\lambda,\mu\vdash n$ for which $\displaystyle{n\choose\mu}\mid{n\choose\lambda}$

In view of this question, I was wondering about general characterizations of $\mu,\lambda\vdash n$ for which $${n\choose\mu}\,\left|\,{n\choose\lambda}\right.,$$ (see multinomial coefficient and ...
0
votes
1answer
26 views

Number of partitions of positive integer $k$ into $f$ non zero integers

In statistical physics my teacher said me the no of partitions of a positive integer $k$ into $f$ partitions is same as no of ways arranging $f$ gaps on a total of $(k+f)$ sites (equals to ...
8
votes
1answer
307 views

Vandermonde identity in a ring

Let $R$ be a commutative $\mathbb{Q}$-algebra. For $r \in R$ and $n \in \mathbb{N}$ we can define the binomial coefficient $\binom{r}{n}$ as usual by $\binom{r}{0}=1$ and ...
6
votes
3answers
312 views

How many solutions are possible to this equation?

Given $$A+2B+3C=N $$ where $N$ is a given positive integer. $A ,B,C\in\mathbb{N}$ vary from $0$ to $\infty$. How many solutions will be there to this equation?
1
vote
1answer
150 views

Bernstein Polynomials and Expected Value

The first equation in this paper http://www.emis.de/journals/BAMV/conten/vol10/jopalagzyl.pdf is: $$\displaystyle B_nf(x)=\sum_{i=0}^{n}\binom{n}{i}x^i(1-x)^{n-i}f\left(\frac{i}{n}\right)=\mathbb E ...
9
votes
1answer
147 views

Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)

I know that $$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$ Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
2
votes
3answers
122 views

Combinatoric Explanation of General Identity

When $k \lt n$, what is the value of the sum $$\sum\limits_{j=0}^n {n \choose j}(-1)^j (n-j)^k.$$ Explain combinatorially. Any ideas on where to start?
0
votes
1answer
74 views

What is the probability of drawing kings

A hand H of 5 cards is chosen randomly from a standard deck of 52. Let $E_1$ be the event that H has at least one King and let $E_2$ be the event that H has at least 2 Kings. What is the conditional ...
0
votes
2answers
114 views

Sum with binomial coefficients and fraction

Is there a closed form known for $$ \phi(n,a,c)=\sum_{k=0}^n \binom{n}{k} a^k \frac{1}{k+c} $$ where $a <0$, $c>0$ and $n \in \mathbb{N}$? I know the answer for two special cases: $$ ...
11
votes
3answers
315 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
1
vote
1answer
37 views

how to get a binomial from a summation

An urn contains 6 Red balls and 1 Blue ball. A fair die having faces f1;2;3;4;5;6g is rolled. If the top face on the die shows m, then m random balls are removed from the urn. What is the expected ...
0
votes
2answers
39 views

Relation between binomials

how can I prove that the following relation is true: $$\binom{x-2}y+2\binom{x-2}{y-1}+\binom{x-2}{y-2}=\binom{x}y$$ Thank you for hints or references! Marted
10
votes
1answer
153 views

Can this product be written so that symmetry is manifest?

Let $i,$ $j,$ $k$ be nonnegative integers such that $i+j+k$ is even. The expression $$(-1)^{j+k}\binom{i+j+k}{i,j,k}\prod_{\ell=0}^{k-1} \frac{i-j+k-2\ell-1}{i+j+k-2\ell-1}$$ apparently computes the ...
6
votes
1answer
470 views

How to compute the sum of every $k$-th binomial coefficient?

My teacher was discussing binomial expansions of $(1 + x)^n$ and he gave as an interesting example with $x = i$ whereby you could obtain the sum of all the odd coefficients ($C_n^1+ C_n^3+ C_n^5 ...$) ...
2
votes
1answer
115 views

Theta asymptotic for $\binom{2m}{m}$ [duplicate]

Show that $\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right)$ without using Stirling's approximation.
2
votes
2answers
75 views

Calculating an “at least” probability without summation?

I know One can calculate the probability of getting at least $k$ successes in $n$ tries by summation: $$\sum_{i=k}^{n} {n \choose i}p^i(1-p)^{n-i}$$ However, is there a known way to calculate such ...
11
votes
7answers
534 views

Summation simplification $\sum_{k=0}^{n} \binom{2n}{k}^2$

$\sum_{k=0}^{n} \binom{2n}{k}^2$ So i'm trying to simplify this one and I'm stuck in nowhere. Some kind of tip would be appreciated. Thanks! :)
5
votes
2answers
928 views

Why does the $n$-th power of a Jordan matrix involve the binomial coefficient?

I've searched a lot for a simple explanation of this. Given a Jordan block $J_k(\lambda)$, its $n$-th power is: $$ J_k(\lambda)^n = \begin{bmatrix} \lambda^n & \binom{n}{1}\lambda^{n-1} & ...
7
votes
1answer
237 views

$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof

Is there a simple combinatorial proof for the following identity? $$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.
0
votes
2answers
216 views

How to show $\binom{2p}{p} \equiv 2\pmod p$?

how to prove $\forall p$ prime : $\binom{2p}{p} \equiv 2 \pmod p$ we have: $\binom{2p}{p} = \frac{2p (2p-1)(2p-3)...1}{p!p!}$ but how to continue?
0
votes
1answer
322 views

Using the general binomial theorem to find a series-like expression for $\sqrt 2$

How do I use the general binomial theorem (i.e. the series expansion of ${(1+x)^\alpha}$ for $ |x|<1$) to show the following? $$\sqrt 2=1+\frac 1{2^2}+\frac{1\cdot3}{2!\cdot{2^4}} ...
2
votes
2answers
173 views

Stirling's Approximation

A sharp Stirling's approximation form states that $$n! \sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}.$$ Use that form to show that: $$\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right).$$
1
vote
1answer
74 views

Prove the following identity combinatorially

Prove the following identity combinatorially $$\left(\begin{array}{c} \left(\begin{array}{c} n \\ 2 \end{array}\right) \\ 2 \end{array}\right) = 3 \left(\begin{array}{c} n \\ 4 \end{array}\right) + ...
0
votes
2answers
1k views

Why is $C(n + r − 1, r) = C(n + r − 1, n − 1)$, specifically why is $r$ equivalent to $n-1$?

I have this theorem in my discrete math textbook: There are $C(n + r − 1, r) = C(n + r − 1, n − 1)$ r-combinations from a set with n elements when repetition of elements is allowed. I can't figure ...
4
votes
2answers
926 views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
1
vote
1answer
636 views

Arrangements with No Two Vowels Consecutive

In general we state that there are ${r-wn - (n-1) \choose (n-1)}$ ways to distribute r identical balls in n distinct boxes with at least w balls in each box. Considering this, how many ways are there ...
8
votes
2answers
4k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
3
votes
2answers
103 views

How to get the sum of the values in a $N \times N$ table?

How to get the sum of the values in a $N \times N$ table (without adding repeating products such as $6 \times 7$ and $7 \times 6$ twice and without counting perfect squares)? Figured out that $1 ...
3
votes
1answer
171 views

Choosing k Multisets from [n]

We are to play a lottery game where five numbers are drawn out of [90], but the numbers drawn are put back into the basket right after being selected. To win the jackpot, one must have played the same ...
1
vote
3answers
279 views

Prove: If $n=2^k-1$, then $\binom{n}{i}$ is odd for $0\leq i\leq n$

Kinda stuck on this one. Help is appreciated. I'm going for either a direct or contrapositive proof. Prove: If $n=2^k-1$, for $k\in\mathbb{N}$, then every entry in Row $n$ of Pascal's Triangle is ...
6
votes
2answers
222 views

Wanted: Insight into formula involving binomial coefficients

There is the formula $$\sum_i (-1)^i\binom{a}{k+i}\binom{l+i}{b} = (-1)^{a+k} \binom{l-k}{b-a}.$$ Only finitely many summands are non-zero (those for $i\in\{b-l,\ldots,a-k\}$), so the sum is finite. ...
1
vote
2answers
423 views

Binomial theorem, prove an expression

Forgive me guys, i don't really know how to edit this so it would look like 'maths' but i really don't understand what this is asking me to do -_- Use the Binomial Theorem to show that: $$ 0 = ...
0
votes
1answer
93 views

$l^{th}$ factorial bound

Show that $$n^{(l)}=n(n-1)\dots(n-l+1)\ge {n^l\over e}$$ where $2\le l \le \sqrt{n}$ Here is how far I've got with this: $$n^{(l)}=\prod_{i=0}^{l-1}(n-i)=n^l\prod_{i=1}^{l-1}(1-{i\over n})\\ \ge n^l ...