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
52 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
64 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
483 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
33 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
34 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
47 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
25 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
42 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
72 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
59 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
26 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
22 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
30 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 ...
4
votes
3answers
221 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
74 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
105 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
96 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
67 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
36 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
62 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
65 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
78 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
25 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
88 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 ...
1
vote
0answers
36 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
93 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
133 views
1
vote
3answers
74 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
60 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
33 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
42 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
219 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
64 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
36 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
40 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
56 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
147 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}$$
2
votes
1answer
47 views

In how many ways can four persons each throwing dice once sum up to 13?

I am solving it by finding out Coefficient of $x^{13}$ in $(x+x^2+....x^6)^4$ but I cannot get the correct answer. Please provide me the final answer if method I am following is correct.
1
vote
2answers
34 views

relationship between pascal's triangle and number of combinations?

I was able to solve a classic algorithm question, robot paths by using pascal's triangle (PT). This is where a robot starts in the upper left corner and can only go down or right. I kind of reverse ...
1
vote
0answers
28 views

Determine maximal addend in Newton Binomial Expansion.

Determine the maximal addend in Newton Binomial Expansion of the expression $$\left ( 2n+\frac{1}{2n} \right )^{4n+1},\quad \left ( \forall n \in \mathbb{N} \setminus \left \{ 1 \right \} \right )$$ ...
0
votes
1answer
42 views

Are there four consecutive binomial coefficients in a row in an arithmetic progression?

Are there four consecutive binomial coefficients in a row in an arithmetic progression? This is suggested by Will Jagy's comment to this question: Find $n$ and $k$ if ...
7
votes
2answers
75 views

Find $n$ and $k$ if $\:\binom{n\:}{k-1}=2002\:\:\:\binom{n\:}{k}=3003\:\:$

$$ \:\binom{n\:}{k-1}=2002\:\:\:\binom{n\:}{k}=3003\:\: $$ What are the values for n and k? My initial idea was to divide those two: ...
0
votes
2answers
37 views

how to find the coefficient of $x^t$ in multiplication of series

how to find the coefficient of $x^5$ in $$(1+x+x^2+x^3+.....)(1+x^2+x^4+x^6+.....)(1+x^3+x^6+x^9+....)(1+x^4+x^8+....)$$ Is there any method in general to find the coefficient of $x^t$ in the above ...