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)

3
votes
2answers
38 views

show that these two equation holds by binomial theorem

I know the binomial theorem, but I have no idea how to simplify this. I tried to write it as (y+x)^n+(y+x)^n-(y+x)^0+(y+x)^n-(y+x)^1+...+(y+x)^n-(y+x)^(n-1), but it didnt work out.
1
vote
1answer
402 views

Binomial Distribution - independence

I have the following problem that I'm stuck on a few parts. ...
3
votes
2answers
113 views

Evaluate the summation involving binomials.

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$ I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.
0
votes
1answer
120 views

Function returning number of subsets of size $k$ of a set of size $n$.

I am looking for a function that returns the number of subsets of size $k$ of a set of size $n$. Ideally, the function is commonly used. I took a look at the binomial coefficient. However, there ...
2
votes
0answers
55 views

find the the variable that maximizes a function

I have a function that I am trying to find for what input it maximizes. $$ f(n) = {\binom{S}{2}}^{n/S}$$ I need to find the $S$ for which this function maximizes (for infinite $n$). more generally, ...
0
votes
0answers
171 views

Solving sample size of hypergeometric distribution given a specific probability

I am trying to figure out how to calculate the sample size of a hypergeometric distribution, given a population, population successes, and probability. Here is the initial formula: ...
1
vote
1answer
42 views

In a lottery of $90$ numbers a man adds extra $1,2,3$

Consider a lottery where $5$ balls are chosen randomly among $90$ balls numbered from $1$ to $90$. A man cheats adding to the $90$ balls, before the draw, three more balls numbered $1,2,3$. We say ...
4
votes
3answers
192 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
2
votes
3answers
105 views

Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following: If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$. I did the following steps: \begin{align} ...
0
votes
0answers
33 views

Approximation of sum with binomial summands

I am new here, so hopefully my question will be understood correctly. I have a function (originating from expected untility theory in economics) that looks the following: ...
3
votes
3answers
81 views

Prove $\sum\limits_{r=0}^{2n} r \binom{2n}{r}^2 = 2n \binom{4n-1}{2n}$

I expanded $(1+x)^{2n}$ = $\sum\limits_{r=0}^{2n} \binom{2n}{r} x^r $ Differentiating both sides, we get $2n(1+x)^{2n-1}$ = $0$ + $\binom{2n}{1}$ + $2\binom{2n}{2}x$ + $3\binom{2n}{3}x^2$ ..... ...
7
votes
2answers
305 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
3
votes
1answer
49 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
2
votes
1answer
44 views

binomial identity involving sum of diagonal elements

It's well-known and easy to show that $\binom{k}{n} = \frac{k}{n}\binom{k-1}{n-1}$. Also, I've come across the formula $\binom{k}{n}=A\binom{k-1}{n-1}+B\binom{k-2}{n-2}$, where $A$ and $B$ are ...
3
votes
1answer
98 views

How find this sum $\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{(-1)^k\binom{n-k}{k}}{n-k}$

How find this sum $$\sum_{k=0}^{\left[\dfrac{n}{2}\right]}\dfrac{(-1)^k\binom{n-k}{k}}{n-k}$$ My try:since $$\dfrac{(-1)^k}{n-k}=\int_{-1}^{0}x^{n-k-1}dx$$ then I can't Thank you very much!
2
votes
2answers
116 views

find the coefficient of the given term when the expression is expanded by the binomial theorem

I am just trying to understand why the term is $\binom{15}8$(3p$^2$ - 2q)$^7$. I need to find the coefficient in $p^{16}q^7$ in $(3p^2 - 2q)^{15}$ So, I know that $n = 15$ and I have $a^{n - k}b^k$ ...
1
vote
1answer
39 views

I want to prove this identity involving the binomial coefficients

Can you help me prove the following identity? I know it holds because I simulated it. For positive integers $n,m,k$ and for $i=0,\ldots,n$ and for $n \leq m$ we have: $$\sum_{j=0}^i (-1)^{i+j}\binom ...
0
votes
1answer
36 views

Remarkable and odd property, why is $\sum_{k=1}^i(-1)^{(i+k)}\text{ }^iC_kk^j= 0$ for $i>j$

At A-level I'd have regarded this as "why I like maths" because it worked, but now I look at it and think "It doesn't look like it should work" and question that. I am showing $$\sum^m_{k=1}\text{ ...
5
votes
2answers
107 views

Partial fraction expansion of $\frac{1}{x(x+1)(x+2)\cdots(x+n)}$

I try to find a partial fraction expansion of $\dfrac{1}{\prod_{k=0}^n (x+k)}$ (to calculate its integral). After checking some values of $n$, I noticed that it seems to be true that ...
3
votes
1answer
267 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot ...
0
votes
1answer
55 views

Conditions for which $n | {n \choose k}$ for all $k$

I'm studying for a number theory exam. Our review sheets offers the question: Under what conditions will $n$ divide $n \choose k$ for all 1 $ \leq k \leq n-1$? I can see that this will be true for ...
6
votes
1answer
299 views

Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

English translation. You can see the original - deprecated - in Portuguese here Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This ...
1
vote
1answer
83 views

Gambler's ruin, probability of loss, infinite turns

A gambler starts with $\$1$ and bets $\$1$ every turn of a game, where he has the probability $p$ to obtain $\$2$ and $1-p$ to obtain nothing. If $p<1/2$, what is the probability he will eventually ...
0
votes
1answer
34 views

Binomials for getting probability of standard deviation

I have the following problem which I am stuck on the second part. Suppose that $30\%$ of all students who have to buy a text for a particular course want a new copy whereas the other $70\%$ want a ...
2
votes
1answer
71 views

Concrete Mathematics, Newton Series and Inversion

In section 5.3 of Concrete Mathematics, on the bottom of page 192, "A special case of the rule (5.45) we've just derived for Newton's series can be rewritten in the following way:" $g(n) = ...
0
votes
1answer
65 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. ...
2
votes
0answers
41 views

Sum of Binomials times Logarithms

Is there a closed-form expression or a very good approximation for $$ \sum_{i=0}^n \binom{n}{i} \log (i+1) \,? $$ If the summands alternate, then there is a very close approximation, yet it feels ...
2
votes
1answer
44 views

Integer valued polynomials in two variables

The ring of integer valued polynomials, $\{ f \in \mathbb{Q}[x] : f(\mathbb{Z}) \subseteq \mathbb{Z} \}$ is fairly well-known to be generated as Abelian group by the binomial coefficients, $f_k(n) = ...
3
votes
3answers
137 views

Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ [duplicate]

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = ...
2
votes
3answers
191 views

Probability of 5 cards drawn from shuffled deck

Five cards are drawn from a shuffled deck with $52$ cards. Find the probability that a) four cards are aces b) four cards are aces and the other is a king c) three cards are tens and ...
2
votes
1answer
84 views

Using combinatorial reasoning to show $n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\dots+\binom{n}{n}D_0$

How can one use combinatorial reasoning to show that $$n!=\dbinom{n}{0}D_n+\dbinom{n}{1}D_{n-1}+\dbinom{n}{2}D_{n-2}+....+\dbinom{n}{n-1}D_1+\dbinom{n}{n}D_0$$ Now $D$ stands for deranged which is a ...
5
votes
5answers
273 views

Asymptotic behavior of $\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k$

I am looking to show that $$\lim_{n \rightarrow \infty}\frac{1}{e^n}\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k = 0. $$ In my application, $c = (e+1)/2 \approx 1.85914\ldots$. I have been ...
3
votes
2answers
127 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?
2
votes
4answers
107 views

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ [closed]

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
0
votes
0answers
62 views

Estimation for sum over binomial coefficients

I am trying to show that a certain procedure for resource allocation is approximately efficient. For this I need to show that $$ \lim_{n\rightarrow \infty} \left(\frac{1}{e}\right)^n\sum_{c=2}^n ...
1
vote
2answers
389 views

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean ...
0
votes
7answers
171 views

$\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$

Show that $\,\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to ...
0
votes
1answer
32 views

Strictly increasing maps

For $p\ge n$, how many strictly increasing maps from $N^*_n$ to $N^*_p$ do exist, where $N^*_n = \{1, 2, \dots, n\}$ is the set of the first $n$ integers greater than 0 ? My answer: uncountable many. ...
0
votes
0answers
45 views

Moment generating function with binomial coefficients

I am trying to calculate a moment generating function, and I have obtained the following result: \begin{equation} ...
7
votes
2answers
164 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
3
votes
2answers
127 views

how to prove $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ without induction?

$$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$$ how to prove it without induction? I tried with several way but I failed anybody help me ?
3
votes
2answers
127 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
0
votes
1answer
46 views

Binomial Theorem Identity

Using the binomial theorem, derive the following identity: $\dbinom{n}{0} - \dbinom{n}{1} \frac{1}{2} + \dbinom{n}{2} \frac{1}{4} - ... \pm \dbinom{n}{n} \frac{1}{2^n} = \frac{1}{2^n}$ It is easy to ...
3
votes
0answers
41 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
2
votes
1answer
45 views

Try to solve Binomial Distribution

I just got a problem related to binomial distribution as following. Which value of $k$ makes $\left(\begin{matrix}n \\ k\end{matrix} \right)p^k(1-p)^{n-k}$ as large as possible? I've spend hours ...
1
vote
3answers
75 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
8
votes
2answers
257 views

Computing the last non-zero digit of ${1027 \choose 41}$?

I am working on the following problem: Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + ...
2
votes
1answer
295 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
2
votes
1answer
108 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
3
votes
3answers
165 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$