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)

6
votes
1answer
66 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
70 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
26 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
120 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
144 views

How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

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

Congruence with binomial

I tried to prove this by induction on $k$. But I did not manage Let $p$ be a prime. For every $k\in\{0,\cdots,p-1\}$, one has $$\binom{p-1}k\equiv(-1)^k\pmod p.$$ By Wilson theorem, it suffices to ...
-2
votes
0answers
94 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
161 views

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

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
48 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
125 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
167 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
66 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
305 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
28 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 ...
0
votes
3answers
78 views

Another sum involving binomial coefficients.

Let both $a$,$b$ and $\theta$ be real numbers not equal to a negative integer. Let $m$ be a positive integer. I have shown that the following equality holds: \begin{eqnarray} ...
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
56 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
359 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
48 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
50 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}. $$ ...
3
votes
2answers
207 views

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

Let $\mathbb{X},\mathbb{Y}$ be vector fields on $\mathbb{R}^n$. Let $\Phi_t$ denote the flow of $\mathbb{X}$. Define $L_{\mathbb{X}}\mathbb{Y}=[\mathbb{X},\mathbb{Y}]$. You are given that ...
1
vote
1answer
106 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
144 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
117 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
35 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
73 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
169 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
30 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)!}$ $= ...
1
vote
0answers
64 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
56 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
57 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
26 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
58 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
50 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
42 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
22 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
41 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
140 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
51 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
54 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 ...
2
votes
2answers
62 views

Average number of trials until drawing $k$ red balls out of a box with $m$ blue and $n$ red balls

A box has $m$ blue balls and $n$ red balls. You are randomly drawing a ball from the box one by one until drawing $k$ red balls ($k < n$)? What would be the average number of trials needed? To ...
0
votes
2answers
37 views

Ratio of 2 Sums of products of binomial coefficients

I want to prove that for $k \ even, 0 \leq k<n, n\in \mathbb{N}$: $-\frac{1}{(2n-3-k)(k+2)}\sum \limits_{i=0}^{k} \frac{(-1)^{i} 2^{i} (2n-2-i)!}{(n-1-i)!i!(k-i)!}=\sum \limits_{i=0}^{k+2} ...
0
votes
1answer
38 views

prove binomial multiplication less than 1

please show me how to prove the following. Given $m >= n,n\geq2$ prove $\binom mn$ $\cdot \frac{1}{n^m} < 1$ ------UPDATE-------- Given the inequalities: $(\frac{m}{n})^n \le \binom mn \le ...
1
vote
1answer
29 views

Binomial Formula conversion

I saw an answer in stackoverflow about binomial here The answerer provide some nice explanation how can binomial can be calculated by pascal triangle. But I'm still not sure how to convert this ...
1
vote
1answer
41 views

Number of overlapping columns

Consider an $m \times n$ matrix $A$ with $m<n$. It is well-known that number of ways of choosing $k$ columns out of $n$ from $A$ is $\binom{n}{k}$, where ($k<m<n$). What is the number of ways ...
2
votes
1answer
66 views

Combinatorics: Number of Six-Card Hands That Can Be Dealt from r Combined Decks

I am having trouble solving this combinatorial problem dealing with the number of different card hands possible from multiple decks of identical cards. Here is the exact question: Use a combinatorial ...
1
vote
2answers
129 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
1
vote
0answers
21 views

binomial coefficient and recurrence relation [duplicate]

any hints on how to solve the recurrence relations for the following binomial coefficient \begin{equation} {n \choose k}=\begin{cases} 1, & \text{if $k\in\{0,n\}$}.\\ {n-1 \choose ...
0
votes
1answer
26 views

Binomial distribution “matix of results”

I am having trouble understanding the formal definition of the binomial distribution. $$f(k;n,p) = \Pr(X = k) = {n\choose k}p^k(1-p)^{n-k}$$ Or rather how I "transform" the definition to suit my ...
2
votes
1answer
55 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $B=B(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \leq B n^{-1/2}2^{n ...