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)

1
vote
1answer
144 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
10
votes
3answers
297 views

Computing: $\lim\limits_{n\to\infty}\left(\prod\limits_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$

I try to compute the following limit: $$\lim_{n\to\infty}\left(\prod_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$$ I'm interested in finding some reasonable ways of solving the limit. I don't find any ...
10
votes
2answers
329 views

The integral $\int_0^1 \frac{(x+1)^n-1}{x} dx$

I know that the integral $\int_0^1 \frac{(x+1)^n-1}{x} dx,$ for $n \in \mathbb{Z}^+$, can be evaluated by expanding the numerator with the binomial theorem and integrating term by term. You get the ...
7
votes
2answers
652 views

Binomial coefficients: how to prove an inequality on the $p$-adic valuation?

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used: $$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln ...
6
votes
3answers
111 views

How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$

How do I find sums like these?-- $$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$ that is, when there is a summation of binomial coefficients, but with jumps of some terms..?
6
votes
1answer
187 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$.
5
votes
2answers
456 views

Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$. I have already shown that if $n$ is of the form $2^r-1$, ...
5
votes
0answers
182 views

Partial sum over $M$, of ${m+j \choose M} {1-M \choose m+i-M}$?

Is there (likely to be) any formula for $$ \sum_{m' \geq m} {m+j \choose m'} {B - m' \choose m+i-m'} $$ ? I am mainly interested in the case $B=1$ (or a prime power), if that's any ...
5
votes
3answers
3k views

How to simplify or calculate a formula with very big factorials

I'm facing a practical problem where I've calculated a formula that, with the help of some programming, can bring me to my final answer. However, the numbers involved are so big that it takes ages to ...
4
votes
5answers
192 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
4
votes
1answer
235 views

Divisibility of binomial coefficient by prime power - Kummer's theorem

Let's say we have binomial coefficient $\binom{n}{m}$. And we need to find the greatest power of prime $p$ that divides it. Usually Kummer's theorem is stated in terms of the number of carries you ...
4
votes
1answer
226 views

Proving $\binom{2n}{n}\ge\frac{2^{2n-1}}{\sqrt{n}}$

Prove that $$\binom{2n}{n}\ge\dfrac{2^{2n-1}}{\sqrt{n}}$$ By the way: I have see $$\binom{2n}{n}\ge\dfrac{4^n}{2n}=\dfrac{2^{2n-1}}{n}$$ proof: Applying the binomial theorem ...
4
votes
2answers
153 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
4
votes
1answer
51 views

$\frac{1}{4^n}\binom{1/2}{n} \stackrel{?}{=} \frac{1}{1+2n}\binom{n+1/2}{2n}$ - An identity for fractional binomial coefficients

In trying to write an answer to this question: calculate the roots of $z = 1 + z^{1/2}$ using Lagrange expansion I have come across the identity $$ \frac{1}{4^n}\binom{1/2}{n} = ...
4
votes
3answers
849 views

Distributing identical objects to identical boxes

We have 6 identical things to be distributed in 4 identical boxes such that empty boxes are allowed the find the number of ways to distribute the things ?
4
votes
2answers
541 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 ...
4
votes
3answers
446 views

Binomial Coefficients in the Binomial Theorem - Why Does It Work Question

to keep it simple: Given $(a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3$ Could you please give me an intuitive combinatoric reason to why the binomial coefficients are ...
4
votes
2answers
504 views

How to find $\sum_{k=1}^n 2^kC(n,k)$?

How to find the sum of series, $$\sum_{k=1}^n 2^kC(n,k)$$
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
4answers
124 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
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
3answers
119 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
121 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
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
145 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
580 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
130 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
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
3answers
833 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
623 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
226 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
96 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
90 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
77 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
1answer
126 views

Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
2
votes
3answers
195 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
481 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
99 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
305 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
294 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
315 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
225 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
157 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
1k 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
431 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
732 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
163 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
3answers
133 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 ...
1
vote
2answers
80 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
5answers
127 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?