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)

2
votes
1answer
35 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that ${-1\choose 0}=1$?

I'm trying to use the binomial coefficient: $$\binom{x}k=\begin{cases} \frac{x^{\underline k}}{k!},&\text{if }k\ge 0\\\\ 0,&\text{if }k<0\;, \end{cases}$$ To check that ${-1\choose 0}=1$. ...
1
vote
1answer
20 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that $ {-n \choose -n}=0$?

I am trying to use this definition of the binomial coefficient: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-[k-1])}{k(k-1)(k-2)\cdots 1}$$ To ...
1
vote
1answer
63 views

Why $ {-1\choose 3}=-1$?

Having the following definition: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}\tag{1}$$ Why $\bbox[1px,border:1px ...
0
votes
2answers
46 views

Sum of binomial coefficients $\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$

$$\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$$ I can't find the sum of the following series. I would appreciate if anyone can show me this problem's solution.
6
votes
2answers
61 views

Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?

This is exercise number $57$ in Hugh Gordon's Discrete Probability. For $n \in \mathbb{N}$, show that $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ My algebraic solution: ...
4
votes
4answers
138 views

Combinatoric proof for $\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$ ($n\geqslant5$)

I'm trying to proove the following: $For\space every\space n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$ I've tried cancelling one $(n-k)$, and got this: ...
25
votes
1answer
623 views

X'mas Combinatorics

Inspired the various** algebraic X'mas greetings sent to me over the festive period, I thought I would try to devise one of my own. $$\Large ...
4
votes
6answers
114 views

How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to ...
1
vote
3answers
46 views

If a word appears with probability $0.05$, how many words are needed so that it appears with probability $0.99$?

Probability of a specific word appearing in a language is $0.05$. How many words must there be in a text, so that the word appears at least once with a probability of $0.99$? My understanding is ...
-3
votes
2answers
34 views

for which : $a_{n}$ and $b_{n}$ , $p_{n}=a_{n}x^{n+1}+b_{n}x^n+1$ to be dividing by $(x-1)²$? [on hold]

let $n \in \mathbb{n^*}$ ,set the real ensembles : $a_{n}$ and $b_{n}$ which the polynomial : $p_{n}=a_{n}x^{n+1}+b_{n}x^n+1$ dividing by $(x-1)²$ and deduce the Quotient $Q_{n}$ ? Thank you ...
1
vote
2answers
115 views

What is the value of $\sum_{n=0}^{\infty}(-\frac{1}{8})^n\binom{2n}{n}$

What is the value of $$\sum_{n=0}^{\infty}\left(-\frac{1}{8}\right)^n\binom{2n}{n}\;?$$ EDIT I bumped into this series when inserting $\overrightarrow{r_1}=\left(\begin{array} ...
3
votes
1answer
62 views

Good approximation for $\binom{N}{\frac{N}{2}}$

$$\log_2\binom{N}{\frac{N}{2}}\approx N\log_2N - 2(N-\frac{N}{2})\log_2(N-\frac{N}{2})=N\log_2N - 2\frac{N}{2}\log_2(\frac{N}{2})$$ $$=N\log_2N - {N}{}\log_2({N}) + {N}{}=N$$ ...
6
votes
1answer
41 views

An identity involving partial fractions decompositions

In Vladimir A. Smirnov's book Analytic Tools for Feynman Integrals (page 38), the following identity is suggested to perform partial fractions decompositions $$ \begin{split} ...
3
votes
0answers
46 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
0
votes
1answer
15 views

expressing canonical base of univariate polynomials in binomial base

Two bases are fairly standard for ${\mathbb Q}[X]$ : the canonical base $(X^j)_{j\geq 0}$ and the binomial base $(b_j(X))_{j\geq 0}$ where $b_j(X)=\binom{X}{j}=\frac{X(X-1)\ldots (X-(j-1))}{j!}$ (thus ...
2
votes
2answers
92 views

Binomial theorem.

I first saw this thing (admittedly much to late in life) in a third year class entitled non-linear dynamics and chaos theory. There if i am remembering correctly we used to look for non-zero terms to ...
0
votes
4answers
63 views

How to prove that the sum of binomials equals $\begin{pmatrix}2n\\n\end{pmatrix}$ [duplicate]

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem to ...
-2
votes
0answers
92 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this : [duplicate]

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
-3
votes
3answers
117 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of [on hold]

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
2
votes
2answers
41 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
11
votes
1answer
112 views

How find all postive integer number such $(n+k)\nmid \binom{2n}{n}$

Question: Find the all integer $k$,such there are exist infinitely many $n$ such $$(n+k)\nmid \binom{2n}{n}$$ This is china 2014 (CMO problem 4),it's have been end exam three hours ago. I ...
6
votes
1answer
134 views

How to transform the product to sum?

I just wonder that how to prove that $$ \prod_{m=1}^{n}\Big(x-2\cos\frac{m\pi}{n+1}\Big)=\sum_{k=0}^{[n/2]}(-1)^{k}\binom{n-k}{k}x^{n-2k}. $$ Similarly, how to transform the product $$ ...
0
votes
1answer
53 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...
3
votes
3answers
237 views

Is there a closed-form formula for sum of “odd combinations”? [closed]

So, I was trying to come with a formula for the sum of below series: ${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$ Thank you.
1
vote
1answer
22 views

What can you conclude about the first moment of a variable given the 3rd moment exists and is finite

Suppose you are given a random variable $X$ and told that $E[X^3]$ exists and finite. Can you conclude that $E[X]$ exists and is finite? What about $E[X^2]$? How would you argue rigorously whether ...
6
votes
4answers
1k views

Probability that given a 1000 page book with 1000 misprints, a page will have 3 misprints.

Setting A book of 1000 pages contains 1000 misprints. Estimate the chances that a given page contains at least three misprints. Solution My solution is ...
4
votes
2answers
54 views

Simplifying $\sum_{j=k}^{n}\binom{j}{k}/(2^{k-1})$

While doing an exercise (computing an expected value), I encountered an expression that looks like this. Is there a simpler formula? $$ \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} $$ If it wasn't ...
7
votes
6answers
334 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
0
votes
4answers
44 views

Proving a formula with binomial coefficient

Is this formula true? How can I prove it? $$\sum_{s=0}^{n-1}\binom{n-1}{s}2s =2^{n-1}(n-1)$$ Thanks!
0
votes
1answer
29 views

Identity of sum of binomial coefficients

I'm struggling to understand the following derivation where $n$ is a positive integer. $$ \sum_{\ell=0}^n {n \choose \ell} 2^\ell \log 2^\ell = n \sum_{\ell=0}^{n-1} {n-1 \choose \ell} 2^{\ell+1}. $$ ...
0
votes
0answers
12 views

Proving that $\Phi_{t*}[\mathbb{Y},\mathbb{Z}]=[\Phi_{t*}\mathbb{Y},\Phi_{t*}\mathbb{Z}]$

Let $\mathbb{X}$ be a vector field on $\mathbb{R}^n$. Let $\Phi_t$ denote the flow of $\mathbb{X}$. You are given that $\displaystyle L^j_{\mathbb{X}}[\mathbb{Y},\mathbb{Z}]=\sum_{k=0}^{j} ...
1
vote
1answer
85 views

How to prove this Catalan number identity

Catalan number is $\displaystyle C_n= \frac{1}{n+1}\binom{2n}{n}$. How to prove that $$C_{2n-1} = \sum_{k=0}^{n-1}\left(\binom{2n-1}{n-k-1}-\binom{2n-1}{n-k-2}\right)^2$$ for $n\geq 1$. Thank you.
4
votes
3answers
124 views

How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose ...
1
vote
2answers
102 views

How prove this identity$\sum_{k=0}^{n}\binom{2k}{k}\binom{n+k}{2k}(s-t)^{n-k}t^k=\sum_{k=0}^{n}\binom{n}{k}^2s^{n-k}t^k$

Today I see a paper,and this author say it is easy to have this identity.But I take sometimes to prove it,and I can't prove it. show this following identity holds for any real $s$ and $t$ and any ...
0
votes
0answers
25 views

Why we can use normal distribution to approximate binomial distribution when n is large enough?

Prove why we can use normal distribution to approximate binomial distribution when n is large enough. Hint: Try to read something on bernoull ...
0
votes
2answers
25 views

Generating functions and central binomial coefficient

How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4y}}$? More precisely, prove that( for $|x|<\frac{1}{4}$ ): ...
3
votes
0answers
79 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
2
votes
1answer
27 views

If $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ …

Problem: If $a_n =\sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ then find the value of $a_0+a_1+a_2+\cdots \infty$ My approach: $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ $= ...
2
votes
0answers
48 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
1
vote
1answer
42 views

Growth of binomial coefficient

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest ...
1
vote
2answers
46 views

Probability involving bread and jam!

SO, I drop a piece of bread and jam repeatedly. It lands either jam face-up or jam face-down and I know that jam side down probability is $P(Down)=p$ I continue to drop the bread until it falls jam ...
0
votes
1answer
12 views

Lie derivatives of vector fields and the binomial expansion

Given the Jacobi identity $[\mathbb{X},[\mathbb{Y},\mathbb{Z}]]+[\mathbb{Y},[\mathbb{Z},\mathbb{X}]]+[\mathbb{Z},[\mathbb{X},\mathbb{Y}]]=0$ and that the Lie derivative of a vector field is ...
1
vote
1answer
44 views

Finite natural summation that leads to double exponential results

We know that $$f(n)=\sum_{i=0}^n\binom{n}{i}=2^n$$ and $$g(n)=\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}.$$ Are there any finite natural sums that lead to $2^{2^n}$ or $2^n2^{2^{n-1}}$ results other than ...
2
votes
4answers
45 views

A finite binomial sum

Is their an exact expression for the following sequence involving binomial coefficients $$\sum_{i=0}^n i\binom{n}{i}?$$
1
vote
1answer
24 views

Multinomial identity - guidance needed

I need hints on a direction to proove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
1
vote
0answers
19 views

Closed form for binomial coefficient series

If $6|n$, is there a closed form for $$\sum_{t=\frac{n}{2}}^n\binom{\frac{n^2}{3}}{t}\binom{\frac{2n^2}{3}}{n-t}?$$
0
votes
4answers
37 views

proof of summation using $\displaystyle \binom{n}{r}$

Prove that $\sum_{r=0}^{n} \binom{n}{r}2^r = 3^n$ for $n \in \mathbb P$. "Hint: give me an argument having to do with the number of strings of length $n$ with $3$ symbols."
2
votes
2answers
80 views

How many positive integer solutions are there to the equation $(a + b + c + d) < N$?

Here's my attempt: My thinking is that this is the same as finding all the non-negative $a, b, c, d$ such that $a + b + c + d = M$ where $M \in \{0, 1, ..., N - 4\}$. Which further reduces to a stars ...
0
votes
0answers
32 views

Closed Form for a Sequence

I have come across this sequence $$a_0 = -2, a_1 = 5, a_2 = -28, a_3 = 255$$ and, in general $$a_n = -\frac{1}{2}\bigg(\sum_{i=1}^n \binom{2n+4}{2i}a_{n-i} + \binom{2n+4}{2n+1}\bigg)$$ I've tried ...
0
votes
1answer
46 views

A binomial inequality

I've tried both expanding the binomials as well as trying to deduce something from the hypergeometric distribution, but I don't see how to prove: $${N\choose n}^{-1}\sum_{i\geq j}{M\choose ...