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
4answers
29 views

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$ I think I'm having a bit of algebra problem with this proof. Here is my work thus far:$$\frac{n!}{k!(n-k)!}+...
4
votes
1answer
28 views

Show that $2k\choose k$ divides the lcm of $1, \dots, 2k+1$

I want to show that $(2k+1){2k\choose k}$ is a factor of $\text{lcm}(1, \dots, 2k+1)$. Clearly the divisor is equal to $2^k\frac{1\cdot3\cdot\dots\cdot (2k+1)}{k!}$, but I don't know how to show that ...
0
votes
1answer
19 views

calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$

Is there any formula for calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$?
3
votes
2answers
203 views

Find the probability of getting one diamond and one spade in a five-card hand, using binomial coefficients.

A five card hand is dealt at random from a standard $52$ card deck. Let $X = \text{# spades}$ and $Y = \text{# diamonds}$. Find $P(X = 1\text{ and }Y =1)$. Leave your answer as a ratio of products of ...
1
vote
1answer
28 views

Is this true that $\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$ is the coefficient of $t^k$ in $(\frac{1}{1+t})^a(\frac{1}{1-t})^b$

I was reading a paper, in which the author assumed that $$\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$$ is the coefficient of $$t^k $$ in $$\left(\frac{1}{1+t}\right)^a\left(\frac{1}{1-...
1
vote
1answer
45 views

Vandermonde's Convolution special case.

I am not able to show this case of Vandermonde's Convolution without using induction. Can someone help me? $$ \binom{n}{m} = \sum_{k=0}^{m} \binom{n-p}{m-k} \binom{p}{k}. $$ I thank now.
4
votes
4answers
308 views

Sum of sum of binomial coefficients

I know there is no simple way to solve the sum: $$\sum_{k=0}^{j}{{n}\choose{k}}$$ But what about the equation: $$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$ Are there any simplifications or ...
4
votes
1answer
72 views

The sequence $(-1)^n\binom{\alpha-1}{n}$ converges.

I need to show that for $n \in \mathbb N_0$ and $\alpha \ge 0$ the sequence $(-1)^n\binom{\alpha-1}{n}$ converges. It can be shown that the sequence convereges to zero using a theorem claiming that $|...
0
votes
0answers
38 views

Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the answer ...
-3
votes
1answer
75 views

Simple Question on Binomial theorems… [closed]

I have tried to solve this question by putting the value of each coefficients but it is really becoming very lengthy.... what i got was this number 10510100501... But how to get this in the required ...
1
vote
2answers
35 views

binomial coefficient where k > n

For solving binomial coefficients we have use from formula $\frac{n!}{k!(n-k)!}$ This formula only works if n > k. What happens if n < k? Is there another formula we need to use?
34
votes
6answers
745 views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. "So, suppose you had 2 minutes to save your ...
0
votes
0answers
29 views

arranging $n$ objects of one kind and $m$ objects of other kind in a row

Why are there precisely $\binom{m+n}{n}$ ways of arranging $M$ objects of one kind and $N$ objects of other kind in a row?
1
vote
1answer
29 views

Binomial expansion extension to negative powers

I know that: $$\sum_{k=0}^n {n \choose k}a^{n-k}b^k = (a+b)^n$$ But how is this extended to negative powers, for example, I came across the following line of maths, which I struggle to understand: $...
1
vote
0answers
33 views

Logic - Binomial Theorem

I could use some assistance with understanding this problem. I understand that there are ${n}\choose{k}$ is a representation of ${n}\choose{k}$ ways to choose k elements from a set of n elements, ...
3
votes
0answers
39 views

Find the sum of $\binom{2007}{0}+\binom{2007}{4}+…+\binom{2007}{2004}$ [duplicate]

Find the sum of $$S=\binom{2007}{0}+\binom{2007}{4}+\binom{2007}{8}+...+\binom{2007}{2004}$$ My work so far: $$(1+1)^n=2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}$$ $$(1-1)^n=0=\...
1
vote
2answers
44 views

Alternating series of compositions of triangular numbers

I'm modeling a process which involves a subset $S$ of a large number $n_A$ of objects - call them balls. Each time I add a ball to $S$, it may dislodge another ball with probability proportional to ...
2
votes
1answer
22 views

Closed form for binomial sum with absolute value

Do you know whether the following expression has a (nice) closed form or a close enough approximation? $$\frac{1}{2^n}\sum_{k=0}^{n} \binom{n}{k}|n-2k|$$ Thanks a lot :) Cheers, M.
0
votes
0answers
23 views

On a certain series of cosines

For natural numbers $p$ and $q$, compute the value of $$\displaystyle \sum_{k=0}^{q-1} \cos^{p} \left(\dfrac{2\pi k}{q}\right).$$ I got the answer $$\dfrac{q}{2^p} \sum_{l=1}^{p} \binom{p}{l} \...
0
votes
2answers
44 views

Expand $f(x)=\log(x+ \sqrt{1+x^2})$ into power series and determine convergence intervals

We have $f(x)=\log(x+ \sqrt{1+x^2})$ and we need to expand it into power series, which I suppose is easy because $f'(x)=(1+x^2)^{-1/2}= \sum_{k=0} {-\frac{1}{2} \choose k}x^{2k}$. It follows that $f(x)...
6
votes
0answers
68 views

Intuitive explanation of Extended binomial coefficient

We all are familiar with the following formula - $$\dbinom{n}r = \dfrac{n!}{(n-r)! \space r!} \space\space \space ; \space \space n>r$$ This is the binomial formula where $n$ and $r$ are ...
1
vote
3answers
42 views

Stirling on ${2n-1 \choose n}$

I'm trying to find an expression for $${2n-1 \choose n}$$ using Stirling's approximation $$k!\sim \sqrt{2\pi k}(\frac{k}{e})^k.$$ I see $${2n-1 \choose n}\approx \frac{1}{\sqrt{2\pi}}\sqrt{\frac{2n-1}...
0
votes
1answer
24 views

Generating function for multiset formula

It's said that the generating function for $g(x) = \sum_{d=0}^\infty {d+m-1 \choose m-1} x^d$ is equal to $\frac{1}{(1-x)^m}$. In the proof that I have seen it states that: By the geometric series, $...
0
votes
0answers
13 views

Smallest Parameter to Satisfy Exponentially Scaled Binomial Coefficient Inequality

Let $t$ be given, I am mainly interested in large $t$. Define $m(t)$ as below $$ m(t)=\min\left\{m: \sum_{k=0}^m \binom{t+k-2}{k} 2^{t+k} \geq 2^{2t}\right\}. $$ Is there a nice estimate for $m(t)$? ...
2
votes
2answers
57 views

Catalan numbers formula derivation

I'm trying to follow a proof of the Catalan numbers being equal to $\frac{1}{n+1} {2n \choose n}$ from the recurrence relation $C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_{1}+C_{n-1}C_0$ Now it's seen ...
0
votes
3answers
39 views

How to sum binomial coefficients which are multiples of 3? [duplicate]

Basically $\sum_{i=0}^{33}\binom{99}{3i} $ I have read about this thread. I am looking for a conventional approach. Like the one we use in $\sum_{i=0}^{n}\binom{2n}{2i} = 2^{2n-1}$
1
vote
2answers
50 views

The number $\binom{8}{4}$ is equal to the number of subsets of size 4 of the set $\{1, \dots, 8\}$

I was asked to proof if is true and give a counter example if it is false. However I prefer True. since all the numbers 1-8 insides the brackets are in the sets. I'm I correct?
-1
votes
3answers
69 views

Find the middle number in the $29$th row in the Pascal's Triangle

This question is taken from the Singapore Mathematical Olmpiad training notes for Primary school. Find the middle number in the $29$th row of the Pascal's triangle. For example, the middle number ...
0
votes
0answers
40 views

Simpler form of binomial coefficients product

I am trying to find a simpler relation or an approximation of a product of binomial coefficients. This product is given by: $\Pi_{i=a}^{N-1}\binom{N}{i+1}$ Or if there is a starting point towards ...
3
votes
1answer
30 views

Can't Remember a Book about Binomial Sums and Hypergeometry

Some time ago I had come across a website which had the online version of a book about techniques dealing with the solution of sums involving binomial coefficients, and something with the word '...
0
votes
0answers
43 views

Calculating summations concerning binominal coefficients

Since $$\sum_{j=0}^{m}\binom{k}{j}\binom{k}{m-j}=\binom{2k}{m},$$ what is the result of $$\sum_{j=0}^{m}\binom{k}{j}\binom{k}{m-j}(\frac{1}{3})^{j}=?$$ Here $i, j, k, m$ are integers.
2
votes
1answer
44 views

Number of Elements in a Conjugacy Class of $S_N$ (Derivation)

Consider the conjugacy classes of the symmetric group $S_N$. Each conjugacy class consists of permutations that have the same cycle structure. We see that the number of possible cycle structures is ...
1
vote
1answer
34 views

Choosing spread out elements

Is there an explicit formula that I'm missing, for the total number of choices from a set $S = \lbrace 1, 2 , \dots , n \rbrace$ such that for every choice $C \subset S$ the following holds: $\forall ...
4
votes
2answers
129 views

Prove that this system of linear equations generates $\left| \left( \begin{matrix} 1/2 \\ n \end{matrix} \right) \right|$ as a solution?

This infinite system of linear equations: $$ \begin{array}( 2x_1=1 \\ 3x_1+4x_2=2 \\ 4x_1+5x_2+6x_3=3 \\ \cdots \end{array} $$ In other words, this is particular case of a system: $$ \begin{array}( ...
2
votes
1answer
45 views

How to prove that $\binom{X+L-1}{L-1} \ge (X-L\times N)^{L-1}$?

I would like to prove the following expression: $$\binom{X+L-1}{L-1} \ge (X-L\times N)^{L-1}$$ , where $X$, $L$ and $N$ are positive integers. Please help me to prove with the following case. $X\ge L\...
1
vote
2answers
37 views

Proving $\left(\binom{n}{k}\right)=\left(\binom{n-1}{0}\right)+\left(\binom{n-1}{1}\right)+\cdots+\left(\binom{n-1}{k}\right)$

Here, $\left(\binom{n}{k}\right)$ denotes the number of multisets in $N$ with length $k$. I can prove it using the fact that $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$ but I want another access. ...
4
votes
1answer
147 views

Find the coefficient of $x^{19}$ in the expression $(x+1)(x+2)(x+3)\cdots (x+400)$

Find the coefficient of $x^{19}$ in the expression $(x+1)(x+2)(x+3)\cdots (x+400)$ I have no clue how to start. Any kind of help will be appreciated.
6
votes
2answers
71 views

How to prove $p^2 \mid \binom {2p} {p }-2$ for prime $p$?

How to prove $p^2 \mid \binom {2p} {p } -2$ for prime $p$? I have a hint: for $1 \le i \le p-1$, $p \mid \binom p i$. I cannot even start the proof. Please help.
0
votes
3answers
51 views

Combinatorial identity involving binomial coefficients.

In order to conclude a proof (see last equality in B. Poonen's article), I need to establish the following identity: $$\forall (\ell,n)\in\mathbb{N}^2,\ell\leqslant n,\sum_{m=\ell}^n{n\choose m}{m\...
0
votes
1answer
31 views

Double counting proof of binomial problem

The assignment is to prove the following assertion using the method of double counting and explaining which pairs were counted. $$\dbinom{n+1}{k+1} = \sum_{i = k}^{n} \dbinom{i}{k}$$ Left side is ...
3
votes
3answers
64 views

Finding the coefficient of expansion

Question: Find the coefficient of $x^{11}$ in the expansion of:$$(1+x^2)^4(1+x^3)^7(1+x^4)^{12}$$ The traditional way of doing this, as far as I know, is to first find the coefficient of each term ...
0
votes
1answer
31 views

Of Balls in Bins in Different Sections with Caps

Problem: There are $19$ bins: $7, 5, 7$ in the left, centre and right sections respectively. There are $8$ balls, some or all of which are to be put into these bins with the following ...
4
votes
1answer
33 views

Combinatorial identity / expected distance of random walk

I am struggling to verify the following identity. $$\binom{2m}{m} \frac{m}{2} = \sum_{j=1}^m j \binom{2m}{m+j}$$ I've tried induction, but I run into issues inside the sum. I can't see a ...
0
votes
2answers
37 views

Error of Stirling’s approximation for Binomial with central limit theorem

So the question asks: Let $X_n$~Bin(2n,1/2),use Stirling’s approximation for $n!$ to show $P [X_n = n]$~ $1/√(πn)$ as $n→ ∞$, and show the error in the estimate for $P [X_n ≤ n]$, given by the central ...
1
vote
2answers
46 views

Computing the coefficient of $x^n$ in the following expansion

The coefficient of $x^{-n}$ in the expansion of $\frac{2-3x}{1-3x+2x^2}$ is $a.)$ $(-3)^n - (2)^{\frac{1}{2}n -1} $ $b.)$ $2^n + 1 $ $c.)$ $ 3(2)^{\frac{1}{2}n - 1} - 2(3)^n $ $d.)$ None of the ...
0
votes
0answers
40 views

Closed form of a finite sum with binomial coefficients

In general, has $\sum_{k=a}^{b} \binom{n}{k}$ a closed form (with $0\le a\le b\le n$)?
0
votes
3answers
48 views

Check whether or not a triangular number is triangular is the square-sum of two other consecutive triangular numbers

I'm trying to write a program that would tell me whether or not a triangular number, a number of the form $\frac{(n)(n+1)}{2}$ is the sum of the squares of two other consecutive triangular numbers. It ...
0
votes
0answers
26 views

Coefficient of Multinomial kind of expression

How do I find the Multinomial coefficient of expression. For example $(x+y+z+w+6)^8$ let say I want the coefficient of xyzw. I know the answer in the simple case of $(x+3)^5$ , for $x^2$ it will ...
1
vote
2answers
44 views

Is there a name for this combinatorial identity?

I found this identity in a textbook that I own but they did not name the identity and I had some trouble finding it online. Does anyone know the name of the identity and if I can find a resource about ...
4
votes
3answers
181 views

Proving a binomial coefficient identity [duplicate]

I'm having some trouble with the following proof: $$\sum^k_{a=0} {{n}\choose{a}}{{m}\choose{k-a}} = {{n+m}\choose{k}}$$ I'm trying to prove this to learn a couple of things about the Pascal's ...