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
4answers
116 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
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 ...
3
votes
3answers
119 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$
3
votes
1answer
46 views

Binomial coefficient difference

I have the following difference of binomial coefficients: $$f(m)={m+n\choose n}-{m-d+n\choose n}$$ I believe the following two things should hold true: For $m$ large enough, $f(m)$ is a polynomial ...
3
votes
2answers
75 views

$2^n=C_0+C_1+\dots+C_n$

Could anyone give me hints for this one? $2^n=C_0+C_1+\dots+C_n$ Thats all I can say and I know tricks like integrating or differentiating both side and then put $x=1$ or what ever we need. but ...
3
votes
3answers
167 views

Find the 100th derivative of $x \sinh(2x)$

If $f(x) = x \sinh(2x)$, find $f^{({100})}(x)$. My (Incorrect) working so far: Using Leibniz' Formula for derivatives: $$(fg)^{(n)}=\sum_{k=0}^n{n\choose k}f^{(k)}g^{(n-k)}$$ ...
3
votes
2answers
83 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
1answer
85 views

Bertrand's postulate proof

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from ...
3
votes
3answers
130 views

Stirling Binomial Polynomial

Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k ...
3
votes
1answer
69 views

Evaluating Sums Combinatorially

Consider the following finite sums: (1) $\sum k(k!)$ for k from 1 to n (2) $\sum (k-1)(n-k)$ from 1 to n I am trying to determine how to evaluate these sums combinatorially. It seems the first is ...
3
votes
3answers
276 views

Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$

Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $ $$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$ use for ...
3
votes
1answer
50 views

Binomial coefficient help?

I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one: Q) If a there are 11 dogs and 9 cats: a) How many 7 ...
3
votes
3answers
107 views

Probability someone's phone will ring during a movie?

Trying to figure out what the probability is that in a room of 200 people what the probability that at least one will get a phone call during a certain time window... In this case 2 hours ...
3
votes
1answer
132 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 ...
3
votes
2answers
274 views

Lower Bound of Central Binomial Coefficients

I would like to prove by induction the following inequality: $\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1. Any hints?
3
votes
2answers
124 views

A combinatorial exercise

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars. This is what I have done, but I realized that it's ...
3
votes
1answer
228 views

binomial expansion

$\displaystyle \binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}$ $\displaystyle \left(1+x\right)^{n} = \left(1+x\right)\left(1+x\right)^{n-1}$ how do I use binomial expansion on the second equations ...
3
votes
1answer
369 views

Finding a simple expression - Binomial Theorem

How does one find a simple expression of the one below applying the binomial theorem: $$\sum_{k=1}^n k \cdot 2^k{ n \choose k}$$ Edit: $\frac{d}{dx}(x^k)=kx^{k-1}$ $(1 + x)^n = \sum_{k=0}^n { n ...
3
votes
1answer
48 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
3
votes
1answer
45 views

How prove $\binom{n}{m}\le\left(\frac{en}{m}\right)^m$ [duplicate]

Show that $$\binom{n}{m}\le\left(\dfrac{en}{m}\right)^m$$ where $0<m\le n,m,n\in N^{+}$ My idea: since ...
3
votes
1answer
200 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot ...
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
1answer
110 views

Pascal Triangle general formula

I'm working on a presentation on the Binomial Theorem for my Algebra 2 class and while writing Pascal's Triangle, I came across one of the properties that I haven't seen in a while. That being ...
3
votes
1answer
107 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
3
votes
2answers
439 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
111 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
259 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
176 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
658 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
59 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
271 views

Sum of product of binomial coefficients $ = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$$ This is a question from a very old high school exam paper I came across. It ...
3
votes
2answers
66 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
131 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
108 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
294 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
341 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
935 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
318 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
43 views

How to calculate the number of integer solution of a linear equation with constraints?

If an equation is given like this , $$x_1+x_2+...x_i+...x_n = S$$ and for each $x_i$ a constraint $$0\le x_i \le L_i$$ How do we calculate the number of Integer solutions to this problem?
3
votes
1answer
72 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
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
51 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
58 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
51 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
78 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
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 ...
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
101 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: ...