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)

0
votes
0answers
21 views

how to estimate $\sum (n,i)$?

How to estimate $\sum\limits_{i=-A}^{A} \binom{n}{i}$ ? This probably relates to the central limit theorem and the proof of it. But I want good estimates, also for small values (not just limits to ...
2
votes
0answers
21 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
3
votes
2answers
82 views

Sum of series with binomial

How to calculate $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{2n}{2^{2n}(2n-1)}$$ ? I tried to use residues, generating function, combinatorics formulas, but unsuccessfully.
0
votes
1answer
41 views

Generalisation of Binomial Coefficient (Combinatorics on words)

So, when trying to find subwords from a bigger word: $\binom{abracadabra}{ab} = 5$ with $ABracadabra$, $AbracadaBra$, $abrAcadaBra$, $abracAdaBra$, $abracadABra$. I have noticed that it doesn't go ...
0
votes
2answers
46 views

$\big(1+\frac {C_0}{C_1}\big) \big(1+\frac {C_1}{C_2} \big) \cdots \big(1+\frac {C_{n-1}}{C_n} \big) =?$

If $(1+x)^n =~~ ^nC_0 ~+~ ^nC_1~x ~+~ ^nC_2 x^2~+~\cdots+~ ^nC_n x^n $, then the value of : $$\bigg(1+\dfrac {C_0}{C_1}\bigg) \bigg(1+\dfrac {C_1}{C_2} \bigg) \cdots \bigg(1+\dfrac ...
1
vote
0answers
31 views

How to find the upper bound of a binomial coefficient by using binomial theorem?

I have a task to find a upper bound of the binomial coefficient for all $r \leq \frac{n}{2}$. I've already obtained by using such relation: $$\frac{\sum_{k=0}^{r}\binom{n}{k}}{\binom{n}{r}}$$ Which ...
1
vote
3answers
23 views

Calculating the sum of coefficients for binomial expression

The question is: Calculate the sum of the coefficients of $(a-b)^{250}$. My reasoning was that we can take the example of $(a-b)^2$, which would have the coefficients of $1$, $-2$, and $1$, ...
1
vote
0answers
39 views

Mean and variance of a random variable whose distribution is Pr {X = k} = Binomial [N-k, n] *Binomial [k-1,n] /Binomial [N, 2n+1] for k=n+1, …, N-n

What is the mean and variance of the random variable whose distribution function is $P(X = k)=$ $\binom{N-k}{ n} \times \binom{k-1}{n} \over \binom{N}{ 2n+1}$ for $k=n+1, ..., N-n$? Progress: ...
0
votes
4answers
72 views

Proving the combinatorial identity $\sum_{k=0}^{n} \binom{2n+1}{2k}=2^{2n}.$

I want to see that $$\sum_{k=0}^{n} \binom{2n+1}{2k}=2^{2n}.$$ Does anybody know how to see this quickly?
1
vote
4answers
110 views

Closed Form Expression of sum with binomial coefficient

I have the following equation which is making me problems. $$A_{n} = \sum_{k=0}^{n} \binom{n-k}{k}(-1)^{k}$$ where $n\in\mathbb{N}$. The task is to find a closed form expression for $A_{n}$. I have ...
2
votes
1answer
25 views

Binomial sum identity

Everyone knows that $\sum{n \choose 2k}=\sum{n \choose 2k+1}$ My question is follwing What is the clear form of $\sum_{k=0} (-1)^k{n \choose 2k}$ and $\sum_{k=0} (-1)^k{n \choose 2k+1}$ For ...
3
votes
3answers
131 views
+50

Permutations containing a given subsequence

Let $f(n)$ denote the number of $4n$-long strings formed from $2n$ a's and $2n$ b's, such that the string contains, as a (possibly non-consecutive) subsequence, a pattern containing $n$ a's and $n$ ...
0
votes
1answer
32 views

$\left( 1 - \frac{1}{n} \right)\left( 1 - \frac{2}{n} \right) \cdot … \cdot \left( 1 - \frac{k-1}{n} \right) = \frac{n!}{n^k r! (n-k-r)!}$

I'm trying to understand a proof in "Interpolation and Approximation by Polynomials" by Phillips. Let me quote (page 253): "For $k\geq 1$ we begin with $$B_{n+k}^{(k)}(f;x)=\frac{(n+k)!}{n!} ...
-5
votes
1answer
35 views

Mathematical Induction problem involving binomial coefficients [closed]

I cannot solve it by using mathematical induction. Please help me with it. $$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\ldots+\binom{n}{n}=2^n$$ ...
5
votes
4answers
88 views

Proving $\binom{m}{n} + \binom{m}{n-1} = \binom{m+1}{n}$ algebraically

I am working through the exercises and have spent half a day on one problem so I decided to get some help because I can't figure it out. Show that if $n$ is a positive integer at most equal to $m$, ...
2
votes
1answer
88 views
+50

Lower bound for the chromatic number of $\mathbb{R}^n$

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$: $$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$ At some point in the proof we get that ...
3
votes
2answers
33 views

Stuck in a problem in permutation and combination.

I am solving problems in permutation & combination and stuck in this problem. Two players $P_1$ and $P_2$ play a series of $2n$ games. Each game can result in either a win or a loss for $P_1$. ...
2
votes
4answers
51 views

Summation of $\binom{N}{K}$

I was working on a math problem that required me to figure out the general summation of $\binom{N}{0} + \binom{N}{1} + \ldots + \binom{N}{K}$. I know that if $k = N$, the answer is $2^N$. But is ...
2
votes
1answer
165 views

How can I prove this combinatorial identity?

Let $n,m$ be non-negative integers. How can one prove the following identity? $$\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$$
1
vote
1answer
25 views

Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$.

Let $k\ge 1, m\ge 1.$ Show that if $x\equiv 1 \pmod {m^k}, $then $x^m \equiv 1\pmod{m^{k+1}}$. First I noticed that the assumption would imply $x^m \equiv 1 \pmod{m^k}$, but that doesn't seem to ...
0
votes
0answers
23 views

Combinatorial identity binomial coefficients [duplicate]

How to prove that $$ \binom{m}{p} = \sum_{j=0}^q \binom{q}{j}\binom{m-q}{p-j}\;?$$
0
votes
0answers
26 views

Formula for coefficient of Mahonian numbers

I recently came out with this article . It tells about triangle of mahonian number.The T(n,k) is coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to n*(n + ...
0
votes
1answer
31 views

finding the value of a node in Pascal’s (a.k.a Yanghui's) triangle [closed]

Image the Pascal Triangle is on an x-y cartesian plane. so that the values of the nodes, by location are ...
0
votes
1answer
22 views

Unimodality of sequence

I have to show the following: a) was pretty easy to show, however, I am not able to get something useful out of the recursive definition in b) and I have no idea how to approach c). What bijection ...
1
vote
1answer
21 views

What's the solution to this binomial?

what's the coefficient of $x^6$ in the expansion of $(1+X^2+X)^{-3}$? I have factorized the term to $\left(\frac{1-x^{-3}}{1-x}\right)^3$ after this I'm having problem solving it
1
vote
0answers
31 views

coefficients of polynomial and binomial expressions

Let us say we are given a polynomial p(x)=$\sum_k a_k x^k$. In order to find $\sum_k a_k$ we simply need to evaluate p(1), and similarly there are many other tricks. Is there any trick to evaluate ...
2
votes
2answers
65 views

Find the coefficient of $x^4$ in the expansion of $(1 + 3x + 2x^3)^{12}$?

I have not learnt the multinomial theorem yet, and was trying to approach this using the binomial theorem. I divided the terms as $a$ being $(1+3x)$ and $b$ being $2x^3$. I then used $${12\choose ...
1
vote
2answers
51 views

When is $n\choose k$ a multiple of $n$

While working through a question, the solution states that in the finite field $\mathbb{F}_p$ for $p$ prime, we have $(u+v)^p=u^p + v^p$ and since $(u+v)^p={p\choose 0}u^pv^0+{p\choose ...
0
votes
0answers
28 views

Final step of a random walk proof

I am working through the last bit of a random walk proof to show that a 3-d random walk is transient. The result I am looking for states that: $\frac {1}{2}^{2s} {{2s}\choose{s}} \sum_{j+k\leq{n}} ...
2
votes
3answers
51 views

Inequality of factorial - Binomial coefficient

my name is Rafał and I decided to create this thread because of my inability to find a solution. I have been fighting with this inequality for 1.5 week and I have a hope that you will give me any hint ...
8
votes
0answers
131 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ which can also ...
2
votes
5answers
93 views

How to sum $\sum_{k=1}^n (k+1)(k)(k-1)$

Is there an intelligent way to do this sum without using sums of cubes and sums of squares? $$\sum_{k=1}^n (k+1)(k)(k-1)$$
0
votes
1answer
32 views

Tree addtion has to do with Pascal's Triangle, why?

Let me define tree addition of a list of numbers as follows: 4 3 2 1 7 5 3 12 8 20 I conjecture that it is true that the tree addition of n numbers ...
0
votes
1answer
69 views

Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$ It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion ...
5
votes
0answers
61 views

Combinatorial Interpretation of these two identities

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
1
vote
1answer
41 views

Relationship between Factorial and Binomial coefficients

Over at this link, there is a claim that $(2n)! = n!n! {{2n} \choose {n}}$ - see Tom Boardman's answer, the second one down. I'm wondering why this is the case and if anyone can provide a proof. Is ...
1
vote
1answer
29 views

Why can I not include unused cards into a second binomial coefficient?

In trying to count the number of 13-card hands where there is at least one ace and no J, Q, K, we can see one way is $$ \sum_{k=1}^4 \binom{4}{k}\binom{36}{13-k} = 9722433280. $$ However, I cannot ...
1
vote
2answers
52 views

What will be the sum of the series of binomial co-efficients?

What will be the sum of the following binomial co-efficent series $$\binom{z+1}{z} + \binom{z+2}{z} + \binom{z+3}{z} + \dots + \binom{z+r}{z} = \sum\limits_{i=1}^r \binom{z+i}{z}$$ Thank you
1
vote
3answers
42 views

Finding the formula for summation of the series

I was just solving a competitive programming question, wherein I found out that a formula can be used for solving it efficiently. Problem statement: http://www.spoj.com/problems/TOHU/ I tried a lot to ...
0
votes
2answers
47 views

Solving inequality equation involving sum of binomial coefficients

I have a function $f(k,\,i)$ involving binomial coefficients: $$f(k,\,i)\,=\left(\begin{matrix}k+i \\ k\end{matrix}\right)=\frac{(k+i)!}{k!\,i!}$$ And the following sum over this function (expansion ...
0
votes
1answer
17 views

Formula for combinatorial series sum [duplicate]

As a part of one computer algorithm, I want to find sum for $$n+ \frac{n(n+1)}{2!} + \frac{n(n+1)(n+2)}{3!}+....+ \frac{n(n+1)(n+2)...(n+r-1)}{r!} $$. I looked at $$\frac1{(1-x)^n}$$. But it is ...
0
votes
1answer
56 views

Where does this equation come from: $ (1+mx)^n = 1 + \sum_{n=1}^{\infty} {\binom{2n}{n} \over 4^n } x^n $

I have found the following problem here: https://brilliant.org/problems/intriguing-sum/?group=Km7yEIDGtHDa&ref_id=709399 In the solution a solver directly started with the equation given in the ...
3
votes
2answers
63 views

A reference for a combinatorial identity

I have come across this identity from study of species. I am not posting my method but I am interested in knowing whether it arises in some other contexts as well. The identity is: $$\sum ...
0
votes
1answer
34 views

Does this sum of products of binomial coefficients have a simple closed form?

Let $c,m,k$ be positive integers. Is there a simple closed form for the following sum? $$ \sum_{i=1}^{c-1} (-1)^i {c \choose i} {im \choose k} $$ Mathematica finds nothing, and Maxima's implementation ...
0
votes
1answer
80 views

Where is my formula false??

I wrote a formula that returned how many numbers in a given row of pascals triangle are divisible by a given prime. This formula was created to answer https://projecteuler.net/problem=148. I was ...
4
votes
3answers
139 views

Find the limit of $4^n\cdot\binom{2n}{n}/\binom{4n}{2n}$

I am trying to prove that $$f(n)=4^n\frac{\dbinom{2n}{n}}{\dbinom{4n}{2n}}$$ converges as $n\rightarrow\infty$. I have already tried to use the fact that, if $n, k \in\mathbb{N}, n\geq k\geq1,$ then ...
2
votes
1answer
18 views

Growth of modified binomial recurrence

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
0
votes
1answer
18 views

Growth of binomial recurrence with different initial conditions

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
2
votes
2answers
29 views

How can I prove this property of binomial coefficients?

I was playing around with binomial coefficients and binomial expansions and I came across an interesting identity: $$ \sum_{k=0}^n\frac{1}{k+1}{n \choose k}x^k=\frac{(x+1)^{n+1}-1}{(n+1)x}$$ I have ...
0
votes
1answer
74 views

Binomial Series. Product series of coefficients [on hold]

How to solve this question? Please provide hints only.