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)

3
votes
2answers
437 views

German tank problem, simple derivation [duplicate]

I was reading the recent question on the German tank problem, and had trouble with one of the derivations in this section. $$\sum_{m=k}^N m \frac{\binom{m-1}{k-1}}{\binom N k} = ...
3
votes
1answer
109 views

Vandermonde-like sum

I know a Vandermonde's identity as $$ \sum_{i=0}^c {a \choose i} {b \choose c-i} = {a+b \choose c} $$ $$ a, b, c \in \mathbb{N} $$ I am looking for a way to simplify these expressions: $$ ...
3
votes
1answer
252 views

Average absolute value of sum with Rademacher random variables

Let $a_1, \ldots, a_n $ be independent Rademacher random variables with distribution $P(a_i=1) = P(a_i=-1) = \frac 12$. Estimate from below $$E \left|\sum_{i=1}^n a_i\right|.$$ I've reduced this ...
3
votes
2answers
172 views

Proving Binomial Idenity without calculus

How to establish the following identities without the help of calculus: For positive integer $n, $ $$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r $$ and $$\sum_{0\le r\le ...
3
votes
2answers
628 views

Binomial theorem in probability

We know according to binomial probability theorem , $$P= \binom{n}{r} p^r (1-p)^{n-r} \tag{1}$$ Now If I flip a coin 10 times and want to get the probability for 4 heads then we get according to the ...
3
votes
1answer
58 views

An equality involving binomial coefitients

I am wondering why formula $$\sum_{j=k}^n\binom{n}{j}(-1)^j = (-1)^k\binom{n-1}{k-1} $$ is correct only for $1<k<n+1$. Could it be extended to $0<k<n+1$? I found this formula here.
3
votes
2answers
65 views

Identity of binomial series with factorial.

I'm looking for a simple identity for the formula: $$ \sum_{k = 0}^{p} \binom{p}{k} \cdot k! \cdot x^k $$ In words, I have $p$ "players" who can choose to play or not (every player is represented by ...
3
votes
1answer
130 views

Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?

How can you compute the asymptotics of $$T=\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k}\;?$$ This is related to Asymptotics of sum of binomials . I attempted to simply use Stirling's ...
3
votes
1answer
106 views

Equivalence of two binomial type equations

Given that $$A=\sum_{i=k}^{2k-1}\binom {2k-1} ix^i(1-x)^{2k-1-i}$$ and $$B=\sum_{i=k+1}^{2k}\binom {2k} i x^i(1-x)^{2k-i}+\frac{1}{2}\binom {2k} k x^k(1-x)^k$$ I would like to prove that $A=B$ ...
3
votes
2answers
186 views

Prove summation formula for binomial coefficients [duplicate]

Possible Duplicate: simple binomial theorem proof Prove that: \begin{equation} \sum_{k=0}^n \binom{k+a}{k}=\frac{(n+a+1)!}{n! (a+1)!}, \end{equation} where $a$ is a constant, without ...
3
votes
2answers
57 views

Proving the binomial coefficient identity $\binom{~s + t~ }{s} = \prod_{i=1}^s \prod_{j=1}^t \frac{i + j}{i + j - 1}$

I tried expanding the factorial, but I do not know how to finish the proof. \begin{eqnarray*} \binom{~s + t~ }{s} & = & \frac{(s+t)!}{s! ~ t!}\\ & = & \frac{(s+t)(s+t-1) \cdots ...
3
votes
1answer
289 views

A sum involving permutation

Does there exist a nice closed form formula for the sum $$\sum_{k=0}^m P(m,k)x^k$$ where $P(m,k)=C(m,k)*k!$, $C(m,k)$ being the "m choose k" number. Formula given by Maple 11 is complicated. I ...
3
votes
1answer
336 views

Sum of every $k$th binomial coefficient.

It is widely known that $$\sum_{m=0}^{n} {n\choose m} = 2^n$$ and that $$\sum_{m=0}^{\lfloor\frac{n}{2}\rfloor}{n\choose 2m} = 2^{n-1}$$ Both results can be proven by exploting the nature of the roots ...
3
votes
1answer
923 views

Counting the number of directed graphs with $N$ vertices and $E$ edges?

Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
3
votes
2answers
314 views

Number of nonnegative integral solutions of $x_1 + x_2 + \cdots + x_k = n$

To find all solutions greater than or equal to $1$ of a linear equation in the form $$x_1+x_2+x_3+\cdots+x_k=n ,$$ the number of them is $\binom{n-1}{k-1}$. If I need all solutions to be greater or ...
3
votes
1answer
9k views

Negative Exponents in Binomial Theorem

I'm looking at extensions of the binomial formula to negative powers. I've figured out how to do $n \choose k$ when $n < 0 $ and $k \geq 0$: $${n \choose k} = (-1)^k {-n + k - 1 \choose k}$$ So ...
3
votes
1answer
124 views

How to prove that $\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$?

How to prove this: $$\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$$ For all $x\in\mathbb R_{\ge0}$ and with $\binom{x}{r}=\frac{\Gamma(x+1)}{\Gamma(r+1)\cdot\Gamma(x-r+1)}$ It is obviously ...
3
votes
2answers
71 views

Root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$

Is there an analytic way to obtain the highest root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$ in terms of $K$ and $C$? The integer $K \ll x$ and the constant $C$ are known. The other way to ask ...
3
votes
3answers
47 views

Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a ...
3
votes
3answers
56 views

How find this sum $\sum_{k=0}^{p}t^k\binom{n}{k}\binom{m}{p-k}$

Find the closed form $$\sum_{k=0}^{p}t^k\binom{n}{k}\binom{m}{p-k}$$ since $$\binom{n}{k}\binom{m}{p-k}=\dfrac{n!}{(n-k)!k!}\cdot\dfrac{m!}{(p-k)!(m-p+k)!}$$ then I can't
3
votes
1answer
48 views

Very loose bound on sum of first binomials

Let $n\geq k\geq 2$. Is it always true that $$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\leq n^k?$$ The left-hand side is dominated by the term $\dfrac{n^k}{k!}$, so the statement should be true. ...
3
votes
1answer
76 views

How find this sum $\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{(-1)^k\binom{n-k}{k}}{n-k}$

How find this sum $$\sum_{k=0}^{\left[\dfrac{n}{2}\right]}\dfrac{(-1)^k\binom{n-k}{k}}{n-k}$$ My try:since $$\dfrac{(-1)^k}{n-k}=\int_{-1}^{0}x^{n-k-1}dx$$ then I can't Thank you very much!
3
votes
1answer
40 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 ...
3
votes
1answer
48 views

Coefficients in Pochhammer Expansion

Can anyone tell me if there is a formula for finding the coefficient of $x^3$ in the expansion of $(3x+5)_{6}$, where $(a)_n$ denotes the Pochhammer symbol, i.e. $(a)_{n}=a\cdot(a+1)\cdots(a+n-1)$? ...
3
votes
1answer
96 views

Sum of fraction of factorials

Can anybody explain this? $$\sum\limits_{k=1}^{\frac{m-1}2}\frac{(2k)!(2m-2k)!}{(2k-1)(2m-2k-1)k!^2(m-k)!^2}=\frac{(2m)!}{(2 m-1)m!^2}$$ I did actually simplify this to: ...
3
votes
1answer
189 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
3
votes
1answer
105 views

How to prove that $\sum_{i=0}^{a}\frac{i\binom{a+b-c-i}{a-i}\binom{c+i-1}{i}}{\binom{a+b-1}{a}}=\frac{ac(a+b)}{b(b+1)}$

let $$b\ge c,a,b,c\in N^{+}$$ Show that $$\sum_{i=0}^{a}\dfrac{i\binom{a+b-c-i}{a-i}\binom{c+i-1}{i}}{\binom{a+b-1}{a}}=\dfrac{ac(a+b)}{b(b+1)}$$ This sum is similar to Hypergeometric distribution, ...
3
votes
2answers
85 views

combinatorics - fixed point permutations

Simple question but I just need a little tip to finish it. we are given $A=\{1,2,3...,2n-1,2n\}$ the set of all integers between and including $1$ and $2n$. We are asked how many different ...
3
votes
1answer
180 views

Proving combinatorial identity

I need to prove following combinatorial identities: $$ \sum\limits_s(-1)^s\binom{p+s-1}{s}\binom{2m+2p+s}{2m+1-s}2^s=0 $$ $$ ...
3
votes
1answer
70 views

Is this equation about binomial-coefficients true?

Question : Is the following true? $$\sum_{r=k}^{n}\frac{\binom{q}{r}}{\binom{p}{r}}=\frac{p+1}{p-q+1}\left(\frac{\binom{q}{k}}{\binom{p+1}{k}}-\frac{\binom{q}{n+1}}{\binom{p+1}{n+1}}\right)$$ for ...
3
votes
1answer
83 views

On Elements of $p$th Row in n Pascal's Triangle (For Prime $p$)

If $p$ is a prime number, in Pascal's triangle all the terms in the $p$th row - except the 1s - are multiples of $p$ . It's easy to prove this property using the formula for $\binom{p}{k}$. Is there ...
3
votes
1answer
120 views

Combinatorial Proof of a Binomial Coefficient Identity

I am looking to prove the following identity combinatorially: $\sum_k$ $n \choose 2k$ $2k \choose k$ $2^{n-2k}$ = $2n \choose n$ Clearly the RHS counts the number of ways to choose n elements ...
3
votes
1answer
52 views

Trying to prove a binomial equation

I've been emptying my notebook over this, and still reach the same nothing at the end. I'm trying to prove that the following equation is true, with no luck: $\forall n,k \in \mathbb{N}^+ . ...
3
votes
1answer
337 views

Three problems with binomial coefficients

I found three difficult problems for me, involving binomial coefficients. They are extremely interesting I think, but I don't know if I have enough knowledge to manage. Seem really hard, can you help ...
3
votes
1answer
945 views

Multiplication of Two Infinite Series

This question has been deleted. How to prove that $$\displaystyle \left( \sum_{k=0}^{\infty }\frac{\left( -a\right) ^{k}y^{2k}}{k!}\right) \left( \sum_{k=0}^{\infty }\frac{a^{k}y^{2k+1}}{\left( ...
3
votes
1answer
88 views

is the approximation of the sum true?

Someone commented under my question Calculation of the moments using Hypergeometric distribution that $$ \sum_{k=0}^l\frac{{l \choose k}{2n-l \choose n-k}(2k-l)^q}{{2n\choose n}}\sim \sum_{k=0}^l ...
3
votes
1answer
420 views

Matrix and Binomial Coefficients

Considering the construction of a matrix as follows. The $n$th row in the matrix is filled with the coeffcients of $x^r$ in the expansion of $(1+x)^n$ from the columns $2n$ to $3n$ inclusive and ...
3
votes
1answer
551 views

How to solve an inequality containing the sum of factorials and powers

In previous question, I asked how one would simplify the following equation for the case where the variables are very big: $\sum\limits^{k}_{i=m}(N-i)^{k-i}(\frac{1}{N})^k\frac{k!}{(k-i)!i!} \leq a$ ...
3
votes
2answers
25 views

The asymptotic behavior of the CDF of Binomial distribution

I got stuck with the following problem which seemed not to be very complicated at the beginning! I would like to compute the CDF of a Binomial distribution, \begin{equation*} F(\ell;n,q) = ...
3
votes
0answers
71 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Sigmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
3
votes
1answer
83 views

How to calculate the sum of binomials? [closed]

I want to prove below: n is natural number. $$\sum_{k=1}^n k \binom{2n}{n+k} =\frac{1}{2}(n+1) \binom{2n}{n+1}$$ Please tell me above proof.
3
votes
0answers
107 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...
3
votes
3answers
114 views

Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ [duplicate]

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = ...
3
votes
0answers
38 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 ...
3
votes
0answers
41 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
1answer
107 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 ...
3
votes
0answers
44 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
3
votes
1answer
108 views

Monotonicity of a finite sum

How can I prove that the following function $f(p)$ is non-increasing in $p$: \begin{align*} f(p)=\sum_{i=a}^{N}\left(1-\frac{1}{b \cdot(i-1)}\right)\binom{N}{i}(1-p)^ip^{N-i} \end{align*} where $N$ ...
3
votes
0answers
207 views

Proving identity involving sum

I'm stuck trying to prove the following identity: $$\displaystyle\sum_{i=j}^k\frac{(-1)^{i+j}{k+1 \choose i}{i \choose j}(4S-i-k-3)!(4S-2i-1)}{(4S-i-j-1)!} $$ $$=\frac{(-1)^{j+k}(4S-2k-3)!{k+1 ...
3
votes
2answers
93 views

Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem

So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...