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)

5
votes
4answers
251 views

Finding coefficient of polynomial?

The coefficient of $x^{12}$ in $(x^3 + x^4 + x^5 + x^6 + …)^3$ is_______? Somewhere it explain as: The expression can be re-written as: $(x^3 (1+ x + x^2 + x^3 + …))^3=x^9(1+(x+x^2+x^3))^3$ ...
1
vote
3answers
64 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
votes
0answers
19 views

Updating array and counting permutations with some criteria [on hold]

We have an array $A[n]$, and an integer $D$. $P$ is a permutation of numbers $[1 2 3 .... n]$ $P$ is a valid permutation if $$ A[P_1]+D>A[P_2] $$ $$ A[P_2]+D>A[P_3] $$ $$ .... $$ $$ ...
0
votes
0answers
22 views

Bounding the summation of binomial terms

For $0<\theta<1, \theta'=(1-\epsilon)\theta, \epsilon< \theta, k\in\mathbb{N}$, the problem is to tightly upper bound the following binomial summation: $$\sum_{i=\lceil \theta k \rceil}^k ...
1
vote
2answers
30 views

Representing geometric series as sum of binomial coefficients

I was learning generating functions, where faced following: $$(1-x)^{-n}=\sum_{i=0}^\infty\binom{n+i-1}{i}x^i$$ I didn't get how is this arrived. I tried out to prove this to me. But failed. ...
4
votes
2answers
100 views

Finding the infinite series: $\sum_{m=0}^\infty\sum_{n=0}^\infty\frac{m!\:n!}{(m+n+2)!}$

Evaluating $$\sum_{m=0}^\infty \sum_{n=0}^\infty\frac{m!n!}{(m+n+2)!}$$ involving binomial coefficients. My attempt: $$\frac{1}{(m+1)(n+1)}\sum_{m=0}^\infty ...
2
votes
0answers
48 views

upper bounding alternating binomial sums

So we know that $\sum_{i=0}^t\binom{m}{i}\binom{n-m}{t-i}=\binom{n}{t}$ by a simple counting argument. Now is there any bound on the quantity $\sum_{i=0}^t(-1)^i\binom{m}{i}\binom{n-m}{t-i}$? Can we ...
0
votes
5answers
76 views

How to find a simplified expression for $\binom{1/2}{n}$? [on hold]

How to find a simplified expression for this specific binomial coefficient? $$\binom{\frac{1}{2}}{n}$$
4
votes
2answers
456 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 ...
13
votes
12answers
739 views

Show that $ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$

I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$ Thanks in advance for any help.
1
vote
1answer
393 views

Binomial Distribution for defects

I'm stuck on the following problem: A batch of components has arrived at a distributor. The batch can be characterized only if the proportion of defective components is at most 0.10. ...
0
votes
2answers
31 views

Question about Binomial Distribution

The chance of a rose flower blooming is $.28$. You are going to plant $5$ rose flowers, what are the chances of $4$ of them blooming? I was thinking the answer would be $35$% since $28\%*5=140$ and ...
2
votes
0answers
32 views

Showing a relation between binomial and negative binomial analytically

If $X$ is binomial random variable $B(n,p)$ and Y is negative binomial $(r,p)$, How can I show that $F_X(r-1) = 1- F_Y(n-r)$. While it is possible to show that using the definition of binomial and ...
1
vote
1answer
72 views

On a “coincidence” of two sequences involving $a_n = {_2F_1}\left(\tfrac{1}{2},-n;\tfrac{3}{2};\tfrac{1}{2}\right)$

This was inspired by this post. Define, $$a_n = {_2F_1}\left(\tfrac{1}{2},-n;\tfrac{3}{2};\tfrac{1}{2}\right)$$ $$b_n = \sum_{k=0}^n \binom{-\tfrac{1}{2}}{k}\big(-\tfrac{1}{2}\big)^k$$ where ...
5
votes
2answers
720 views

Number of monomials of certain degree

Wikipedia says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
1
vote
1answer
23 views

Summation of series with binomial coefficients

The value of $$\sum {n\choose n-r} (n-r) \sin(r\cdot \pi/n)$$ where $r\in (0 ..,n)$ is equal to? I think the question can be solved by writing the series in reverse order but I am not able to solve ...
0
votes
1answer
46 views

find a value in pascal triangle given row and column

How can I find a value from this pascal triangle given row and column number without calculating $^nC_r$? For example, for row=$4$, column=$3$: value is $10$, For row=$3$, column=$5$: value is ...
1
vote
0answers
40 views

For any given $k$, show that an integer $n$ can be represented as: $n={m_1 \choose 1} + {m_2 \choose 2} + \cdots + {m_k \choose k}$

For any given $k$, show that an integer $n$ can uniquely be represented as: $$n={m_1 \choose 1} + {m_2 \choose 2} + \cdots + {m_k \choose k}$$ where $0 < m_1 < m_2 < \cdots < m_k$. My ...
1
vote
0answers
17 views

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$ [duplicate]

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$. Typically to combinatorially prove something we need to show that the LHS indeed counts the same ...
0
votes
1answer
25 views

Using Pascal's formula to derive another formula

Use Pascal’s formula repeatedly to derive a formula for $\dbinom{n+3}{r}$ in terms of values of $\dbinom{n}{k}$ with $k \leq r.$ (Assume $n$ and $r$ are integers with $n\geq r \geq 3).$ I have a idea ...
1
vote
1answer
66 views

Prove ${20n \choose 10n}\ge {2n-1 \choose n-1}^{10}$

As the title says, I can't prove that, no matter what I try. What I've tried so far: induction: seemed the most obvious method, since we already had a lot of tasks with it, but using the esimates ...
2
votes
2answers
7k views

How many solutions are there to the equation $x + y + z + w = 17$?

How many solutions are there to the equation $x + y + z + w = 17$ for non-negative integers $w, x, y, z$ ? I don't know if I'm doing this right, but I guessed that the solution would be ...
5
votes
1answer
115 views

How do you find the probability of A winning if the probability of getting a favourable outcome in the $r^{th}$ turn is a function of $r$?

Problem: Two players A and B are playing snake and ladder. A is at 99 and he needs 1 to win in rolling of a dice. However, he is always allowed to re-throw the dice if 6 appears. What is the ...
17
votes
5answers
1k views

Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$ For the first one, I was able to express $k^2$ in terms of the binomial coefficients by ...
-1
votes
1answer
41 views

Prove that $\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^m=…$ [closed]

Let $\binom{n}{k}$ denotes the number of subsets with $k$ elements in $n$-elements set. Prove that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^m=\begin{cases} 0, & \text{ if } 0\le m \le n-1; \\ 2^n ...
-2
votes
1answer
35 views

How to get from left to right-hand side of the equation? $ \sum_{k=0}^{d} \binom{2d+1}{k} = \frac{1}{2} \cdot 2^{2d+1} $

I would like to know how the left hand side of the equation is achieved. In particular why the $\frac{1}{2}$ is there. I don't understand how one can get from the left to the right side. $$ ...
3
votes
1answer
60 views

Product of sums into a sum of products

Any idea on how I can get an expression in the form of sum of products from the following one?: \begin{equation} \prod_{i=1}^M \left(\sum_{n=1}^i x_n\right) \end{equation}
0
votes
2answers
38 views

what is the n-k derivative of $x^n$? Also, why is $n!/k! = …$

I am having troubles finding $\frac{d^{n-k}x^n}{dx^{n-k}}$ where $ k \leq n$ I believe it is equal to $n(n-1)(n-2)....k(k+1)x^k$ but htis is just from obersation, I do not know why it's that exactly. ...
0
votes
1answer
33 views

Use induction and Pascal's Identity to show that $\sum_{k=0}^{r}C(n+k,k) = C(n+r+1,r)$

I know Pascal's Identity is ${n \choose k}={n-1 \choose k-1}{n-1 \choose k}$, but I am not sure how to set up and use the proof to show that $\sum_{k=0}^{r}C(n+k,k) = C(n+r+1,r)$. Can anyone help me ...
-1
votes
5answers
70 views

Give a proof of ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + … + {n \choose n}^2 = {2n \choose n}$ [duplicate]

I must prove this: ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + ... + {n \choose n}^2 = {2n \choose n}$ But, I have no idea how to prove it or how it necessarily works. Could someone help ...
26
votes
6answers
10k views

Proof that a Combination is an integer

From its definition a combination $\binom{n}{k}$, is the number of distinct subsets of size $k$ from a set of $n$ elements. This is clearly an integer, however I was curious as to why the expression ...
0
votes
1answer
42 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
2
votes
2answers
61 views

What is the coefficient of $x^4$ in the expansion of $\sqrt[3]{1+x}$

Here's what I tried: $$\sum_{n \ge0} {\frac{1}{3} \choose n} x^n= \sum_{n \ge0} = \frac{\frac{1}{3}!}{n!(n-\frac{1}{3})!}x^n=\sum_{n \ge0} \frac{(\frac{1}{3}-1)(\frac{1}{3}-2)\cdot ...
0
votes
2answers
40 views

Give a formula for the coefficient of $x^{k}$ in the expansion of $(x+{1 \over x})^n$

I followed the binomial theorem and got this: The Binomial Theorem is: $(a+b)^{n}= \sum_{k=0}^{n} {n \choose k}{a}^{k}{b}^{n-k}$ Then let $a=x, b={1\over x}, n = n, k = k.$ I then get ...
4
votes
1answer
618 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
4
votes
5answers
159 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
1
vote
1answer
55 views

Gaussian polynomial identities

I'd appreciate any hints for showing that these identities are true for Gaussian polynomials. I've tried to approach the problem using basic algebra but it gets messy very quickly and I've gotten ...
1
vote
1answer
35 views

What is this matrix notation and how is it solved?

I've never taken a stats class, or linear algebra or much of anything that involves matrices. In one of my books they give me this as part of an example and it states, $$\binom{6}{4} = 15 \text{ ...
1
vote
3answers
76 views
3
votes
3answers
97 views

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

The following sum came up in a combinatorial argument. I know what it equals thanks to Wolfram Alpha, but I'm not sure how to show it $$\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$$
7
votes
2answers
271 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 ...
0
votes
1answer
36 views

Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 2016$

$(1)$ Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 120$ $(2)$ Evaluation of all positive integer ordered pair $(n,r)$ for which ...
6
votes
2answers
180 views

summation of a binomial expression that doesn't start from 0

I have the following expression: $$ \sum_{k=9}^{17}\binom{17}{k} $$ and I need to show that it's equal to: $$ 2^{16} $$ now I know that if 'k' was starting from zero and not from 9 , like this: $$ ...
2
votes
0answers
29 views

Simplify binomial coefficients sum [duplicate]

Exercise requires to simplify this sum: $$\sum_{k=0}^{20} \binom{50}{k}\binom{50}{20-k}$$ Tried to figure this out with no success. I have only final answer, which is $\binom{100}{20}$. Please help ...
4
votes
3answers
68 views
0
votes
2answers
42 views

Simplify the sum of binomial coefficients

The exercise requires to simplify the following expression: $$\sum_{k=0}^{25} \binom{50}{2k}$$ By finally looking at someone's answer, I know that the result should be $2^{49}$, but the following ...
1
vote
1answer
25 views

Binomial distribution, explanation formula

I have a really simple question. I can't figure out the meaning of the binomial coefficient in the case of a binomial distribution formula. I know what the formula means, and how to use it for the ...
3
votes
3answers
54 views

how to come up with this identity $\sum\limits_{i=r}^{n-k+r}{i \choose r}{{n-i} \choose {k-r}}={{n+1} \choose {k+1}}$

This identity is used in an exercise. Could you help me understand how I should reason to come up with it? Ideally, from a combinatorial point of view.
0
votes
3answers
89 views

Binomial coefficient problem

I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this? I need to write this expression in a more simplified way: ...
2
votes
1answer
48 views

Prove that $\frac{(2n)!}{(n!)^2}-1$ is divisible by $(2n+1)$

Prove that $$\frac{(2n)!}{(n!)^2}-1$$ is divisible by $(2n+1)\;,$ Where $n\in \mathbb{N}$ and $n>1$ $\bf{My\; Try::}$ Let $$S = \frac{(2n)!}{n!^2}-1 = \frac{2^n(2n-1)(2n-3)\cdot \cdot ...