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

4
votes
3answers
1k views

Estimating a certain row of Pascal's triangle

I need to calculate all the numbers in a certain row of Pascal's triangle. Obviously, this is easy to do with combinatorics. However, what do you do when you need to estimate all the numbers in, say, ...
3
votes
1answer
121 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
4answers
111 views

Find $\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$

Find $$\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$$ I got $$\frac{2^{2n+1}(2n^2+n+1)-1}{(2n+1)(2n+2)}$$ but the answer is $$\frac{2^{2n+1}(2n^2-n+1)-2}{(2n+1)(2n+2)}$$ Thanks for the help...
3
votes
1answer
106 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
1answer
112 views

Combinatorial Proof of a Binomial Identity

$$\sum_k {m\choose k} {n \choose k} = {m+n \choose n}$$ In this identity we seem to be choosing subsets that do $\it not$ contain k of type m and type n for all possible k. In the style of ...
3
votes
1answer
125 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
142 views

How do i reduce this expression of binomial coefficients

I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression? $$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} ...
3
votes
4answers
544 views

Trying to find $\sum\limits_{k=0}^n k \binom{n}{k}$ [duplicate]

Possible Duplicate: How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$? $$\begin{align} &\sum_{k=0}^n k \binom{n}{k} =\\ &\sum_{k=0}^n k ...
3
votes
2answers
128 views

Why is the binomial coefficient related to the binomial theorem?

The binomial coefficient basically provides the number of ways to choose a set of $k$ from $n$ sets. To me, it can be considered the number of unique ways to pick $k$ amount of "cards" from a deck of ...
3
votes
3answers
750 views

How can I prove that the binomial coefficient ${n \choose k}$ is monotonically nondecreasing for $n \ge k$?

I want to prove that the binomial coefficient ${n \choose k}$ for $n \ge k$ is a monotonically nondecreasing sequence for a fixed $k$. How do I do this?
3
votes
2answers
617 views

Why does $\sum\limits_{i=0}^k {k\choose i}=2^k$ [duplicate]

Possible Duplicate: Proving a special case of the binomial theorem Can anyone explain to me why $$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$ Thanks in advance
3
votes
1answer
215 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 ...
2
votes
4answers
84 views

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ [closed]

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
2
votes
1answer
86 views

Another binomial identity

Prove that $$(2m-1)^m=\sum_{j=1}^m(2j-1)C^m_j(2m-1)^{m-j},$$ where $C^m_j$ denotes binomial coefficient. I tried induction but got nowhere. I guess some simple binomial coefficient identity will do ...
2
votes
1answer
75 views

Simple problem on restricted partition

When finding number of ways to partition n distinct chocolates among m children such that each child has at most $$\left\{\begin{matrix} \left \lfloor \frac{n}{m} \right \rfloor & \text{if} \ \ ...
2
votes
3answers
186 views

Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?

Can this identity be derived from the binomial theorem? $$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$ I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it ...
2
votes
2answers
391 views

Finding Binomial expansion of a radical

I am having trouble finding the correct binomial expansion for $\dfrac{1}{\sqrt{1-4x}}$: Simplifying the radical I get: $(1-4x)^{-\frac{1}{2}}$ Now I want to find ${n\choose k} = ...
2
votes
1answer
98 views

How to simpify the following equation involving binomial coefficients?

How can one simplify this equation: $$ \sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1} $$
2
votes
3answers
253 views

How many distinct football teams of 11 players can be formed with 33 men?

Can anyone help me with this problem, I can't figure out how to solve it... How many distinct football teams can be formed with 33 men? Thanks!
2
votes
1answer
267 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the ...
2
votes
2answers
303 views

Does this qualify as a proof? (Spivak's 'Calculus')

I'm working through Spivak's 'Calculus' at the moment, and a question about series confused me a bit. I think I have the solution, but I'm not sure if my "proof" holds. The question is: Prove ...
2
votes
1answer
207 views

Going from binomial distribution to Poisson distribution

Why does the Poisson distribution $$\!f(k; \lambda)= \Pr(X=k)= \frac{\lambda^k \exp{(-\lambda})}{k!}$$ contain the exponential function $\exp$, while its relation to the binomial distribution would ...
2
votes
1answer
155 views

Cardinality of set containing true order relations from a power set

This question is from the book Introduction to Topology and Modern Analysis by GF Simmons, Problem 3(d) at end of Section 1. I'll paraphrase the question here. Suppose $U$ is a containing $n$ ...
2
votes
1answer
966 views

Proving that $n \choose k$ is an integer [duplicate]

Possible Duplicate: Proof that a Combination is an integer I can't think how to prove that ${n\choose k} \in\mathbb{Z}$. I've played with it for a while, using the factorial definition for ...
2
votes
2answers
418 views

Divisibility using binomial coefficients

I have to prove that $6 \mid n^3 + 5n$ in a number of ways. One that I've been finding impossible is binomial coefficients. This is the problem statment: Use an expression in terms of binomial ...
2
votes
2answers
696 views

Combinatorial proof of binomial coefficient summation

While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming: Given two positive integers $n$ and $k$, in how many ways do $k$ ...
2
votes
4answers
161 views

How to sum up this series?

How to sum up this series : $$2C_o + \frac{2^2}{2}C_1 + \frac{2^3}{3}C_2 + \cdots + \frac{2^{n+1}}{n+1}C_n$$ Any hint that will lead me to the correct solution will be highly appreciated. EDIT: ...
1
vote
2answers
61 views

Finding the child node in the recombining binomial tree

I am trying to program a binomial tree in Matlab. The tree looks something like this: The numbers in the picture refer to the index of the array to create a binomial tree. Problem: Value of 2 = ...
1
vote
2answers
60 views

How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$ Im trying with mathematical induction but im stuck. My inductive step: $H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$ $T) \sum_{k=0}^{h+1} ...
1
vote
1answer
36 views

Binomial-like Sum

We know that $\sum_{k=0}^n a^k \frac{n^{\underline k}}{k!} = (1+a)^n$. Is there a known (preferably closed) form for $\sum_{k=0}^n a^k/k!$ ? This question was prompted by another recent question.
1
vote
3answers
51 views

Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]

Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$. While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging ...
1
vote
3answers
866 views

Sum with binomial coefficients

I'm repeating material for test and I came across the example that I can not do. How to calculate this sum: $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
1
vote
3answers
433 views

Binomial inequality

Show that we have: $$ \binom{n}{s}\leq n^n $$
1
vote
1answer
137 views

On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
1
vote
1answer
105 views

Combination Problem with a Variable

I have the following problem: $_xC_6$ = $_xC_4$ I expand both sides to: $$\frac{x!}{[(x-6)!]6!} = \frac{x!}{[(x-4)]!4!}$$ Next I multiply both sides by the denominator of the right-hand ...
0
votes
4answers
78 views

$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum $$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}$$ could anyone give me an advice on how to get started?
0
votes
1answer
98 views

Combinatorial approach to $\sum\limits_{i=1}^n \binom{i+r-1}i$ [closed]

$$\sum_{i = 1}^n \binom{i+r-1}{i}$$ I want to solve above sum combinatorially.
0
votes
1answer
152 views

How do I compute the summation of ${80\choose k}\cdot {k+1 \choose 31}$?

How do I compute the summation of ${80 \choose k}{ k+1 \choose 31}$? I have it expanded in this way $\frac{80!}{k!(80-k)!} \cdot \frac{(k+1)!}{31!(k-30)!}$ Is there a way I can write this as an ...
0
votes
1answer
500 views

Finding the Greatest Coefficient in a Binomial Expansion?

when I do this question, I try not using the: $(n-k+1)/k * b/a$ formula, but rather the $T(k+1)/T(k) ≥ 1$ formula. However, when I do it like that, I get the wrong answer - which is probably a simple ...
0
votes
2answers
110 views

Finding a set of values with the binomial theorem

For $n \in \mathbb N$ and the function $p(x) = \left(x + \frac 1x\right)^{n}$. By the binomial theorem: $$\left(x + \frac 1x\right)^{n} = \sum_{k=0}^n {n \choose k} x^{n-k} \left(\frac ...
0
votes
1answer
94 views

Binomial expansion for solving american put option identity [duplicate]

For american put option I have to prove that: 1) As $D$ tends to $\infty$, $a_n$ tends to $-r/D$ so that $S^*$ tends to $0$. 2) As $D$ tends to $-\infty$, $a_n$ tends to $2D/ \sigma^2$ so that ...
0
votes
1answer
84 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 ...