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)

12
votes
1answer
768 views

Counting subsets with r mod 5 elements

Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4). The story becomes even more interesting if one asks about number of subsets of ...
11
votes
5answers
452 views

How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$ ...
8
votes
4answers
392 views

Why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0$?

I know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$? I've been ...
7
votes
4answers
490 views

The binomial formula and the value of 0^0

Here is the text from Knuth's The Art of computer programming, 1.2.6 F formula 14: Knuth doesn't give the proof of the statement. So, I tried to write it myself. To make binomial formula equal to ...
7
votes
2answers
340 views

Combinatorial argument for the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$

I am looking for the combinatorial argument for the identity: \begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation} This is easy to show algebraically as: \begin{equation} \binom{n}{k} ...
6
votes
6answers
202 views

How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to ...
6
votes
4answers
906 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
6
votes
6answers
5k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
6
votes
2answers
422 views

Prove the identity $\sum\limits_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $

I need to prove $$\sum_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $$ using: $$(1-x)^{-m-1} (1-x)^{-q-1} = (1-x)^{-m-q-2} .$$ ok, generating function :$\frac1{(1-x)^{m+1}} = ...
5
votes
3answers
402 views

Dividing factorials is always integer

Is there a simple way to show that $$n!\over r!(n-r)!$$ is always an integer?
5
votes
3answers
820 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
4
votes
4answers
139 views

A binomial inequality with factorial fractions

Prove that $$\left(1+\frac{1}{n}\right)^n<\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{n!}$$ for $n>1 , n \in \mathbb{N}$.
4
votes
3answers
608 views

Alternating sign Vandermonde convolution

The well-known Vandermonde convolution gives us the closed form $\sum_{k=0}^n {r\choose k}{s\choose n-k} = {r+s \choose n}$. For the case $r=s$, it is also known that $\sum_{k=0}^n (-1)^k {r \choose ...
3
votes
2answers
115 views

when is $\frac{1}{n}\binom{n}{r}$ an integer

So I am considering for which values of n is $a_n =\frac{1}{n}\binom{n}{r}$ an integer for all $ 1\leq r \leq n-1 $. The first thing I did was to check the Pascal Triangle. So I guess n has to be ...
3
votes
3answers
110 views

Asymptotic of a sum involving binomial coefficients

Could you help me to find an asymptotic for this sum? $$ \sum_{k=0}^{n - 1} (-1)^k {n \choose k} {3n - k - 1 \choose 2n - k} = {n \choose 0} {3n - 1 \choose 2n} - {n \choose 1} {3n - 2 \choose 2n - ...
2
votes
1answer
37 views

Number of Elements in a Conjugacy Class of $S_N$ (Derivation)

Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is ...
2
votes
2answers
49 views

how many terms will there be once you collect terms with equal monomials? What is the sum of all the coefficients?

If you expand $(x_1+x_2+\cdots+x_k)^n$, how many terms will there be once you collect terms with equal monomials? What is the sum of all the coefficients? I'm kind of lost here. This came up with ...
2
votes
4answers
138 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
2
votes
3answers
107 views

Gosper's Identity $\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $

The page on Binomial Sums in Wolfram Mathworld http://mathworld.wolfram.com/BinomialSums.html (Equation 69) gives this neat-looking identity due to Gosper (1972): $$\sum_{k=0}^n{n+k\choose ...
2
votes
3answers
414 views

Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following: If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$. I did the following steps: \begin{align} ...
2
votes
2answers
381 views

Alternating sum of binomial coefficients $\sum(-1)^k{n\choose k}\frac{1}{k+1}$ [duplicate]

I would appreciate if somebody could help me with the following problem Q:Calculate the sum: $$ \sum_{k=1}^n (-1)^k {n\choose k}\frac{1}{k+1} $$
2
votes
1answer
539 views

Evaluate $\sum\limits_{k=0}^n \binom{n}{k}$ combinatorially

Please help me to evaluate combinatorially the following sum: $$\sum_{k=0}^n \binom{n}{k}$$ Thank you.
2
votes
4answers
1k views

Show that $\binom{2n}{ n}$ is divisible by 2? [duplicate]

Possible Duplicate: prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer Show that $\binom{2n}{ n}$ is divisible by 2? Any help would be appreciated..
2
votes
1answer
333 views

Formula for binomial coefficients

Does someone know, if the subsequent formula holds for $m \ge n \ge i \ge 1$ and if yes, can give a reference. $$\sum_{k=i}^{m-n+i}\binom{k}{i}\binom{m-k}{n-i} = \binom{m+1}{n+1}$$ Thank you very ...
1
vote
3answers
91 views

Number of terms in the expansion of $\left(1+\frac{1}{x}+\frac{1}{x^2}\right)^n$

Number of terms in the expansion of $$\left(1+\frac{1}{x}+\frac{1}{x^2}\right)^n$$ $\bf{My\; Try::}$ We can write ...
1
vote
2answers
74 views

Prove equality between binomial coefficients.

Using the Binomial theorem, prove that: $$ \binom{m+n}{k}=\sum_{j=0}^k \binom{n}{j}\binom{m}{k-j},\; 0\leq k\leq m+n$$
7
votes
3answers
180 views

Prove inequality with binomial coefficient: $6 + \frac{4^n}{2 \sqrt{n}} \le \binom{2n}n$

I have to prove inequality, where $n \in N$ $$6 + \frac{4^n}{2 \sqrt{n}} \le {2n \choose n}$$ I have checked and it is true when $n\ge4$, however I have no idea how I should start. Can anyone give a ...
7
votes
4answers
344 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 = ...
7
votes
2answers
286 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$.
6
votes
2answers
66 views

Find 2 sums with the binomial newton

Find the sum of: i)$\displaystyle\sum_{k=0}^{n} k^2$ $\left(\begin{array}{c} n\\k\end{array}\right)$ ii) $\displaystyle\sum_{k=1}^{n} \frac{2k+5}{k+1}$$\left(\begin{array}{c} ...
6
votes
2answers
214 views

Challenge: How to prove this identity between bi- and trinomial coefficients?

This question is the continuation of its predecessor. Using the convention that trinomial coefficients $$ \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!} $$ are zero if $k_i<0$ or $\sum_i k_i\neq ...
6
votes
3answers
139 views

Bounds for $\binom{n}{cn}$ with $0 < c < 1$.

Are there really good upper and lower bounds for $\binom{n}{cn}$ when $c$ is a constant $0 < c < 1$? I know that $\left(\frac{1}{c^{cn}}\right) \leq \binom{n}{cn} \leq ...
5
votes
1answer
155 views

Trying to solve the equation $\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{n-m}{t-i}=0 $ for non-negative integers $m,n,t$

While considering a previous unanswered question, I started looking for the non-negative integer solutions $ m,n,t , (n\ge m)$ to the equation: $$ ...
5
votes
4answers
133 views

Proving $\binom{m}{n} + \binom{m}{n-1} = \binom{m+1}{n}$ algebraically

I am working through the exercises and have spent half a day on one problem so I decided to get some help because I can't figure it out. Show that if $n$ is a positive integer at most equal to $m$, ...
5
votes
2answers
348 views

What's the intuition behind this equality involving combinatorics? [duplicate]

What is the intuition behind $$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$ ? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
5
votes
4answers
370 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
5
votes
1answer
781 views

Calculation of the moments using Hypergeometric distribution

Let vector $a\in 2n $ is such that first $l$ of its coordinates are $1$ and the rest are $0$ ($a=(1,\ldots, 1,0, \ldots, 0)$). Let $\pi$ be $k$-th permutation of set $\{1, \ldots, 2n\}$. Define ...
4
votes
4answers
169 views

How to prove that $\sum_{r=0}^n\binom{n}{r}2^r=3^n$

I need help proving that $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$ I'm thinking this should use the idea that $\binom{n}{r}=\binom{n}{n-r}$ but I'm not sure how to proceed with it. Thanks in advance!
4
votes
2answers
2k views

How do I determine the possible number of combinations of two ordered sets?

I'm not quite sure what the mathematical term for what I'm asking is, so let me just describe what I'm trying to figure out. Let's say that I have two ordered sets of numbers $\{1, 2\}$ and $\{3, ...
3
votes
2answers
60 views

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$, $1 \le n < pq$, are divisible by $pq$? In particular, if $p$ and $q$ are distinct odd primes, and $n$ is even, does $pq ...
3
votes
5answers
145 views

Calculate $\lim_{n\rightarrow +\infty}\binom{2n} n$

Calculate $$\lim_{n\rightarrow +\infty}\binom{2n} n$$ without use Stirling's Formula. Any suggestions please?
3
votes
2answers
142 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
3
votes
3answers
243 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
3answers
520 views

A combinatorial proof that the alternating sum of binomial coefficients is zero

I came across the following problem in a book: Give a combinatorial proof of $$ {n \choose 0} + {n \choose 2} + {n \choose 4} + \, \, ... \, = {n \choose 1} + {n \choose 3} + {n \choose 5} + \, \, ...
3
votes
3answers
96 views

Manipulation of a binomial coefficient

In obtaining a formula for the Catalan numbers I have got the expression $-\frac{1}{2}\binom{1/2}{n}(-4)^n$. All my efforts to show that this simplifies to $\frac{1}{n}\binom{2n-2}{n-1}$ have not ...
2
votes
5answers
112 views

Prove $n\binom{p}{n}=p\binom{p-1}{n-1}$

Let $p\in \mathbb{R}$ and $n\in \mathbb{N}$ and $$\binom{p}{n}=\frac{p(p-1)(p-2)...(p-n+1)}{n!}$$ b) Prove $$n\binom{p}{n}=p\binom{p-1}{n-1}$$ Thanks for all the help with a! I definitely understand ...
2
votes
2answers
316 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
2
votes
1answer
555 views

Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: $$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$ The problem is that I ...
2
votes
1answer
164 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
2k views

Negative Binomial Coefficients

Is it true that Pascal's Rule holds for binomial coefficients with a negative upper index? With $n = -1$ and $k = 3$, for example, it appears not to hold.