Questions tagged [binomial-coefficients]
Coefficients involved in the Binomial Theorem. $ \dbinom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
7,128
questions
0
votes
1
answer
27
views
Probability of all n koalas climbing up (1,2,...,m) trees other than trees i and j?
Let i and j be distinct elements in (1,2,...,m). What is the probability of all n koalas climbing up (1,2,...,m) trees other than trees i and j?
My approach was to find the probability that no sloths ...
- 1
0
votes
1
answer
56
views
Sum of coefficients in the expansion of $(2x+3y-2z)^n$.
Sum of coefficients in the expansion of $(2x+3y-2z)^n$ is $2187$ then the greatest coefficient in the expansion of $(1+x)^n$.
I put $x=y=z=1$ in the expansion. So, sum of coefficients became equal to ...
- 76
0
votes
0
answers
34
views
Sum of the indices of Pascal's triangle up to k? [duplicate]
We are all familiar with Pascal's triangle.
1
11
121
1331
14641
...
Conveniently, each row is actually all the coefficients of $n \choose k$ for row $n$. So row 0, is $0 \choose 0$, row 1 is $1 \...
- 2,383
3
votes
0
answers
63
views
Applying the Stirling's formula on $\binom{n}{k}$
In class we used the following estimate:
$$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{(1+\mathcal{O}(1))\sqrt{2 \pi n} \frac{n}{e}^n}{(1+\mathcal{O}(1))\sqrt{2 \pi k} \bigl(\frac{k}{e}\bigr)^k \sqrt{...
- 3,094
3
votes
0
answers
50
views
A limit involving binomial coefficients and square roots
I am trying to evaluate the following limit
$$\lim_{n\to\infty}\frac{1}{2^n\sqrt{n}}\sum^n_{k=1}\binom{n}{k}\sqrt{k},$$
but to no avail. I experimented with some large values of $n,$ and it seems like ...
- 73
0
votes
0
answers
72
views
Show that $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \left(1+\mathcal{O}\bigl(\frac{1}{n}\bigr)\right)$
Show that $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \left(1+\mathcal{O}\bigl(\frac{1}{n}\bigr)\right)$.
Hint: It might be useful that for $f,g: \mathbb{N} \rightarrow \mathbb{R}_{\ge 0}$ with $f(n) = \...
- 3,094
0
votes
1
answer
69
views
How do I evaluate this series? $\sum_{i=1}^{m-6}(i+2)\binom{2i-1}{i}\frac{1}{m-2-i}\binom{2m-2i+6}{m-i+3}$
I'm working on a study about nonlinear reccurence.
$a_1 = 1, a_2 = 3, a_3 = 12, a_4 = 50, a_5 = 210$
I'm trying to find the general term of $a_m$ and I found that it follows the recurrence
$a_{m+1}=\...
- 9
0
votes
1
answer
38
views
How many ways to a form a team of $11$ members?
Find the number of ways of selecting $11$ member cricket team from $7$ bats men, $6$ bowlers and $2$ wicket keepers so that the team contains $2$ wicket keepers and atleast $4$ bowlers.
My attempt:-
...
- 1,393
5
votes
3
answers
144
views
A series sum involving Catalan numbers
I was trying to compute $$\sum_{k=0}^{n} \left(-\frac{1}{2}\right)^k \, \binom{2k}{k} \, \frac{k}{k+1} = \sum_{k=0}^n \left(-\frac12\right)^k k C_k$$
(where $C_k$ is the $k^{\rm th}$ Catalan number) ...
- 51
0
votes
0
answers
38
views
Name for a Power Series with Binomial coefficient
I am hoping this is a relatively simple question to answer but does the following series have an accepted name (e.g. Taylor series, Maclaurin series, etc.)
$$\sum_{k=0}^n \binom{n}k a^k$$
I have a ...
- 1
0
votes
0
answers
76
views
How to simplify $\sum_{k = n}^{2n} \binom kn^2 $ [closed]
I arrived at this expression while solving a question. I don't have any ideas to simplify this $\sum_{k = n}^{2n} \binom kn^2.$
I know the following expressions and their results but unable use them.
$...
- 11
0
votes
0
answers
25
views
Simplify summation of binomial coefficients
I was trying to check if the reasoning in this question is correct: Remarks on Lucas–Lehmer test.
Given an odd prime $p$ , is it possible to simplify this summation?
$\sum\limits_{k=1}^{\lfloor{2^{p-2}...
- 504
0
votes
1
answer
34
views
Factoring out a coefficient from binomial
I watched a youtube video (I cannot find it anymore) however, the author showed that the following binomial equation could be factored (If I remembered it correctly.)
$$\binom{n}{n+2k}=\binom{n}{n+k}\...
- 149
0
votes
0
answers
33
views
bijective proof that $\sum_{k=0}^n {2k \choose k} {2(n-k)\choose (n-k)} = 4^n$ [duplicate]
Provide a combinatorial proof that $\sum_{k=0}^n {2k \choose k} {2(n-k)\choose (n-k)} = 4^n.$
It might be easier to find a non-combinatorial proof first (e.g. a proof by induction). For the bijective ...
- 1,509
0
votes
0
answers
32
views
Does summing over even upper indexes of a binomial have a closed form? $\sum_{0 \le i < n} \binom{2i}{k}$
The even and odd sums can be determined from each other:
$$\sum_{0 \le i < n} \binom{2i}{k} + \sum_{0 \le i < n} \binom{2i+1}{k} = \binom{2n}{k + 1}$$
- 11
-1
votes
0
answers
72
views
$ {n\choose1} + {n\choose5}+{n\choose9} + \ldots$ [duplicate]
Can anyone give me a hint and best help with the solution? I know that you have to use complex numbers in a clever way, but I have no idea what expression to consider.
Let $n$ be a fixed natural ...
- 109
1
vote
0
answers
54
views
Reference request: gcd of binomial coefficients
Let $n > 1$. What is a good reference for the following fact?
$$\mathrm{gcd} \left\{\binom{n}{k} : 0 < k < n \right\} = \begin{cases} p & n = p^m \text{ is a prime power} \\ 1 & \text{...
- 149k
2
votes
0
answers
97
views
Probability of runs with cyclical criteria in Bernoulli trials
I am considering an extension of a previously posed problem, for which I have a hand-wave solution. I would like to determine whether the solution is exact and if not, need help with a rigorous ...
1
vote
0
answers
18
views
Tight bound on a binomial like sum [duplicate]
I'm looking for a tight bound on: $$\sum_{k=0}^r {n\choose k}$$ where I can assume that $r<n$.
Looking at the pascal triangle I understand that $n\choose n/2$ might be the largest element among the ...
- 31
1
vote
0
answers
29
views
Alternating product of binomial powers on descending natural numbers
While trying to prove something completely different I noticed a strange combinatorial result looks like it would follow:
For $n, t\in \mathbb{N}$ with $n\geq 2$ and $t \geq 1$
$$
\frac{(n)^{^{n-t}C_{...
- 11
0
votes
0
answers
18
views
Test whether data generating process is the sum of values selected by doing n choose k [closed]
I have a given sample from an experiment. I want to do two things.
First, test the null hypothesis that the data generating process of this population is doing, for each observation, the following: (i)...
2
votes
5
answers
82
views
Prove that $2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$ using double counting. [duplicate]
Using a combinatorial proof (counting the same thing in different ways), show that:
$$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$
I was thinking of having some set $A$ where $|A| = n$, and then ...
- 29
1
vote
0
answers
54
views
Proof explanation, no two subsets of a set are subsets of each other
I have a question about the following proof:
Question: Recall that there are $2^n$ subsets of an $n$-element set. For example, when $n = 4$, there are $2^4 = 16$ subsets of a 4-element set. Of these ...
- 335
3
votes
1
answer
74
views
Is this proof of $\binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k} $ valid?
I want to show that :
$$\binom{n}{k}+\binom{n}{k-1} = \frac{(n+1)!}{k!(n+1-k)!}$$
Here is my proof : $\forall 0\leq k\leq n$ :
$$\begin{align}
\binom{n}{k}+\binom{n}{k-1} &= \frac{n!}{k!(n-k)!} + \...
- 119
1
vote
3
answers
74
views
How to prove an asymptotic estimate for $n \choose k$, where $k = \mathcal{o}(n^{2/3})$?
Let $k = k(n)$ such that $k \rightarrow \infty$ as $n \rightarrow \infty$, but $k = \mathcal{o}(n^{2/3})$. Use Stirling's formula $$n! = (1+\mathcal{o}(1))\sqrt{2\pi n} \biggl(\frac{n}{e}\biggr)^n$$
...
- 3,094
0
votes
2
answers
63
views
How does ${n \choose k}$ relate to $2^n$ in asymptotic notation?
What would be an asymptotic (big-O) notation for ${n \choose k}$ which puts it into perspective with $2^n$?
EDIT: for $k$ constant, this post states ${n \choose k} = \Theta(n^k)$. I'm searching for a ...
- 323
0
votes
1
answer
38
views
Number of ways to choose $m$ boys and $k$ girls from $n$ boys and $n$ girls?
Suppose there are $n$ boys and $n$ girls and we want to choose $m$ boys and $k$ girls such that $k \le m$. Then there are $\binom{n}{m} \binom{n}{k}$ ways to do it. Now, using counting in two ways, I ...
- 1,181
0
votes
1
answer
37
views
Ways to colour elements of matrix using two colours
Let $A$ be a $n \times n$ matrix and suppose we want to colour elements of this matrix using black and white colours. Since each element can be either white or black, so total number of ways are $2^{n^...
- 1,181
-1
votes
0
answers
19
views
Sum of N choose K for all k = 1 through n [duplicate]
I see a lot of versions of this problem, but I do not see ones exactly like this. When I use Wolfram Alpha, I get
,
but I do not know the proof of this. What is the proof?
- 1
1
vote
1
answer
84
views
Problem in deriving $\binom nk=\frac{n!}{k!(n-k)!}$ through recurrence relation.
I tried to derive through intuition the value of $n$ choose $k$ but got stuck
my observations were
$\binom n2=n(n-1)/2$,
$\binom n1=n$,
$\binom nn=1$,
I quickly developed a recursive relation
$\binom{...
- 25
1
vote
1
answer
63
views
Show for $n$, $k$ $\in$ N, such that 1 $\leq k \leq n$, $\sum_{k = 1}^{n}\binom{n}{k}\binom{n}{k-1} = \frac{1}{2}\binom{2n+2}{n+1} - \binom{2n}{n}$ [duplicate]
We are given a hint to show that both sides are equal to $\binom{2n}{n+1}$
For the right side, I have computed that
$$\frac{1}{2}\binom{2n+2}{n+1} - \binom{2n}{n}$$
$$=> \frac{(2n+2)!}{2((n+1)!)^2} ...
- 39
4
votes
2
answers
193
views
$\binom{54}{5}+\binom{49}{5}+\binom{44}{5}+\cdots+\binom{9}{5}$
How to calculate the sum
$$\binom{54}{5}+\binom{49}{5}+\binom{44}{5}+\cdots+\binom{9}{5}$$
I wrote this as $$\sum_{r=2}^{11}\binom {5r-1}{5}$$
$$=\frac{1}{120}\sum_{r=2}^{11}(5r-1)(5r-2)(5r-3)(5r-4)(...
- 1
-3
votes
1
answer
57
views
Could someone please help me with this proof? Can't think of an idea [closed]
Prove:
$$\sum^k_{r=0}C^{r}_mC^{k-r}_n = C^{k}_{m+n}$$
3
votes
1
answer
75
views
Does $\sum_{j=0}^n\sum_{k=0}^n\binom{j}{a}\binom{k}{b}\binom{n-j-k}{c}=\binom{n+1}{a+b+c+2}?$
I'm working on a problem,
(a) Let $a,b,n\geq1$ with $a+b\leq n$. By considering choosing $a+b+1$ numbers from the set $\{0,1,...,n\}$, and the possibilities for the number in position $a+1$ when the ...
- 1,727
2
votes
3
answers
92
views
Choosing 2 color pairs from 6 balls
I saw an example for choosing a full house from a deck of cards. The formula used was: $$\binom{13}{1}\binom{4}{2}\binom{12}{1}\binom{4}{1}\over\binom{52}{5}$$
In order to gain some intuition for why ...
- 201
-5
votes
1
answer
101
views
Can Someone tell me where I went wrong in this proof
The question asked to find the solution to $ \sum_{k=1}^{n}(2k+1)\binom{n}{k}$. Here's what I did:
By the binomial theorem, we know that $ \sum_{k=1}^{n}\binom{n}{k}x^k = (1+x)^n$.
Set $x=x_1^2$. Then ...
5
votes
1
answer
79
views
Is it allowed to consider "invalid" binomial coefficients as 0 (in a proof)?
I want to prove (for the natural numbers) $$ \sum_{k=0}^n \binom{n}k = 2^n$$ by induction. In the induction step I want to apply this formula: $$\binom{n + 1}k = \binom{n}k + \binom{n}{k - 1}$$ This ...
- 165
0
votes
1
answer
69
views
An identity between summations involving a binomial expansion.
Could someone give me some hint to prove that this equality is an identity?
It's not about homowork; it has arisen in a development and what I want is to go from RHS to the LHS, since the LHS is the ...
0
votes
1
answer
37
views
Double summation over binomial coefficients
I tried to solve $\displaystyle \sum_{j=0}^{n} \sum_{i=j}^{n} \binom{n}{i} \binom{i}{j}$. Unfortunately, I cannot succeed in doing so. It comes with a hint that says: "Interchange the sums and ...
1
vote
0
answers
41
views
Binomial collisions algorithm
I am looking for an efficient algorithm to find collisions in the pascal triangle with repeats $\ge 4$.
Definition of a collision:
let (n, k, m, l) with 2<=k<= (1/2)*n and 2<=l<=(1/2)*m. A ...
0
votes
0
answers
16
views
Unable to prove binomial based identity related to succesive difference between nth power of numbers? [duplicate]
https://youtube.com/shorts/I0WF5-a2B7g?feature=share
I was trying to prove a mathematical identity that I come up with after watching the above video.
$$\sum_{k=0}^n (-1)^k \binom{n}{k}(n-k+M)^n =n! \\...
0
votes
2
answers
121
views
Hints on evaluating this infinite sum
Can someone give some hints on how to evaluate this sum:
$$\sum_{n=0}^\infty \binom{2n+2}{n}\left(\frac{2}{3}\right)^n\left(\frac{1}{3}\right)^{n+2}$$
I came across this sum when I was solving a ...
- 189
-2
votes
1
answer
81
views
What are all the integral solutions to $\binom{x}{6}+\binom{y}{6}=z^n$ with $n≥2$?
Background: The equation $\binom{x}{6}+\binom{y}{6}=z^n$ is studied here. Here the task is to completely solve this Diophantine equation with $n≥2$.
Are there infinitely many nontrivial solutions to ...
2
votes
2
answers
71
views
Provide a combinatorial argument for the following: $2^n = \sum_{k\text{ odd}} \binom{n+1}{k}$ [duplicate]
I'm trying to find a combinatorial proof (and algebraic too but that's optional) of the following result:
Let $S = \{2k+1 | 0 < 2k+1 ≤ n+1\}$
$$2^n = \sum_{k\in S} \binom{n+1}{k}$$
I was thinking ...
- 669
1
vote
2
answers
107
views
Is Pascal's Rule the only such identity?
I am wondering if Pascal's Rule is the only such identity in which
$$\binom{a}{b}+\dbinom{c}{d} = \binom{n}{m}$$
Precision aside on the expression above, in general I am wondering if there exist non-...
- 9,872
0
votes
2
answers
64
views
Asymptotics of a sum involving factorials
I'm interested in the large-$n$ behavior of the sum
$$a(m,n) = \sum_{k=0}^m \frac{x^k}{k! (n-k)!}$$
- 61
0
votes
1
answer
33
views
Leading order of a combination of binomials
I would like to determine the leading order in $n$ of this combination of binomial probabilities:
$$ f(n) = \sum_{k=0}^{n-1} \sum_{l=0}^{k} \sum_{m=0}^{k} \frac{P_l P_m}{P_k}$$
where $P_k = { n \...
- 61
0
votes
1
answer
39
views
Prove that $\sum_{j=0}^R {R+N-j-1 \choose N-1}(j+1) = {N+R+1 \choose N+1}, \quad N \geq 1, R \geq 0$
I have written $\sum_{j=0}^R {R+N-j-1 \choose N-1}(j+1)$ as ${N-1 \choose N-1}(R+1) + {N \choose N-1}(R) + \dots + {R+N-1 \choose N-1}(1)$. This then turns into
$$\frac{1}{0!}(R+1) + \frac{N}{1!}(R) + ...
- 304
7
votes
4
answers
284
views
Binomial transform of fibonacci sequence is negated fibonacci sequence proof
I'm trying to prove that the following relation holds
$$
\sum_{j=0}^n \binom{n}{j}(-1)^j F_j = -F_n
$$
Where $F_i$ denotes the $i$-th finonacci number. I'm currently trying an induction argument but I ...
- 73
3
votes
1
answer
97
views
Alternative proof for ${pn \choose n}{qn \choose n} \ge {pqn \choose n}$ inequality
Reading this question, I saw that for $p,q,n$ positive integers the following inequality holds:
$${pn \choose n}{qn \choose n} \ge {pqn \choose n}$$
The inequality is not tight.
A simple combinatorial ...
- 2,309