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)

4
votes
3answers
133 views

$N^L$ vs. ${N+L\choose N}$

Any ideas on finding a good estimate/approximation for $A/B$ where $A = N^L$ and $B = {N+L\choose N}$?
2
votes
2answers
124 views

Calculating the highest possible damage achievable using 6 items from a pool of ~25

I am writing an app in javascript to try to figure out item builds for characters in a video game. There are about 25 top-tier items, and you can carry 6 at a time. They have very different effects, ...
5
votes
3answers
508 views

A Binomial Coefficient Sum

In my work on $f$-vectors in polytopes, I ran across an interesting sum which has resisted all attempts of algebraic simplification. Does the following binomial coefficient sum simplify? \begin{align} ...
3
votes
1answer
139 views

Simplification of a sum

Any ideas on how to approximate and/or simplify this crazy-looking sum will be massively appreciated) $$\frac{1}{\mu}\sum_{j=0}^{\frac{\lambda}{2}} ...
3
votes
2answers
108 views

Bounding sum of binomials

For a small $c>0$, what is a smallest $k$ such that $$\sum_{i=0}^k \binom{n}{i} \ge c \cdot 2^n.$$ The sum jumps somewhere around $k=\frac{n}2$ from $o(2^n)$ to almost $2^n$. Is there a better ...
4
votes
1answer
169 views

Derive maximal sum of binomial terms

How to determine a positive value of variable $m$, so that the following formula is maximized. $$\frac{(1-q)^m}{\sum_{x=m/c}^{m}{\binom{m}{x} (1-q)^{m-x} q^x}}$$ where $1<c<m$, $0<q<1$, ...
2
votes
1answer
351 views

Evaluating (bounding) sum involving the binomial coefficient

Solving some problem I have stumbled into the following sum : $ \displaystyle \sum_{i=0}^{n-2} {e \choose i} (n-1-i) (1-p)^{e-i} p^i $ where $ 0 \leq e \leq {n \choose 2}$. I am not very efficient ...
9
votes
2answers
517 views

Closed form for a sum involving binomial coefficients

Let $n,k$ be positive integers. Is there a closed form of the sum $$\sum_{s=0}^{k} \binom{n}{s} \binom{s}{k-s}\text{?}$$ By that I mean a representation which is free of sums and hypergeometric ...
7
votes
3answers
207 views

Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$. How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
7
votes
2answers
798 views

Squared binomial coefficient

I've got the following finite sum: $s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as ...
5
votes
4answers
456 views

Proving a special case of the binomial theorem: $\sum^{k}_{m=0}\binom{k}{m} = 2^k$ [duplicate]

I want to know if I can get some help with this proof. I tried, but I just cannot seem to get $2^{k}$. It states that, For $k \in \mathbb{Z}_{\ge 0}$, $$\sum^{k}_{m=0}\binom{k}{m} = 2^k$$ Thank ...
7
votes
2answers
304 views

A binomial coefficient identity?

Suppose $p$, $k$ and $s$ are integers with $s,k \le p$. Consider the following polynomial in $x$ and $y$, $$ \sum_{\ell=0}^k \binom{s}{\ell} \binom{p-s}{k-\ell} x^\ell y^{p-\ell}$$ Does this ...
2
votes
3answers
165 views

How can I prove the formula for calculating successive entries in a given row of Pascal's triangle?

I've found in Wikipedia the formula for calculating an individual row in Pascal's Triangle: $$v_c = v_{c-1}\left(\frac{r-c}{c}\right).$$ where $r = \mathrm{row}+1$, $c$ is the column starting from $0$ ...
6
votes
5answers
250 views

Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, ...
4
votes
0answers
357 views

p-adic numbers and binomial coefficients

Let $\alpha\in \mathbb{Z}_p$ be an $p$-adic integer and define for $n\in \mathbb{Z}_{\geq 0}$ $${\alpha\choose n} := \frac{\alpha(\alpha-1)\cdot\ldots\cdot(\alpha-n+1)}{n!}.$$ This is again a ...
5
votes
1answer
150 views

Showing two definitions of a binomial coefficient are the same

I have a homework question where we have to prove the following definitions of a binomial coefficient are equal, algebraically. This is what I got so far, and it's getting pretty complicated. And I ...
5
votes
1answer
637 views

Upper bound on summation involving binomial coefficients

I am trying to upper bound the following sum: $$\sum_{k=1}^{n/2} \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}.$$ Based on numerical computations, it seems like the upper bound is a constant ...
4
votes
1answer
420 views

Computing the Coefficients of a Polynomial in the Binomial Basis

Let $f(t) = \sum_{i = 0}^{n} c_i \ t^i$ be a degree $n$ polynomial. In the binomial basis, we can write $f(t) = \sum_{k = 0}^{n} h_k \ \binom{t + n - k}{n}$. Using the calculus of finite differences, ...
29
votes
3answers
3k views

The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that: the product of non-adjacent vertices is constant. the greatest common ...
8
votes
6answers
4k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ...
2
votes
2answers
86 views

what is some polynomial bound of the following expression?

I have the expression (for some $k$ and $r$ natural numbers): $\sum_{l=0}^r {l \choose k}$. Is there a way to bound this expression using a polynomial of degree which is linear in $k$ (or polynomial ...
3
votes
0answers
359 views

Multinomial Coefficients ! [closed]

I have come across a paper that has suggested a formula for "NUMBER OF MULTINOMIAL COEFFICIENTS NOT DIVISIBLE BY A PRIME"; but I don't understand the notation.Please help. The formula is: $ G(n,l,p)= ...
8
votes
2answers
1k views

prime numbers in Pascal's triangle

Just wondering about this: Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$? From the first 18 lines it appears that this is ...
3
votes
1answer
422 views

Matrix and Binomial Coefficients

Considering the construction of a matrix as follows. The $n$th row in the matrix is filled with the coeffcients of $x^r$ in the expansion of $(1+x)^n$ from the columns $2n$ to $3n$ inclusive and ...
12
votes
4answers
1k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
42
votes
5answers
3k views

$n$th derivative of $e^{1/x}$

I am trying to find the $n$'th derivative of $f(x)=e^{1/x}$. When looking at the first few derivatives I noticed a pattern and eventually found the following formula $$\frac{\mathrm d^n}{\mathrm ...
4
votes
1answer
324 views

Is there a combinatorial proof of this congruence identity?

Prove that $$\binom{2p}{p} \equiv 2\pmod{p^3},$$ where $p\ge 5$ is a prime number.
4
votes
2answers
520 views

How to find $\sum_{k=1}^n 2^kC(n,k)$?

How to find the sum of series, $$\sum_{k=1}^n 2^kC(n,k)$$
3
votes
0answers
321 views

Solving a certain binomial sum involving the floor function

Does anybody know of any techniques to solve the following sum (or a fast way (polynomial in N) to compute it): $$\sum_{i=0}^{N} \binom{N-i}{A} \cdot \binom{\lfloor iP/Q \rfloor + 1}{B}$$ where $P$ ...
5
votes
3answers
357 views

Prove that $\sum_{i=0}^n2^{3i} \binom {2n+1}{2i+1}$ is never divisible by 5

Question : Prove that the number is never divisible by 5.
4
votes
2answers
3k views

Number of even and odd subsets [duplicate]

Suppose we have the following two identities: $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ The first says that the number of subsets ...
2
votes
2answers
160 views

Combinatorial Identity and Counting

Show that $\binom{2n}{2} = 2 \binom{n}{2}+n^2$. LHS: This is the number of pairs of $2n$ distinct elements. RHS: We can rewrite this as $2 \binom{n}{2}+ \binom{n}{1} \binom{n}{1}$. So you can ...
8
votes
1answer
282 views

Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$. LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset. RHS: We are ...
7
votes
2answers
660 views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
9
votes
3answers
808 views

Simplify $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$

Can this sum be simplified: $\sum \limits_{k=0}^{n} \binom{n}{k} 2^{\sqrt{k}}$ Or at least is there a simple fairly tight upperbound? EDIT So I think this sum is more easily bounded than I ...
1
vote
1answer
132 views

How can we prove this property?

$ \qquad \qquad $ The greatest term in $\left(1+x\right)^{2n}$ has the greatest cofficient if $\frac{n}{n+1} \lt x \lt \frac{n+1}{n}$ Can we derive something like this for $n$ in general? Please ...
2
votes
4answers
165 views

How to sum up this series?

How to sum up this series : $$2C_o + \frac{2^2}{2}C_1 + \frac{2^3}{3}C_2 + \cdots + \frac{2^{n+1}}{n+1}C_n$$ Any hint that will lead me to the correct solution will be highly appreciated. EDIT: ...
2
votes
2answers
94 views

Are these two expressions for sums of binomial coefficients valid?

These two appear in my module (without any proof): $$\sum_{r = 1}^{n} C(n-2,r-2) = 2^{n-1}$$ $$\sum_{r = 0}^{n-1} C(n-2,r) = 2^{n-2}$$ For the first one when when $r=1 \Rightarrow C(n-2,1-2) = ...
14
votes
3answers
6k views

Proof that a Combination is an integer

From its definition a combination $(^n_k)$, is the number of distinct subsets of size k from a set of n elements. This is clearly an integer, however I was curious as to why the equation ...
11
votes
4answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
9
votes
4answers
2k views

$C(n,p)$: even or odd?

Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? ($p\lt n$, $p$ and $n$ are positive integers)
1
vote
5answers
249 views

$C(n,p) = C(n,q) => p + q= n$

How to prove the following theorem? Theorem: If the binomial numbers $C(n,p)$ and $C(n,q)$ are equal, with $p$ different from $q$, then $p+q = n$. ($n$, $p$ and $q$ are natural numbers)
8
votes
3answers
399 views

Non-probabilistic proofs of a binomial coefficient identity from a probability question

Combining the answers given by me and Ralth to the probability question at Probability Question, we get the following identity: $$ \sum\limits_{k = m}^n {{n \choose k}p^k (1 - p)^{n - k} {k \choose ...
18
votes
6answers
1k views

Exercise from Comtet's Advanced Combinatorics: prove $27\sum_{n=1}^{\infty }1/\binom{2n}{n}=9+2\pi \sqrt{3}$

In exercise 36 Miscellaneous Taylor Coefficients using Bernoulli numbers on pages 88-89 of Louis Comtet's Advanced Combinatorics, 1974, one is asked to obtain the following explicit formula for the ...
3
votes
2answers
2k views

How can I determine asymptotic growth of binomial coefficients?

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$? Is there a general ...
0
votes
1answer
158 views

Order of the maximum term of (a +b)^(-m)

I would like, if possible, to obtain a proof of the theorem below. "Being given real numbers a and b, with |a|>|b|, and m is a positive integer, the order p, which occupies the maximum term (in ...
1
vote
2answers
522 views

Maximum term of (a + b) ^ n

I would like a demonstration of the fact below. Being given real numbers a and b (nonzero) and a positive integer n, the order p, that occupies the maximum term (in absolute value) of the ...
13
votes
4answers
712 views

How this operation is called?

This operation is similar to discrete convolution and cross-correlation, but has binomial coefficients: $$f(n)\star g(n)=\sum_{k=0}^n \binom{n}{k}f(n-k)g(k) $$ Particularly, $$a^n\star ...
7
votes
3answers
268 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...
8
votes
1answer
423 views

$\binom{n}{k} : \binom{n}{k+1} : \binom{n}{k+2} = a : b : c$

It is a rather surprising fact (to me, at least) that $\displaystyle \binom{14}{4} = 1001$; $\displaystyle \binom{14}{5} = 2002$; $\displaystyle \binom{14}{6} = 3003$. Actually, this is the only ...