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

Product of binomial coefficients

Is there any way to simplify given expression ($j$ and $i$ are given, $n\leq \lfloor j/i \rfloor$) $$\prod_{x=1}^n \binom {j-(x-1)i} {i}$$ (e.g. in terms of factorials)? Thanks!
0
votes
1answer
44 views

Black bears and tan-colored bears catching salmon in Alaska

One of popular tourist attractions in Alaska is watching black bears catch salmon swimming upstream to spawn. Not all "black" bears are black, though- some are tan-colored. Suppose that 6 black bears ...
0
votes
0answers
61 views

Permutation and combination identity

Prove that $\displaystyle \sum_{i=0}^n \binom{n}{i}\binom{m+i}{n}=\sum_{i=0}^n \binom{n}{i}\binom{m}{i} 2^i$ for natural numbers $m,n.$ The question doesn't seem to have any direct combinatorial ...
0
votes
2answers
27 views

How can I solve for $n$ in this binomial coefficient equation

How can I solve for $n$ in this binomial coefficient equation? $${n\choose 3} = {n\choose 9}$$ When I try to expand it using factorials, I get a very, very long equation, involving $n-s$ up to $n^6$ ...
1
vote
1answer
57 views

prove that $ \binom n 2 + \binom {n-2} 2 + \binom {n-4} 2 + \dots + \binom 3 2 = \frac 1 {24} (n-1)(n+1) (2n+3) $

$$ \binom n 2 + \binom {n-2} 2 + \binom {n-4} 2 + \dots + \binom 3 2 = \frac 1 {24} (n-1)(n+1) (2n+3) $$ where n is odd. Plesase help mi with that equation.
2
votes
3answers
57 views

combinational proof for $ 1 + 2 + \cdots + n = \binom {n+1} 2 $

$$ 1 + 2 + \cdots + n = \binom {n+1} 2 $$ Please give me a help with combinational proof for this formula. Greetings for everybody and thanks in advance.
0
votes
2answers
33 views

counting the rectangles in nxn square

How many different rectangles can be seen in an $$ n \times n $$ grid like the one shown? Of course the rectangles must be at least one box wide and deep, and squares are allowed. ...
1
vote
1answer
94 views

World series lengths competition, binomial distribution.

Listed in the following table is the length distribution of World Series competion for the 58 series from 1950 to 2008 (there was no series in 1994). WORLD SERIES LENGTHS (note, the total = 58) of ...
2
votes
1answer
102 views

Proof with combinatorial argument

Show with combinatorial argument that this is equal : $$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$ I have no idea how to do that so it would be really helpful ...
2
votes
1answer
38 views

Showing equivalence of two binomial expressions

I wish to show that $\sum_{k=0}^n {n\choose k}(\alpha + k)^k (\beta + n - k)^{(n-k)} = \sum_{k=0}^n {n\choose k}(\gamma + k)^k (\delta + n - k)^{(n-k)}$ given that $\alpha + \beta = \gamma + \delta$. ...
0
votes
0answers
23 views

Choice problem: number of pairs can be formed out of a set with odd cardinality

There are 17 languages (at a meeting) and for every two languages there is one interpreter assigned. The number of pairs we can form out of 17 languages is $\binom{17}{2} = 136$. So 136 interpreters ...
2
votes
4answers
69 views

Prove that $\sum_{k=1}^nk^2{n\choose k}^2=n^2 \binom {2n-2}{n-1}$

Please help me / give a hand with combinational prove for: $$ 1^2 \binom n 1 ^2 + 2^2 \binom n 2 ^2 + \dots + n^2 \binom n n ^2 = n^2 \binom {2n-2}{n-1}$$
1
vote
2answers
48 views

Why does $ \frac{b^n-a^n}{b-a}=\sum_{k=1}^nb^{n-k}a^{k-1}$?

Trying to work through the answer in this question: The inequality $b^n - a^n < (b - a)nb^{n-1}$
6
votes
5answers
421 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
2
votes
4answers
161 views

Proving $ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $ without induction

I have to prove that: $$ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $$ I don't want a complete solution, but only a hint.
2
votes
2answers
47 views

Sums with squares of binomial coefficients multiplied by a polynomial

It has long been known that \begin{align} \sum_{n=0}^{m} \binom{m}{n}^{2} = \binom{2m}{m}. \end{align} What is being asked here are the closed forms for the binomial series \begin{align} S_{1} &= ...
0
votes
0answers
33 views

difference between independent binomial variables

It is well known that if $X \sim B(m, p)$ and $Y \sim B(n, p)$ are independent then $X+Y \sim B(m+n, p)$ but what is the distribution of $X-Y$? Here is what I have tried. $\Pr[X-Y = c] = \sum_{i=0}^n ...
0
votes
3answers
52 views

Alternating sum with binomial coefficients

$\sum_{k=0}^{49}(-1)^k\binom{99}{2k}$ = ? I've tried expanding the binomial coefficient in its factorial form and can't seem to get to manipulate it in a way that solves the expression. ...
0
votes
2answers
34 views

proving counting problems?

Let n >= 1 be an integer. We consider passwords consisting of n characters, each character being a digit or a lowercase letter. A password must contain at least one digit. How do I show that the ...
0
votes
0answers
53 views

How binomial theorem is used in IP distribution?

I have read the binomial theorem/ Pascal triangle that they can be useful for IP ( Internet Protocol) address distribution . However, I am unable to understand it. How it can be applied for IP address ...
2
votes
2answers
112 views

Estimating sum with binomial coefficients

Lately when I was estimating complexity of some algorithm I came across this sum: $$\sum_{k=0}^n \binom {n}{k} \binom {n-k}{k}$$ Is it possible to find a closed-form expression for this sum, or at ...
0
votes
0answers
38 views

How to add binomial coefficients?

How do I add let say $\binom{n-2}{k-2} + \binom{n-2}{k-1}$ What are the steps of adding these together without breaking them down in factorials and add them up?
-2
votes
2answers
91 views

Using Newton's binomial theorem to prove that a sum evaluates to $36^n-26^n$ [duplicate]

Using Newton's binomial theorem to argue that: $n \ge 1$ $$36^n - 26^n = \sum_{k=1}^{n}\binom{n}{k}10^k \cdot 26^{n-k}$$ my argument $$(26+10)^n = ...
0
votes
1answer
35 views

Use Leibniz' formula to show that the $(2n)$th derivative of $(2x^2 + 3x +1)sinx$ is $(-1)^n(2x^2+3x-8n^2+4n+1)sinx+(-1)^{n+1}(8nx+6n)cosx$ wrt $x$

If I let $f=f(x)=sinx$ and $g=g(x)=2x^2+3x+1$ and $D=$ First derivative wrt $x$, $D^2=$ Second derivative wrt $x$ and $D^n=$ $nth$ derivative wrt $x$ then, Leibniz' formula states that $\displaystyle ...
2
votes
3answers
100 views

What is wrong with this calculation of $\binom{\frac{1}{2}}{k}$?

The reason I ask this question is that I want to show that: \begin{equation*} \binom{\frac{1}{2}}{k} = -2\frac{1}{k}\binom{2k-2}{k-1}\left(-\frac{1}{4} \right)^k \end{equation*} \begin{align*} ...
1
vote
3answers
53 views

Yet another sum involving binomial coefficients.

Given $A,B,N \in \mathbb N$ Is there a closed form for this expression? $$\sum_{n=1}^N n \binom{A}n \binom{B}{N-n} $$ If there is such, can you give a proof? EDIT: $A,B \geq N$
13
votes
1answer
206 views

Fitting a closed curve on the roots of ${x \choose k}-c$

Let $${n \choose k} = \frac1{(n+1) \operatorname{B}(n-k+1, k+1)}.$$ be the generalized binomial coefficient, and here $\operatorname{B}$ is the Beta function. Let $f_{k,c}(x)$ be the following ...
1
vote
0answers
19 views

Approximating the max value of a function containing the half-sum of binomial series

I recently met a problem and I have been finding related materials about it. However it is still hard to handle. Precisely, I want to maximize a function related to $$S_n = \sum_{i=0}^{\lfloor ...
0
votes
2answers
44 views

Understanding a combinatorial relation.

I would like some insight as to why the following expression is true. $$\sum_{i=0}^n {{n}\choose{i}} 2^{n-i} = 3^n $$ I arrived at this relation in solving a subset problem, and I understand the ...
1
vote
3answers
40 views

What does this symbol mean in this equation?

I am reading up on n-choose-k problems (Binomial Coefficients). Wikipedia gives a multiplicative solution that is more efficient: I've taken a few calculus courses, and it reminds me of how you ...
0
votes
0answers
35 views

All or no Heads from biased coin tosses

What is the probability that all five tosses of a biased coin with $P(H)=0.28$ are (a) Heads and (b) Tails? (c) What is the probability of at least one Head? (a) Heads $Pr(5\ Heads) = {5 \choose 5} ...
1
vote
1answer
15 views

Prove identity based on binomial theorem

$\displaystyle \sum_{r=0}^{n-1} {2n-1 \choose r} = 2^{2n-2} $ Perhaps it can be proved by using sum of all combinations from r=0 to r=n is 2 to the power of n.
1
vote
2answers
42 views

Alternating sum of a part of a row of Pascal's triangle

$\displaystyle \sum_{r=0}^m(-1)^r{n \choose r}=(-1)^m{n-1 \choose m}$ if $m$ is less than $n$. This question actually consists of two part that is when $m$ is less than $n$ and when $m$ is equal to ...
1
vote
2answers
82 views

Solving equation involving binomial function

Solve for $x$ in terms of $i$ and $j$: $$ \binom{x}{i} = j $$ where $x$ is Real; $i$ and $j$ are Integers: $x \geqslant i$, $i \geqslant1$, $j \geqslant 0$. I came across this problem while trying ...
0
votes
1answer
63 views

Conditions for equality of two binomial sums

Let $k,r,n$ be integers such that $0<k,r<n$. Let $$K=\sum^n_{i=k}k^{n-i}\binom{n-k}{i-k}^2k!(i-k)! \,\text{ and }\, R=\sum^n_{i=r}r^{n-i}\binom{n-r}{i-r}^2r!(i-r)!.$$ How to show that ...
1
vote
1answer
28 views

Prove that $F(N/2;N,x)+F(N/2;N,1-x)=1$ where $F$ is binomial CDF

I have the following claim: $$F(N/2;N,p)+F(N/2;N,1-p)=1$$ where $F$ is a binomial CDF with exactly $N/2$ successes in $N$ total trials, and with each trial having success probability $p$. Is it ...
2
votes
1answer
21 views

How to articulate this expression

I was walking a student through the binomial expansion process and remarked that I prefer Pascal's triangle to generate the coefficients. He also needed to know this way of producing the numbers. ...
1
vote
2answers
112 views

Binomial theorem / Generating function

I had trouble figuring out if the following equality holds by applying the binomial theorem and using generating functions. Could anyone please shed some light? Any help is greatly appreciated. $${n ...
1
vote
1answer
34 views

Variance in offspring genotypes. Binomial distribution

Background Here is first some vocabulary: Diploid: phase in the life cycle where the individuals carry two chromosomes of each type, just like in humans (exception of the sexual chromosomes). ...
1
vote
2answers
56 views

Problem proving $ \sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2} $

I'm stuck at proving the following. $$ \sum_{r=0}^{n-1} \binom{2n-1}{r} = 2^{2n-2} $$ I know that I have to use the Binomial theorem like this, letting x=1,y=1 in $(x+y)^{2n-1}$ $$ ...
2
votes
1answer
54 views

Prove $\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}$

How to prove that $$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ? I tried to break the right ...
0
votes
3answers
36 views

Proving $\sum_i \binom{k}{k-i} \binom{n-k}{i} = \binom{n}{k}$

I am in the middle of a probability question. The question is indeed simple. For the sake of clarity of the notation, I also include the question here, which is from Sheldon M. Ross's Introduction to ...
4
votes
2answers
109 views

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
1
vote
1answer
151 views

Placing m books on n shelves

If we let m and n be integers with $m \ge n \ge 1$. how many ways are there to place m books on n shelves, if there must be at least one book on each shelf? the order matter. How do I solve this, do I ...
0
votes
2answers
44 views

Solve Identity about Combination

Find the values of a and b such that $\binom{2n}{2} = a\binom{n}{2} + b(n^2)$ This is a past year question about Introduction of Combinatorics in my university.
1
vote
2answers
42 views

How many ways can the school choose a President Vice President?

There are n >= 4 students. The school has a Board of Directors, consisting of one president and three vice-presidents. The entire board consists of four distinct students. How can I prove that ...
3
votes
4answers
102 views

Question about ${n+1\choose k} = {n\choose k} + {n\choose k-1}$ proof?

I've found past proofs of this problem and for the most part I'm able to follow. $$\eqalign{{n\choose k}+{n\choose k-1}&= {n!\over (n-k)!k!}+ {n!\over (n-(k-1))! (k-1)!} \text{ (step 1)}\cr ...
2
votes
1answer
68 views

The sum of binomial coefficients up to $k\le n/3$ does not exceed the $k$th coefficient

How would you prove the following (for when $k\leq\frac{n}{3}$)? $$\sum_{i=0}^{k-1} \binom ni \le \binom nk$$
1
vote
1answer
216 views

A urine test, the VMA test

Neuroblastoma is a rare, serious, but treatable disease. A urine test, the VMA test, has been developed that gives a positive diagnosis in about 70 % of cases of neuroblastoma. It has been proposed ...
0
votes
1answer
34 views

Binomial coefficients and order of infinity

Which among $$ \left(2\,k+1 \atop j\right),~~j=1,3,5,...,2\,k+1 $$ has the larger order of infinity when $k\rightarrow\infty$? I am pretty sure that the largest order is reached around $j=k$ but I ...