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$.

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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) ...
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}...
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}\...
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}$$
-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{...
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 ...
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_{...
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 ...
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{...
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} ...
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)(...
-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

1
2 3 4 5
143