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
1answer
44 views

Binomial Coefficient: monotonically decreasing in this range?

relating to this question, I'd like to ask a further one. Again we have $$f(x)={k-1 \choose x-1} p^x (1-p)^{k-x}$$ We know that this term is maximal for $x=kp$, before increasing, afterwards ...
0
votes
1answer
24 views

monotonicity of binomial coefficient

I am interested in $$f(x):={k-1 \choose x-1} p^{x} (1-p)^{k-x}.$$ How do I find out in which Domain this function is monotonically increasing, in which it is monotonically decreasing? For which $x$ ...
1
vote
0answers
48 views

Is there a sharper bound than exponential for $\sum_{k\ge0}\frac{m!(k+n-m)!}{(k+n)!}\frac{s^k}{k!}$?

I am trying find a bound for an expression and I am getting something not quite as convenient as I hoped. Going through my calculations again I think that the only place I use a non sharp bound is ...
3
votes
2answers
72 views

Integer sum as binomial coefficient

What's the rule for expressing integer sums as binomial coefficients? That is, for $p=1$ it is $$\sum_{n=1}^N n^p = {{N+1}\choose 2} $$ What is it for higher powers?
1
vote
2answers
35 views

Alternative proofs:

I have worked about a result and want to know if there are better ways of proving the following: $$N^M - (N-1)^M$$ $$=\binom{N}{1}(N-1)^{M-1} + \binom{N}{2} (N-1)^{M-2} + \binom{N}{3} (N-1)^{M-3} + ...
1
vote
0answers
23 views

Equation for those level curves?

Related to this question Let $n\in\mathbb{N}^*,\alpha\in\mathbb{R}$. What would be the equation $y=f(x)$ for the curve defined by $\ln\binom{N-y}{x}=\alpha$ That's how they look : TL;DR : What ...
0
votes
1answer
57 views

The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
1
vote
1answer
24 views

A sum of Laguerre polynomials

I'm looking to find a closed-form expression for the sum $$S = \sum_{n=0}^N e^{-x/2} L_n^{0}(x),$$ where $L_n^{0}$ is the $n$th Laguerre polynomial. Using the formula $$L_n^{\alpha}(x) = \sum_{m=0}^n ...
0
votes
0answers
49 views

Asymptotic complexity of $\sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$

I'm trying to examine the asymptotic complexity of $$f(m) = \sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$$ Question: How do you prove or disprove $f(m) \in \mathcal{O}(2^{2^m})$? Bonus ...
2
votes
0answers
45 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$$ which can be proved combinatorically whether one particular element(among the $n$) is ...
0
votes
1answer
28 views

A little help in this binomial problem.

In the binomial expansion of $(a-b)^n$, $n \geq 5$, the sum of $5^{th}$ and $6^{th}$ term is $0$, then $\frac{a}{b}$ is ? I've solved this problem but its coming $n-4$ only, and the answer says it ...
0
votes
3answers
39 views

Binomial coefficient after expansion.

What is the coefficient of $x^7$ in the expansion of $(1-x-x^2+x^3)^6$ ?
2
votes
1answer
78 views

A generalized combinatorial identity for a sum of products of binomial coefficients

I have the following question. For given natural numbers $n$ and $d$, let $a_1,a_2,..., a_r$ be fixed integers such that $a_1+\cdots+a_r=d$. Let $A=\{(i_1,..,i_r)~|~0\le i_j\le n~ \text{and}~ ...
0
votes
0answers
41 views

A sum of powers of binomials

For $n$ and $k$ non-negative integers, let $$F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k.$$ For example, $F(n,0)=n+1$, $F(n,1)=2^n$ and $F(n,2)=\binom{2n}{n}$. Does there exist a general formula for ...
0
votes
0answers
24 views

Finding the co-efficient

I am trying to find the co-efficient of $\frac{1}{z}$ in the expansion of $$\frac{(1+z^2)^{2n}}{z^{2n+1}}$$ I proceeded like this - ...
3
votes
4answers
116 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
2
votes
0answers
32 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
1
vote
0answers
30 views

Number of draws that contain at least $k$ red coins

Assume there are $n$ coins in an urn from which $r$ are read. What is the number of draws of $r$ coins that contain at least $k$ red coins? It is obvious that there are ...
2
votes
2answers
59 views

Limit of binomial coefficients

Let $0\leq a_n\leq n$ be a sequence of integers. Under which condition on the $a_n$ does $$\frac{{n-a_n\choose a_n}}{{n\choose a_n}}=\frac{(n-a_n)(n-a_n-1)\dots(n-2a_n+1)}{n(n-1)\dots(n-a_n+1)}$$ ...
2
votes
2answers
34 views

highest power of prime $p$ dividing $\binom{m+n}{n}$

How to prove the theorem stated here. Theorem. (Kummer, 1854) The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ ...
0
votes
2answers
46 views

Coefficient of polynomials

Could someone explain to me why $$ [x^{24}](1-2x^6)^{-31} = 2^4 \binom{4 + 31 - 1}{31 - 1} \, ? $$ Reads: The coefficient of $x^{24}$ in $(1-2x^6)^{-31} =$ ...
0
votes
0answers
64 views

What's the interpretation of $\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$?

I'm having problems with finding the combinatorial interpretation of this sum: $$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$$ Can anyone help, please?
1
vote
1answer
35 views

How prove $\sum_{k=0}^{2m}\binom{2m+1}{k}\cdot 2^k\cdot B_{k}=0$

we know Bernoulli number such identity $$\sum_{k=0}^{n}\binom{n+1}{k}B_{k}=0$$ see:Bernoulli number identity show that $$\sum_{k=0}^{2m}\binom{2m+1}{k}\cdot 2^k\cdot B_{k}=0$$ where $B_{n}$ ...
4
votes
2answers
189 views

Generating function of binomial coefficients ${n\choose5}$

How to prove easily this identity for (almost classical) series with binomial coefficients: $$ \sum_{n=5}^\infty \dfrac{\binom{n}{5}}{2^{n+1}} = 1 . $$ Thank you. Any smart proof would be much ...
3
votes
2answers
71 views

Root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$

Is there an analytic way to obtain the highest root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$ in terms of $K$ and $C$? The integer $K \ll x$ and the constant $C$ are known. The other way to ask ...
1
vote
1answer
29 views

Equality of binomial coefficients

I have seen that the following equations are equal, but are wondering how this is shown ${n \choose m} \cdot 1 \cdot 3 \cdots (2m-1)\cdot 1 \cdot 3 \cdots (2n-2m-1) = \frac{n!}{2^n} {2m \choose m} ...
4
votes
1answer
65 views

Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
0
votes
2answers
27 views

Probability of special configuration of ones in a binary string

Consider the sequence $(X_i)_{1 \leq i \leq L}$ of i.i.d. random variables, where $X_1 \in \{0,1\}$ and $P(X_1 =1) = p$. For a $k \in \mathbb{N}$ define the event $A_{k,L}$ as "all ones in the ...
0
votes
2answers
57 views

Largest term in binomial expansion of $(1+n)^k$

The binomial expansion of $(1+n)^k$ is $$(1+n)^k=1+\binom{k}{1}n+\binom{k}{2}n^2+\cdots+\binom{k}{k}n^k.$$ If $n=1$, then the term in the middle is the largest, i.e. when $i=\lfloor k/2\rfloor$ and ...
1
vote
1answer
28 views

How find this sum $\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$

Let $m$ is give postive integer numbers, Find the sum $$\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$$ if this not have closed form,and can you use Special function ?
1
vote
1answer
45 views

How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$ where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with ...
0
votes
0answers
42 views

Behavior of this function involving binomial coeffs

I have the function: $$ f(n,m,\ell)=\binom{n+m}{\ell}-\left(n\binom{m}{\ell-1}+\binom{m}{\ell}+\binom{n}{\ell}\right) $$ It represents the number of possible sets of size $\ell\ge 3$ that can be ...
2
votes
1answer
44 views

Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
1
vote
0answers
40 views

Closed form expression sum-product of binomials

Is it possible to find a closed form expression for $$\sum_{j=1}^a\sum_{i=1}^{b} {i+j-1\choose j} {i+j-1\choose i},$$ where $a \geq 1$, and $b \geq 1$ are integers. I couldn't apply any type of ...
0
votes
0answers
8 views

Confidence intervals for bernoulli trials over a cyclic time series

I have a time series with observations of 0 or 1 observed yearly for approx. 20 years. The time series is cyclic and I want to find a CI for the probability p over the cycle (mean). Unfortunately I ...
12
votes
1answer
243 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
0
votes
1answer
39 views

Is it possible to get a formula for this summation

The binomial sum $$s_n=\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots+\binom{2n}{n}$$ I tried solving through recurrence, but unable to find one.
0
votes
0answers
56 views

$\sum_{k=1}^{n}\dfrac{(-1)^{k+1}}{k}{n\choose k}=\sum_{k=1}^n\dfrac{1}{k}$

If $n$ is a positive integer, then the above identity holds. I tried to solve this question using generating function. $$A(x)=\sum_n\left(\sum_{k=1}^n\dfrac{1}{k}\right)x^n=-\dfrac{\log(1-x)}{1-x}$$ ...
3
votes
3answers
49 views

Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a ...
1
vote
2answers
53 views
1
vote
1answer
60 views

Binomial Coefficient Even or Odd? [duplicate]

How to check whether the value of binomial coefficient nCr is even or odd ?
1
vote
3answers
72 views

Why is $\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even? [duplicate]

Why is $\displaystyle\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even ? The case if $n$ is odd, is clear, since ...
2
votes
1answer
67 views

simplifying a triple sum of products of binomial coefficients

Right now I have a horribly-looking triple sum ($x,y,z$ are non-negative integers and $x+y+z=N$): $$ W_{12}(x,y)=\frac{x}{N}\sum_{l=0}^{x-1}\sum_{l'=0}^{y}\sum_{l''=0}^{z}{x-1 \choose ...
2
votes
1answer
112 views

Combinatorial proof involving reciprocals

This is a follow-up to this question: show that if $n$ is a positive integer then $$\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}\binom{n}{k} =\sum_{k=1}^{n}\frac{1}{k}\ .$$ I was able to answer the question by ...
0
votes
0answers
24 views

Efficient way to compute the binomial using $(2^k+1)^{k+1}$

The following web page: "http://introcs.cs.princeton.edu/java/78crypto/" (at Exercise 28) effectively says that: "Pascal's triangle. One way to compute the $n$-th row of Pascal's triangle (for $n ...
9
votes
3answers
301 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
0
votes
2answers
60 views

How many coefficients are in the expansion $(x + y + z)^{10}$

I need to find the number of coefficients in the expansion $(x + y + z)^{10}$. I had this exercise on a recent assignment. The answer I gave is: $3^{10} = \binom {3 + 10 - 1}{10} = \binom{12}{10} = ...
1
vote
3answers
45 views

convergence of a sum of binomials

how can I show this converges to zero for some constant C as large as you need? $$\lim\limits_{n\rightarrow\infty} \sum\limits_{k=C\sqrt{ n\log(n)}}^{n}{n \choose k } 2^{-n}$$
3
votes
1answer
85 views

How to calculate the sum of binomials? [closed]

I want to prove below: n is natural number. $$\sum_{k=1}^n k \binom{2n}{n+k} =\frac{1}{2}(n+1) \binom{2n}{n+1}$$ Please tell me above proof.
1
vote
2answers
109 views

Binomial representation

We already know that we can represent this binomial as the following: $$(a+b)^K=\sum _{n=0}^K \binom{K}{n} b^n a^{K-n};$$ where $\binom{K}{n} = \frac{K!}{n! (K-n)!}$ I want to know if this ...