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
413 views

Combinatorial proof of $\sum_{i=0}^k\binom{m+k-i-1}{k-i}\binom{n+i-1}{i}=\binom{m+n+k-1}{k}$?

Please provide a combinatorial proof for the following: Prove the identity $$\sum_{i=0}^{k}{m+k-i-1 \choose k-i}{n+i-1 \choose i}={m+n+k-1 \choose k}$$ Hint: use idea of "selection with repetition". ...
6
votes
2answers
249 views

Combinatorial proof: $p^{r-n}$ divides $\binom{p^{r-2}}{n}$

Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting ...
2
votes
0answers
119 views

Inequality with binomial coefficient

Let $n$ be a natural number, $m\in [-n, n]$. Let $p=0,\ldots, \frac{n+m}{2}$. Show, that for all $p$, $$ {n \choose \left[{\frac{n+m}{2}}\right]}\geq \frac{2^{n+1/2}}{\sqrt{n-p/2}}. $$ Thank you for ...
13
votes
1answer
344 views

Binomial sum of $n$ terms in closed form

Can we calculate the given combinatorial sum in closed form? $$ \frac{\binom{2}{0}}{1}+\frac{\binom{4}{1}}{2}+\frac{\binom{8}{2}}{3}+\frac{\binom{16}{3}}{4}+\cdots+\frac{\binom{2^n}{n-1}}{n}$$
11
votes
4answers
299 views

Determine $\displaystyle \lim_{n \to \infty}{{n} \choose {\frac{n}{2}}}\frac{1}{2^n}$, where each $n$ is even

For each positive even integer $n$, set $$P_n = \displaystyle {{n} \choose {\frac{n}{2}}}\frac{1}{2^n}.$$ Show that $\displaystyle \lim_{n \to \infty} P_n$ exists and determine its value. Here's ...
5
votes
1answer
79 views

Inconsistency in binomial expansion?

When I do a binomial expansion on $\frac{1}{(1-2x)(1+3x)}$ about $0$, I can do it in 2 ways. Method 1 $$\frac{1}{(1-2x)(1+3x)}=\frac{1}{1-2x}\frac{1}{1+3x}$$ Thus, getting $(1+y_1)^{-1}(1+y_2)^{-1}$. ...
1
vote
3answers
405 views

Combinatorial interpretation of the identity: ${n \choose k} = {n \choose n-k}$

What is the combinatorial interpretation of the identity: ${n \choose k} = {n \choose n-k}$? Proving this algebraically is trivial, but what exactly is the "symmetry" here. Could someone give me some ...
-1
votes
2answers
122 views

combinatorial proof, still don't understand

There are plenty of questions regarding combinatorial proofs up, but I'm not understanding them very well. Basic understanding: Count something on the RHS (show WHAT it is counting), and show that ...
2
votes
1answer
232 views

probability of rolling at least $n$ on $k$ 6-sided dice

Is there a simple form for the probability of rolling at least $n$ on $k$ 6-sided dice? Of course you can do it by recursion (see here). But is there a way to do it with just a few binomial ...
2
votes
4answers
670 views

Binomial Theorem identities, evaluate the sum

This is a homework problem, please don't blurt out the answer! :) I've been given the following, and asked to evaluate the sum: $$\sum_{k = 0}^{n}(-1)^k\binom{n}{k}10^k$$ So, I started out trying ...
7
votes
1answer
179 views

Determining when a certain binomial sum vanishes

Consider the following sum of signed binomial coefficients: $$S_{n,a,p} = \sum_{i \equiv a \mod p} \binom{n}{i}(-1)^i$$ ($n$ is a positive integer, $p$ is an odd prime, $a$ is between $0$ and ...
8
votes
1answer
194 views

Evaluate $\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$

Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$ I don't understand where to start. Please help.
1
vote
2answers
91 views

$\binom{n}{n+1} = 0$, right?

I was looking at the identity $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}, 1 \leq r \leq n$, so in the case $r = n$ we have $\binom{n}{n} = \binom{n-1}{n-1} + \binom{n-1}{n}$ that is $1 = 1 + ...
10
votes
3answers
408 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...
5
votes
1answer
127 views

ordered pairs in binomial coefficients

I have Two Question on Binomial Coefficients in which we have to calculate $n$ and $r$ (1) No. of ordered pairs $(n,r)$ which satisfy $\displaystyle \binom{n}{r} = 2013$ (2) No. of ordered pairs ...
0
votes
1answer
143 views

Binomial Coefficients

Using Combinatorial How can i Calculate (1) The Sum $\displaystyle \bf{\sum_{i=0}^{n}\binom{10}{i}.\binom{20}{m-i} = Maximum}$ . Then value of $\bf{m}$ is (2) The sum of $\displaystyle ...
0
votes
1answer
28 views

Calulating coefficiencies

I'm trying to calculate the number ofcoefficiencies of every $x^k$ in the expansion of $(x-\frac{1}{x})^{100}$ for an arbitrary $k\in\mathbb{Z}$ Now I tried the following formula: $\binom{100}{k}$ ...
5
votes
1answer
335 views

Evaluate $\sum_{n=1}^{\infty} \frac{(2n)!}{2^{2n}(n!)^2 (2n-1)}$

How to evaluate the series $$S = \sum_{n=1}^{\infty} \frac{1}{2^{2n}(2n-1)} \binom{2n}{n}$$ The original question was to show that for $$ a_n=\left(\frac{ 2n-3 }{ 2n }\right)a_{n-1} , a_1 = \frac 1 ...
3
votes
1answer
57 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}^+ . ...
7
votes
0answers
142 views

Characterization of Sequences with Integral Binomial Coefficients

For any sequence of positive integers $\{ a_i \}_{i \ge 1}$ we can define the generalized binomial coefficients $\binom{n}{k}_{a}$ as follows: $$m!_a = a_1 a_2 \cdots a_m, \binom{n}{k}_a = ...
4
votes
2answers
1k views

In how many ways can 3 distinct teams of 11 players be formed with 33 men?

Problem: In how many ways can 3 distinct teams of 11 players be formed with 33 men? Note: there are 33 distinct men. The problem is similar to this one: How many distinct football teams of 11 ...
1
vote
1answer
38 views

Binomial Theorem :: Confusion with Wiki Entry

I wanted an expansion of $(1+x)^n$ and refered Wikipedia but I don't understand why there is a condition of $|x|<1$. In general, for the series, the condition is not required am I right or am I ...
4
votes
1answer
206 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} ...
0
votes
1answer
222 views

binomial identity $\sum\limits_{k\ge 0} (-1)^k{n+1\choose k}{n+m-4k\choose n}=\sum\limits_{k\ge 0}{n+1\choose k}{n\choose m-2k}$

Let $m,n$ be integers satisfying the condition $m\le 3(n+1)$. Prove the identity $$\sum\limits_{k\ge 0} (-1)^k{n+1\choose k}{n+m-4k\choose n}=\sum\limits_{k\ge 0}{n+1\choose k}{n+1\choose m-2k}$$
11
votes
3answers
315 views

Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$
1
vote
0answers
164 views

Binomial coefficient (mod m)

$n\ge k $ $ m>0$ How to find? $$\binom{n}{k}\mod m$$ without counting $n,k!$
1
vote
4answers
958 views

Finding coefficient of a complicated binomial expression?

Say we have something like $$ (x+2+y)^{23} $$ How does one go about finding the co efficient of say $$ x^6y^7 $$
3
votes
4answers
726 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 ...
1
vote
1answer
44 views

$X_1+X_2$ follows $\operatorname{Bin}(n_1+n_2,p)$

$\newcommand{\Bin}{\operatorname{Bin}}$ My text doesn't define $X\sim \Bin(n,p)$ but after mentioning it, in the next few lines it writes that $f(x)$=$ {n\choose x}p^xq^{n-x}$ is the p.m.f. of the ...
1
vote
0answers
60 views

Approximation of factorial - Stirling formula [duplicate]

Possible Duplicate: Elementary central binomial coefficient estimates How can I prove that $$ \binom{n}{n/2} = \Theta\left(\frac{2^n}{\sqrt n}\right) $$ I tried with Stirlings ...
6
votes
3answers
524 views

Binomial Theorem past exam question, what do I do?

I have trouble understanding what I'm supposed to do in some of these math questions. Here's an exam question from an old exam: Let $A$ be a set with $n$ elements. The number of subsets of $A$ with ...
2
votes
3answers
662 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!
1
vote
3answers
349 views

Property of Binomial Coefficient

I have a "must be trivial" problem which I could not solve. Prove the following relation of binomial coefficients, if true: $$\sum_{k=1}^{n}{2n+1 \choose k}=2^{2n}-1$$ P.S. Though this is not ...
5
votes
2answers
84 views

Prove that $\lim_{n \to \infty} \binom{n}{k}a^n = 0$

I'm working with this problem but I have no idea how to solve it. Here $k$ is fixed and $0<a<1$. I was trying to use that $\lim_{n \to \infty} a^n =0$ and that $\binom{n}{k}\leq\frac{n^k}{k!}$ ...
2
votes
0answers
25 views

Majorante functions of class $C^k$ to multinomial coeficientes.

Let's $k_1+\ldots +k_p=1$. What functions of class $c^k$ are upper bounds for multinomial coeficientes $$ \begin{pmatrix} n\\k_1,\ldots,k_p\end{pmatrix}=\frac{n}{k_1!\cdot k_2!\cdot\ldots\cdot k_p!} ...
3
votes
2answers
378 views

This question involves Pascal's Triangle & Binomial Theorem. Full Question

Could anyone please help me on the following problem: Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use ...
3
votes
3answers
86 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 ...
4
votes
1answer
246 views

Probability of a certain dice roll sum disregarding lowest rolls

The number of ways to obtain a total of $p$ in $n$ rolls of $s$-sided dice is: $$c=\sum_{k=0}^{\lfloor(p-n)/s\rfloor}(-1)^k\binom{n}k\binom{p-sk-1}{n-1}\;.$$ What I'm interested in is making the $n$ ...
1
vote
6answers
269 views

How to simplify this expression by division

How to divide it $${\frac {{x}^{n-2}-{y}^{n-2}}{x-y}}$$ to remove the $x-y$ term from the denominator. We may assume that $n>2$ is an integer. Thanks.
5
votes
2answers
191 views

Generalization Of The Binomial Theorem

Consider the sum $$\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k$$ where $\alpha \in \mathbb{R}$ arbritary, $n_0 < n$. So it looks like binomial theorem, $$\sum_{k=0}^n {n \choose k} \cdot ...
2
votes
4answers
271 views

How is this a property of Pascal's triangle?

For all non-negative integers $k$ and $n$, $$ \dbinom{k}{k} + \dbinom{k+1}{k} + \dbinom{k+2}{k} + \ldots + \dbinom{n}{k} = \dbinom{n +1}{k+1} $$ How is this a property of Pascal's triangle? I do not ...
14
votes
3answers
431 views

A relationship between matrices, bernoulli polynomials, and binomial coefficients

We define the following polynomials, for $n≥0$: $$P_n(x)=(x+1)^{n+1}-x^{n+1}=\sum_{k=0}^{n}{\binom{n+1}{k}x^k}$$ For $n=0,1,2,3$ this gives us, $$P_0(x)=1\enspace P_1(x)=2x+1\enspace ...
7
votes
5answers
217 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
5
votes
0answers
535 views

Proof for an identity involving a sum of binomial coefficients

I am moving through a On The Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my skills are ...
6
votes
3answers
283 views

Number of acyclic digraphs on $[n]$ with $k$ edges and each indegree, outdegree $\leq 1$

How many (labelled) acyclic digraphs are there on the vertex set $[n]$ with exactly $k$ edges and each indegree, outdegree $\leq 1$? The answer is $${n \choose k} {n-1 \choose k} k!.$$ Is there a ...
1
vote
1answer
130 views

Identity for central binomial coefficients

On Wikipedia I came across the following equation for the central binomial coefficients: $$ \binom{2n}{n}=\frac{4^n}{\sqrt{\pi n}}\left(1-\frac{c_n}{n}\right) $$ for some $1/9<c_n<1/8$. Does ...
13
votes
3answers
430 views

Sum of binomial coefficients

How do I prove the following identity: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$ I am trying to use inclusion-exclusion, and this will boil down to a sum like ...
2
votes
4answers
305 views

Show ${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$

How can we show the following equality? $${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$$
1
vote
1answer
126 views

Binomial Coefficients Problem

I have to evaluate the following but I am not sure how to do it. My professor went over it briefly trying to get it in before the end of the semester but did not explain it very well. I'm not even ...
1
vote
2answers
141 views

How is this equation called?

I'm trying to figure out some math problems. In particular I have this "In an office you have 6 clerks. How many ways can you select a team of 3 clerks?" and the solution given is: $$\binom{6}{3} = ...