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
2answers
50 views

$\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

(Own) Let $n,m$ be positive integers such that $m>n$. Prove that $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ ...
2
votes
3answers
101 views

Binomial Coefficient Computation by Dividing Consecutive Terms

If I take the binomial coefficient: $$\frac{n!}{k! (n-k)!}$$ and I want to know the result of 10 choose 4 and I proceed to do the computation $$\frac{7*8*9*10}{1*2*3*4}$$ by first dividing and then ...
1
vote
3answers
40 views

Show that the coefficient of $x^i$ in $(1+x+\dots+x^i)^j$ is $\binom{i+j-1}{j-1}$

Show that $$\text{ The coefficient of } x^i \text{ in } (1+x+\dots+x^i)^j \text{ is } \binom{i+j-1}{j-1}$$ I know that we have: $\underbrace{(1+x+\dots+x^i) \cdots (1+x+\dots+x^i)}_{j\text{ times}}$ ...
-4
votes
2answers
36 views
0
votes
0answers
29 views

Exponentiation of Pascal's Triangle(in matrix form)

I want to find a pattern in subsequent exponentiations of the pascal triangle shown in the form below Matrix P[K+1][K+1]: $$ \begin{matrix} \binom{0}{0} & 0 & 0 & 0\cdots ...
5
votes
5answers
186 views

Binomial coefficients in Geometric summation

Guys please help me find the sum given below. $$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}$$ (NOTE):The two coefficients are multiplied by 2 power (k-j) I am using the formula: ...
0
votes
3answers
55 views

Counting numbers of possible solutions

For the equation $\displaystyle x_1+x_2+x_3+x_4+x_5=n$ there are $\displaystyle \binom{4+n}{4}$ solutions. But what about the equation $\displaystyle x_1x_2x_3x_4x_5=n$ ? Assuming $\displaystyle ...
6
votes
3answers
420 views

Some trouble with the induction

Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$ For $n=2$ the inequality is true. Directly just take and ...
-1
votes
0answers
29 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [on hold]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
5
votes
2answers
123 views

Limit involving binomial coefficient

I was trying to find the below limit. The sum can be written in a hypergeometric function but it doesn't seem to help me to find the limit. Any help will be appreciated. $$ \lim_{n \rightarrow ...
1
vote
3answers
102 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
0
votes
1answer
24 views

number of binary strings with equal number of 0's and 1's

I am trying to count the number $S$ of binary strings with equal number of 0's and 1's. Since this boils down to picking $n$ out of $2n$ places where 0's can fall into, my ansatz is $$ S = ...
-1
votes
1answer
37 views

Explain proof of sum equivalence

I need to prove: $$\sum_{k=1}^n k{n \choose k} 2^{k-1} = n3^{n-1}$$ I have the answer, but I can't understand how can I get from step 1 to step 2?! Step 1: $$(1+x)^n = \sum_{k=0}^n {n \choose k} ...
9
votes
2answers
221 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
1
vote
1answer
40 views

Determinant of a matrix with binomial coefficients.

Let $n \in\mathbb{N}$ and $A=(a_{ij})$ where \begin{equation}a_{ij}=\binom{i+j}{i}\end{equation} for $0\leq i,j \leq n$. Show that $A$ has an inverse and that every element of $A^{-1}$ is an integer. ...
2
votes
1answer
82 views

How to find coefficient of $x^{12}$ in the expansion of $(1+x+x^2+x^3+…+x^n)^4$

How to find coefficient of $x^{12}$ in the expansion of $(1+x+x^2+x^3+...+x^n)^4$ I tried this : Since $(1+x+x^2+x^3+...+x^n)$ is in GP its sum will be $(x^{n+1}+1)(x-1)^{-1}$ now ACQ we have to ...
3
votes
1answer
45 views

closed form for some binomial sum

I am trying to derive a closed form for the generating function of $a_n(x)=\sum_{k=0}^n \binom{n+k}{n}x^k, x>0, n\in\mathbb{N},$ i.e. for $G(z)=\sum_{n=0}^\infty a_n(x)z^n$. The only method I ...
0
votes
0answers
27 views

Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$ [duplicate]

How do we show that this identity holds for any n? Any hints or solutions? Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$
0
votes
1answer
67 views

Complexity of $\binom{n}{2}$

So: $$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$ Using Stirling's approximation we have: $$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi ...
0
votes
2answers
71 views

Prove by induction $\sum\limits_{k=m}^{\ n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$

I can't figure out what is the base case. Could someone show the steps?
1
vote
1answer
41 views

An identity involving the binomial theorem

While working on another problem that involved a linear system of arbitrary size $n$, I managed to empirically come up with a solution for that system. My solution is correct if and only if the ...
0
votes
1answer
47 views

Combinatorial proof for $\sum_{k = 0}^n \binom {r+k} k = \binom {r + n + 1} n$ [duplicate]

I'm trying to figure out a combinatorial proof for: $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$ I've tried the committee counting thing, but that didn't work.
8
votes
2answers
181 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
6
votes
5answers
221 views

Is this combinatorial identity a special case of Saalschutz's theroem?

When I solved a question, the following combinatorial identity was used $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ But to prove this identity is ...
7
votes
0answers
70 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
4
votes
1answer
68 views

Combinatorial interpretation of identity

I recently came across the identity $$\sum_{k=0}^m\dbinom{m}{k}\cdot \frac{(-1)^k}{n+k+1}=\dfrac{n!\cdot m!}{(n+m+1)!},$$ while working on evaluating $$\int_0^1 x^n(1-x)^m\, dx.$$ I ended up ...
0
votes
5answers
74 views

If I have 10 different pairs of socks and have washed 10 socks, what are the chances that none will match?

I have 10 pairs of different types of socks. I randomly (let's just assume it was true randomness) washed 10 individual socks. It turns out none of them match! What are the chances of this? I've ...
12
votes
0answers
82 views

Prove a matrix of binomial coefficients over $\mathbb{F}_p$ satisfies $A^3 = I$.

(This problem is problem $1.16$ in Stanley's Enumerative Combinatorics Vol. 1). Let $p$ be a prime, and let $A$ be the matrix $A = \left[\binom{j+k}{k} \right]_{j,k = 0}^{p-1}$, taken over the ...
1
vote
1answer
28 views

A little problem with a binomial identity

I have to compute the quantity $\sum\limits_{k=0}^{n-1} \binom{n}{k} \frac{k}{n-k}$. Using the identity $k\binom{n}{k}=n\binom{n-1}{k-1}$ and reindexing the sum, it's easy to see the previous sum ...
0
votes
2answers
55 views

Two new binomial identities [closed]

I have to compute the following values: $$ 1) \sum\limits_{k=0}^{n-1} 2^k \binom{n-1}{k} \frac{k}{n-k} $$ $$ 2) \sum\limits_{k=0}^{n-1} 2^{n-k} \binom{n-1}{k} \frac{k}{n-k} $$ How can I solve them? ...
0
votes
1answer
45 views

Please help with finding binomial coefficient in the following expression

I'm trying to find the coefficient of $x^{2m}$ from the both sides of the following equality: $$ \frac{(1-x^2)^n}{(1-x)^n} = (1+x)^n $$ For the right side of equality I've found it as follow: $$ ...
1
vote
2answers
49 views

Please help to find term's coefficient in the following example

I trying find the number of all solutions in the following: $ x_1 + x_2 + x_3 + x_4 + x_5 = 24 $ where: 2 of variables are natural odd numbers 3 of variables are natural even numbers none of ...
0
votes
2answers
19 views

Let $(2x − y)^4 = gx^4 + hx^3y + ix^2y^2 + jxy^3 + ky^4$ , where $g, h, i, j, k$ are integers.

Let $(2x − y)^4 = gx^4 + hx^3y + ix^2y^2 + jxy^3 + ky^4$ , where $g, h, i, j, k$ are integers. What is $h$? = $-32$ What is $j$? = $-8$ i'm using the pascal triangle and know that i should start ...
5
votes
3answers
78 views

Summation of series in powers of x with certain combinations as coefficients

How can I find the sum: $$\sum_{k=0}^{n} \binom{n-k}{k}x^{k}$$ Edit: The answer to this question is: $$\frac{{(1+\sqrt{1+4x})}^{n+1}-{(1-\sqrt{1+4x})}^{n+1}}{2^{n+1}\sqrt{1+4x}}$$ I don't know how to ...
5
votes
0answers
223 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
1
vote
4answers
58 views

Coefficient of $x^9$ in the Product

Find the Coefficient of $x^9$ in $$G(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)\cdots(1+x^{100})$$ My Try: $$G(x)=P(x)(1+x^{10})(1+x^{11})\cdots(1+x^{100})=P(x)(1+O(x^{10}))$$ Hence Coefficient of $x^9$ in $G(x)$ ...
1
vote
0answers
11 views

Binomial random variable/z-score question?

I was given the problem: In a restaurant called ”Allegory”, on average 1 in 10 people order a bottle of white wine. Out of a sample of 50 people 11 chose a bottle of white wine. Has this wine become ...
9
votes
2answers
72 views

When is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $n,m,j$?

As stated in the title: when is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $m,j,n$? I was thinking about this problem a couple of days ago because in all my years of ...
3
votes
2answers
65 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
2
votes
2answers
47 views

Proof that ${{2n}\choose{n}} > 2^n$ and ${{2n + 1}\choose{n}} > 2^{n+1}$, with $n > 1$

i'm trying to proof these two terms. I started with an induction, but I got stuck... Can anybody help?
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...
4
votes
3answers
191 views

Convolution of binomial coefficients

As part of a (SE) problem I've been working on, I came up with this expression: $$ \sum_{i=0}^M\binom{M-1+i}{i}\binom{M+i}{i} $$ I'd like to get a closed form for this, but after a considerable amount ...
3
votes
3answers
56 views

How to expand $\sqrt{x^6+1}$ using Maclaurin's series

The expansion would be $\sum_{n=0}^\infty$$\frac{1}{2}\choose n $$x^{6n}$ How to evaluate binomial coefficient with rational numbers? If $\frac{1}{2}\choose n $=$2n\choose n $$\times ...
2
votes
1answer
70 views

Sum with binomial coefficients and integer powers

I would like to have an analytic expression for the following sum $$ G_{n,a} = \sum_{p=1}^n \frac{(-1)^p p^{2(a+n)}}{(n-p)! (n+p)!} \;. $$ I am not sure it has a closed form, but I would at least ...
1
vote
1answer
65 views

Summation of a series of binomial coefficients

What will be summation of this Series: $$ {}_nC_1 + {}_nC_2 + {}_nC_3+\cdots +{}_nC_k$$ for $k \leq n$?
2
votes
2answers
67 views

$\frac{1}{{9\choose r}} -\frac{1}{{10\choose r}} = \frac{11}{6{11\choose r}}$. Is there a way to find $r$ without using algebra?

$$\frac{1}{\dbinom 9r} -\frac{1}{{\dbinom{10}r}} = \frac{11}{6\times \dbinom{11}r}$$ I guess directly applying algebra for this problem would be enough. But are there any simpler and prettier ...
1
vote
0answers
33 views

Hamming weight in multiple label

Assume you have a $N$ balls. You give each ball $T$ different labels randomly from $\{0,\dots, N-1\}$. So hamming weight of each of labelling varies from $0$ to $\lceil\log_2 N\rceil$. What is ...
0
votes
0answers
27 views

Calculating $\binom{n}{r}$ modulo $p^a$ where $p$ is prime

I need to calculate the value of $\binom{n}{r}$ modulo $p^a$ where $p$ is a prime number. If $a$ is equal to $1$, this is solved by Lucas' Theorem. Can anyone help me in this case by taking a ...
2
votes
2answers
56 views

Find sum with binomial coefficients and powers of 2

Find this sum for positive $n$ and $m$: $$S(n, m) = \sum_{i=0}^n \frac{1}{2^{m+i+1}}\binom{m+i}{i} + \sum_{i=0}^m \frac{1}{2^{n+i+1}}\binom{n+i}{i}.$$ Obviosly, $S(n,m)=S(m,n)$. Therefore I've tried ...
1
vote
4answers
257 views

How to simplify this triple summation containing binomial coefficients?

$$ \large\sum_{i=0}^{n} \sum_{j=i}^{n} \sum_{k=j}^{n} \binom{i+m-1}{m-1}\binom{j+m-1}{m-1}\binom{k+m-1}{m-1} $$ How to solve it when this involve more than thousand summation ?