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)

4
votes
2answers
61 views

If $n$ is a product of primes, what is the number of divisors?

Let $n=p_1p_2...p_k$ Then the number of divisors is what? I assumed it was $1+ \binom k1+ \binom k2 + \binom k3 + ... + \binom kk=2^k$ Is this correct? Prove that the number of divisors is odd ...
2
votes
2answers
62 views

How do you evaluate this sum of multiplied binomial coefficients: $\sum_{r=2}^9 \binom{r}{2} \binom{12-r}{3} $?

We have to find the value of x+y in: $$\sum_{r=2}^9 \binom{r}{2} \binom{12-r}{3} = \binom{x}{y} $$ My approach: I figured that the required summation is nothing but the coefficient of $x^3$ is the ...
3
votes
1answer
79 views

Number of permuatations such that no two consecutive letters are neither vowels nor identical

Find number of different permutations of all the letters of the word "PERMUTATION" such that any two consecutive letters are neither both vowels nor both identical. The vowels in this word are ...
1
vote
1answer
23 views

Binomial coefficients sum convergens

Find when $\sum_{n=1}^{\infty }\binom{\alpha}{n}$ ($\alpha$ is a real number) diverges, converges, or converges absolutely. First I notice that it is basically ${(1+1)}^{\alpha}$ so the sum ...
1
vote
1answer
46 views

Prove using the binomial theorem that $(1+\frac{1}{n})^n < \sum_{j=0}^n \frac{1}{j!} < 2 + \frac{1}{2} + \frac{1}{4} + …+ \frac{1}{2^{n-1}}$

I understand how to prove this problem, essentially the middle term $\sum_{j=0}^n \frac{1}{j!}$ is equal to the Euler's number, e, and the third term in this sequence is equal to 3. However, I am not ...
0
votes
0answers
27 views

given the polynomial what is the coefficient?

Consider the polynomial $(−3x + 4y)^8$. What is the coefficient of $x^3y^5$ in this polynomial? I need help clarifying this. When I create Pascal's Triangle I get the answer to be 56. Yet when my ...
1
vote
1answer
50 views

Proving an inequality that looks related to the Binomial series,

Edit: I changed the inequality to the one that I think was meant to be asked. This is a former exam question from my math dept, and it is relatively old - from 1993. So, I think there was a typo on ...
3
votes
2answers
60 views

How to make sense of the binomial coefficient over $p$-adic integers?

I recently asked this question: Show that $y^2=x^3+1$ has infinitely many solutions over $\mathbb Z_p$. and now I'm trying to make sense of the first answer that was posted. It said that I should show ...
7
votes
3answers
463 views

After 6n roll of dice, what is the probability each face was rolled exactly n times?

This is closely related to the question "If you toss an even number of coins, what is the probability of 50% head and 50% tail?", but for dice with 6 possible results instead of coins (with 2 possible ...
0
votes
2answers
30 views

Algebra of the Binomial Distribution

I'm reading an economics paper on labour market search which uses the binomial distribution in one of its arguments but with a simplification that I cant quite derive. The idea is this. Suppose that ...
2
votes
1answer
29 views

Generating function, finding coefficient (decomposing)

I just started learning about generating functions, and there is a problem that I have the solution to, but I'm wondering if there is a better general method to solve problems of that kind. If I want ...
0
votes
0answers
44 views

Simple random walk in $\mathbb{Z}^3$

I have the following combinatorial problem. I want to find the probability that a SRW $(X_n)_n$ in $\mathbb{Z}^3$ returns to $0$. So let's consider $2n$ steps. Then we can go in $3$ different ...
0
votes
0answers
20 views

weighted average of quantity with hypergeometric distribution providing the weights

I'm trying to understand some of the details of the following paper: Hauert, et. al., "Via Freedom to Coercion: The Emergence of Costly Punishment," Science, vol. 316, pp. 1905-1907, 2007. In the ...
1
vote
1answer
41 views

Compute $\sum_{k=1}^{22}\binom{21}{k-2}3^k$

I just got to a new material in discrete math and I still cant get a good grasp of the material, if anyone can solve this, it'd be much appreciated. $$\sum_{k=1}^{22}\binom{21}{k-2}3^k$$
5
votes
3answers
71 views

Prove this sum $\sum_{k=0}^{n}(-1)^k\cdot 2^{2n-2k}\binom{2n-k+1}{k}=n+1$

Show that $$\sum_{k=0}^{n}(-1)^k\cdot 2^{2n-2k}\binom{2n-k+1}{k}=n+1$$
1
vote
2answers
40 views

Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
-2
votes
2answers
56 views

Sum of binomial coefficients multiplied by $k^2$

Show the method used to evaluate $\displaystyle\sum\limits_{k=1}^{12} {12\choose{k}}k^2$ The answer is $159744.$
0
votes
0answers
21 views

Estimate $\sum_{\left|\frac{k}{n}-x\right|>\delta}\binom nk x^k(1-x)^{n-k}$

How to establish the following inequality? $$\sum_{\left|\frac{k}{n}-x\right|>\delta}\binom nk x^k(1-x)^{n-k}\leq \frac{x(1-x)}{n\delta^2}$$ where $\delta >0$.
0
votes
0answers
16 views

How many terms (non-simplified) does this polynomial have?

I'm currently doing a homework assignment and am trying to find a correlation between the number of terms the expanded version of a binomial/polynomial has. I haven't yet gotten a formula to find a ...
0
votes
4answers
43 views

The coefficient of $x^3$ in $(1+x)^3 \cdot (2+x^2)^{10}$

Find the coefficient of $x^3$ in the expansion $(1+x)^3 \cdot (2+x^2)^{10}$. I did the first part, which is expanding the second equation at $x^3$ and I got: $\binom {10} 3 \cdot 2^7 \cdot (x^2)^3 = ...
0
votes
1answer
15 views

$A_k=\{(w_1,w_2,…,w_n)\in \Omega^n: w_i=1 \text{ for exactly k indices}\}$ $\implies$ $|A_k|={n \choose k}$

Could someone elaborate how the following implication is seen: $$A_k=\{(w_1,w_2,...,w_n)\in \Omega^n: w_i=1 \text{ for exactly k indices}\}$$ $$\implies|A_k|={n \choose k}$$ where $\Omega = ...
0
votes
2answers
28 views

A different approach in distributing $8$ distinct balls into $6$ distinct boxes

Find the number of ways in distributing $8$ distinct balls into $6$ distinct boxes such that there is atleast $1$ ball in each box. We are well acquainted with the traditional Inclusion Exclusion ...
3
votes
3answers
208 views

How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?

Question: How to prove the following identity? $$ \sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m. $$ I'm also looking for the generalization of this identity like $$ ...
1
vote
2answers
31 views

Find cofficient for $x^n$ for a Generating function

If given a GF $F(x) = \frac{1}{(1-rx)^2}$, how do I find the coefficient for the term $x^n$? I can tell $F(x) = A(x)^2$, where $A(x)$ is the GF for the sequence $1, r, r^2, r^3, r^4, \ldots$ but I ...
2
votes
2answers
61 views

Prove this binomial identity using the following equality:

Use the equation $\frac{(1-x^2)^n}{(1-x)^n} = (1+x)^n$ to prove the following identity: $\displaystyle \sum_{k=0}^\frac{m}{2}(-1)^k{n\choose k}{n+m-2k-1\choose n-1}={m\choose n}$, $m\leqslant n$ and ...
1
vote
5answers
104 views

Why is ${n \choose k} ≥ 1$?

Why is $${n \choose k} ≥ 1$$ I've looked at the expansion of the binomial coefficient, but can't see why the nominator is larger or equal to the denominator.
2
votes
2answers
60 views

How to apply generating series to solve this following enumerative problem?

Background I am a software engineer and I have been picking up combinatorics as I go along. I am going through a combinatorics book for self study and this chapter is absolutely destroying me. Sadly, ...
4
votes
1answer
62 views

Prove the identity Binomial Series

Use $(1-x)^{2n} = (1-x)^n(1-x)^n$ to prove the identity $${2n \choose n} = \sum_k {n \choose k}^2$$ I converted $(1-x)^{2n}$ into a binomial series yielding $$\sum_{k=0}^{2n} {2n \choose k} (-x)^k$$ ...
1
vote
2answers
31 views

Subtracting Unwanted Combinations in a Fish Store Sale

So, I'm working out one of my assignments and I'm a little bit stuck on this problem: A fish store is having a sale on guppies, tiger barbs, neons, swordtails, angelfish, and siamese fighting ...
2
votes
1answer
59 views

Another combinatorial identity of McKay

Suppose $v\ge 2$ and $s\ge 1$ are integers. I'm stuck trying to show that $$ v\sum_{k=0}^{s-1} \binom{2s}{k} \frac{s-k}{s}(v-1)^k = \sum_{k=0}^s \binom{2s}{k} \frac{2s-2k+1}{2s-k+1}(v-1)^k $$ I've ...
3
votes
1answer
55 views

closed form expression for the sum of the first s items of alternating binomial coefficients

Is there a closed form expression for the following sum: $$\sum_{k=0}^s (-1)^k {n \choose k}, $$ where $s \in \{0,1,2,...,n\}$ -- which is basically the first $s$ terms in the alternating binomial ...
1
vote
4answers
76 views

Summation without end value?

$$\sum_{a+n-b=c}\binom{n}{a}\binom{n}{b}$$ What does this mean ? I found it here It is meant to sum up from where to where ?
0
votes
0answers
27 views

Can the binomial coefficient be extended to all scalars?

What would it then mean to "$\pi$ choose $e$? Is there a unique way to do it? Does it have a practical application?
0
votes
0answers
24 views

Inequality for the binomial coefficient $\binom{n}{k}\leqslant\frac{2^{nH(\frac{k}{n})}}{\sqrt{2\pi k(n-k)/n}}$

Here $H(x)=-x\log_2(x)-(1-x)\log_2(1-x),\space x\in(0,1),\space H(0)=H(1)=0$ is the entropy function. I was trying to prove this inequality using the following bounds for factorial: $\sqrt{2\pi ...
1
vote
1answer
78 views

What is $\lfloor(\sqrt 3 +1)^5\rfloor$? (without a calculator)

The question states: Let $[x]$ be the greatest integer less than or equal to $x$. If $x=(\sqrt 3 +1)^5$, then $[x]$ is equal to $75$ $50$ $152$ $151$ When I punch it out in the ...
0
votes
0answers
30 views

Very odd binomial coefficients

The number of odd binomial coefficients in each row of Pascal's triangle is always a power of two although their sum rarely is. One of these rare occasions occurs for numbers of the form $\,$$n = 2^m ...
1
vote
3answers
87 views

Prove $\sum_{i=0}^n {{n \choose i} \times 2^i} = 3^n $ [duplicate]

I have to prove that $$\sum_{i=0}^n {{n \choose i} \times 2^i} = 3^n $$ Such that ${n \choose i} = \frac{n!}{i!(n-i)!} $ and $n $ is some arbitrary int I proved we can expand 2^I in a way such that ...
1
vote
4answers
121 views
1
vote
3answers
68 views

Finding $\binom n0+\binom n3+\binom n6+\cdots $ [duplicate]

How to get $$\binom n0 + \binom n3 + \binom n6 + \cdots$$ MY ATTEMPT $$(1+\omega)^n = \binom n0 + \binom n1 \omega^1 + \binom n2 \omega^2 + \cdots$$ $$(1+\omega^2)^n = \binom n0 + \binom n1 ...
2
votes
1answer
45 views

Summation involving binomial coefficients

I came across the following sum online and have spent awhile trying to compute it: $$\sum_{i=0}^{100} \binom{300}{3i}$$ Based on a pattern I noticed, the answer should be $\frac{2^{300}}{3}$ rounded ...
0
votes
0answers
32 views

Prove:$\sum\limits_{k=0}^{n}\frac{(-1)^k{n\choose k}}{k+1}=\frac{1}{n+1}$ [duplicate]

Prove:$\sum\limits_{k=0}^{n}\frac{(-1)^k{n\choose k}}{k+1}=\frac{1}{n+1}$ I tried to prove the equation by induction, but can't find the relation between $\sum\limits_{k=0}^{m}\frac{(-1)^k{m\choose ...
1
vote
1answer
39 views

A recursion similar to the one for Bernoulli numbers

For the Bernoulli numbers $B_m$, there is a recursion: $B_0=1$ and $\sum_{j=0}^{m-1}\binom{m+1}{j}B_j=-(m+1)B_m $ for $m\ge 1$. It is known that $B_{m}=0$ when $m\gt 1$ is odd. Now, ...
3
votes
1answer
214 views

Prove identity without using complex numbers

How to prove the following identity without using complex numbers (and de Moivre's formula)?
1
vote
2answers
41 views

prove the formula and then evalute the sum

m,n,r are given non-negative integers, show that $\sum_{k>=-n}$ ${r \choose m+k}$ ${s \choose n+k}$ $=$ ${r+s \choose r-m+n}$ Then evaluate $\sum_{k>=0}k$ ${r \choose k}$ ${s \choose k}$ I ...
3
votes
0answers
61 views

How to evaluate: $\int_0^1x^{n-1}(1-x)^{n+1}dx$

How can I evaluate the following integral? ($n \in R$, $n>0$) $$\int_0^1x^{n-1}(1-x)^{n+1}dx$$ I was solving the following problem (as practice) in school: Prove that the sum of $n+1$ terms of ...
3
votes
1answer
35 views

The sum of binomial coefficients $\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}$

Prove by induction: $$\sum_{i=1}^n \binom{i}{2}= {n+1 \choose 3}$$ I already know that: $$\sum_{i=1}^n \binom{i}{2} = {i+1 \choose 2+1}$$ And the LHS is now equal: $$\sum_{i=1}^n \binom{i}{2} + ...
1
vote
3answers
33 views

prove that $(\frac{1}{6})^{4}\cdot\lim_{n\rightarrow\infty}\sum_{i=4}^{n}\binom{i-1}{3}(\frac{5}{6})^{i-4}=1$

I have to prove the following: $(\frac{1}{6})^{4}\cdot\lim_{n\rightarrow\infty}\sum_{i=4}^{n}\binom{i-1}{3}(\frac{5}{6})^{i-4}=1$ any ideas? thanks
1
vote
1answer
34 views

GCD of binomial coefficients of the form ($p^n$ choose $k$)

Let $n$ be a positive integer and $p$ be a prime. Find the greatest common factor of $\binom{p^n}{1}, \binom{p^n}{2},...,\binom{p^n}{p^n-1}$. Progress: We know that for any given $n$ and $k$ in ...
0
votes
1answer
37 views

Equating coefficients of binomial expansion modulo p

In this answer: http://math.stackexchange.com/a/652909 Ted equates mod $p$ the coefficients of $$\sum_{n=0}^{pa} \binom{pa}{n} x^n$$ and $$\sum_{i=0}^{a} \binom{a}{i} x^{pi}$$ to get that ...
2
votes
1answer
139 views

Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$

How to find this alternating sum of binomial coefficients? $$\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$$