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$.
6,335
questions
-4
votes
0answers
21 views
I need help simplifying a term, I think it's related to Newton's Binomial & Combinatorics [closed]
Here's said term :
I am not sure how to go about this. I would appreciate help. Thank you.
0
votes
2answers
32 views
find $p$ that maximizes $P[X = 10]$ where $X$ is the total number of attempts.
Suppose we keep tossing a coin until we see $4$ heads, and suppose that the probability of
seeing a head on each toss is an unknown value $p$. If we actually perform this experiment and get the fourth ...
1
vote
0answers
20 views
How to maximize both of these expressions with respect to $A$ and $B$
I wish to maximize
\begin{equation}
f(A,B) = \dfrac{\dbinom{A+B-a-b}{A-a}}{\dbinom{A+B}{A}}\qquad\text{and}\qquad g(A,B) = \dfrac{\dbinom{A-a}{x-m}\dbinom{B-b}{y-n}}{\dbinom{A+B}{x+y}}
\end{equation}
...
0
votes
1answer
41 views
Evaluating $\lim_{m \to \infty} \binom{m}{k} \cdot 2^{-m}$ for $0 \leq k \leq m$.
I am attempting to evaluate the limit $\lim_{m \to \infty} \binom{m}{k} \cdot 2^{-m}$ for $0 \leq k \leq m$, and I have been able to confirm via Mathematica that this limit is indeed 0. How would one ...
0
votes
1answer
25 views
Fraction manipulation and binomial coefficients
I am working through a proof and I do not understand why the following equation holds:
$$\frac{m(m-1)(m+1)}{6} = \binom{m + 1}{3}$$
relative to the following definition of the binomial: $$\binom{n}{k} ...
6
votes
3answers
127 views
Prove that a certain sum of binomial coefficients is divisible by a power of 2
As many will recognize the following expression is a closed form for the Fibonacci numbers. Can it be proved that
$$\frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} \quad \text{...
1
vote
1answer
68 views
Using binomial theorem to express $ \frac{1}{\sqrt{5}} \ [((\sqrt{5}/2)+(1/2))^{10} - (-(\sqrt{5}/2)+(1/2))^{10}]$ as a single finite series
I am trying to write
$$\frac1{\sqrt5}\left[(\frac{\sqrt5}2+\frac12)^{10}
- (-\frac{\sqrt5}2+\frac12)^{10}\right]
$$
as a single finite series of the form $\sum^{10}_{j=0}a_j$, where $a_j$ depends on $...
0
votes
1answer
90 views
Proof of $C_n = \frac{1}{n + 1} \binom{2n}{n}$
I want to comprehend the first proof of $C_n = \frac{1}{n + 1}\binom{2n}{n}$ on Wikipedia. Link: here.
I have problems with two steps:
$$\sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}y^n = \sum_{n=0}^{\...
-1
votes
0answers
12 views
Binomial Expansion ratio of two terms
In the expansion of (2+x/k^2)^18, the coefficients of x^6and x^7are in the ratio 7:54. Find the possible values of k
1
vote
1answer
52 views
Maximize $\binom{N-m}{n-k}/\binom{N}{n}$ with respect to $N$
The question is actually in the title. I wish to maximize this function with respect to $N$, where $m, n$ and $k$ are fixed naturals less than $N$ and also $k\le \min(m,n)$. How do I go about proving ...
6
votes
2answers
46 views
Radius of Convergence of $(1-x)^{1/4}$
This is my first post so I am very new to MathJax formatting - i apologize in advance for the messy formatting
This equation becomes $$\sum_{n=2}^\infty \frac{(4n-5) x^n}{(4^n)n!}$$
The textbook says ...
1
vote
2answers
34 views
How to prove ${2n \choose n} = 2\cdot (2n-1) \cdot \frac{1}{n} {2(n-1) \choose n-1}$?
I've been staring at this identity which appears in my textbook for a while. Plugging in numbers I can verify that this is true, however I have no idea how this was determined or proved? Is there a ...
0
votes
1answer
49 views
Why is this sum equal to 1?
I'm sorry for opening a new question for a triviality, but I couldn't find this result online.
The following holds:
$$\sum_{j=0}^{n-1} {\dfrac{ {{K-1}\choose{j}} {{N-1-(K-1)}\choose{n-1-j}} } {{N-1}\...
3
votes
1answer
58 views
Simplifying the sum of a product of multinomial coefficients
From the multinomial theorem the following holds
$$
\sum_{k_1 + k_2 + \ldots + k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n
$$
I have the following sum
$$
\sum_{\substack{k_1 + k_2 + \ldots + k_m ...
3
votes
2answers
72 views
Calculate $2 C_{n}^{k-1} + 3 C_{n}^{k-2} + 4 C_{n}^{k-3} + … + (k + 1)C_{n}^{0}$
Are there any easy ways to calculate this?
$$ \sum_{i=1}^{k} (i + 1) \cdot C_{2k}^{k-i} = 2 C_{2k}^{k-1} + 3 C_{2k}^{k-2} + 4 C_{2k}^{k-3} + ... + (k + 1) C_{2k}^{0} $$
I tried to "turn" the ...
0
votes
0answers
34 views
Simplifying $ \prod_{i=1}^k b_i!\cdot \left(x-b_i\right)! $
I have the following product
$$
\prod_{i=1}^k b_i!\cdot \left(x-b_i\right)!
$$
where $x, b_i$ are positive integer values.
How can I simplify it so that it can be calculated in an easier way without ...
-1
votes
0answers
17 views
Prove that $\sum_{k=0}^m {m \choose k} {n+k \choose m} = \sum_{k=0}^m {m \choose k} {n \choose k} 2^{k}$? [duplicate]
Preferably a combinatoric proof would be helpful.
4
votes
1answer
45 views
What is the combinatorial interpretation for this expression$ \sum_{i=0}^{n} (-1)^{i} \binom{n}{i} = 0$ [duplicate]
What is the combinatorial interpretation for this expression $$\sum_{i=0}^{n} (-1)^{i} \binom{n}{i} = 0\:?$$
1
vote
1answer
58 views
Show that $\sum_{k=0}^N\binom{N}{k}x^k(1-x)^{N-k}(1-\alpha k/N)^{-1}$ is decreasing in $N$
I've come across the following sum of binomial coefficients:
$$S = \sum_{k = 0}^N \binom{N}{k}x^k (1-x)^{N-k} \frac{1}{1 - \alpha \frac{k}{N}},$$
where $x \in [0, 1]$ and $\alpha \in [0, 1)$.
I need ...
0
votes
0answers
17 views
Differentiation of a product involving divided differences
In 'Collocation at Gaussian Points' by DeBoer (top of p601):
We have a function $h_{t}(u) = G(t, u)r[\tau_{1}, ..., \tau_{k}, u]$ being considered on an interval $[a, b]$ where: $G(t, u)$ is a Green's ...
0
votes
1answer
51 views
For integers $n,r$, let $\binom nr = \begin {cases} \binom nr & n\ge r\ge 0 \\ 0 & \text{otherwise} \end {cases}$
For integers $n,r$, let $\binom nr = \begin {cases} \binom nr & n\ge r\ge 0 \\ 0 & \text{otherwise} \end {cases}$. Find the maximum value of $k$ for which the sum $\sum_{i=0}^k \binom {10}{i} \...
3
votes
3answers
88 views
Identity on the sum $\sum_{i=1}^{n-2}{i-1 \choose k}{n-2-i \choose k-1}={n-2 \choose 2k}$
I need to evaluate the first summation for $k\geq1$ and $n\geq2$.
Some computer calculations allow the identification with the expression ${n-2 \choose 2k}$
above but, how can it be derived? Are there ...
-1
votes
3answers
67 views
Evaluating $\sum_{t=0}^{1000}(-1)^t \binom{2000}{2t}$
Calculate the sum $$\sum_{t=0}^{1000}C_{2000}^{2 t}(-1)^{t}$$
Please kindly help me or show me how to do this.
$$\sum_{t=0}^{1000}C_{2000}^{2 t}(-1)^{t}=\sum_{t=0}^{1000}C_{2000}^{2 t}(i)^{2t}$$
$$\...
2
votes
2answers
75 views
Induction for binomial coefficients
I would like some help to prove the following equality :
$$\sum_{i=0}^n \binom{n}i^2=\binom{2n}n$$
I wanted to do a proof by induction :
$$\sum_{i=0}^{n+1} \binom{n+1}i^2=1+\sum_{i=1}^{n+1} \binom{n+1}...
-2
votes
0answers
30 views
Odds of getting 5 heads in a row out of 45 tries [closed]
With a probability of .515 of landing heads, what are the odds that I get 5 heads in a row out of 45 tries?
0
votes
0answers
23 views
Number of Routes and Valid Routes within a 2D grid w/ obstacles
9x9 Grid w/ Start, Goal, and U-Shaped Obstacle
Take this 9x9 grid with a start location (0, 0), goal location (9,9), and U-shaped obstacle at (2,3), (3,3), (4,3), (2,4), and (4,4), how would I tackle ...
7
votes
1answer
59 views
How many arrangements of red and blue balls are there so that, the number of red balls with: the ball immediately to the right is also red, is $9$.
The question is too long to fit in the title, but I tried.
$50$ balls: $23$ indistinguishable red balls; $27$ indistinguishable blue balls. The balls are arranged in a line. How many distinct ...
0
votes
1answer
36 views
Limit involving multiple factorials
Let $n, k\in\mathbb N_0$ be fixed (where $k\leq n$), and $S_N\in\mathbb N$ be a sequence such that $\lim_{N\to\infty} S_N/N=p$ for some fixed $p\in(0,1)$.
Show that $$\lim_{N\to\infty} \frac{S_N! (N-...
1
vote
0answers
27 views
Find the coefficient of $x^{9\ }$ in$\left(1+x\right)\left(1+x^{2}\right)\left(1+x^{3}\right)…\left(1+x^{100}\right)$ [duplicate]
This is a question from binomial theorem. How do i approach these problems, can we find the coefficient of any arbitrary power of x, if there is some particular concept linked to these problems? ...
1
vote
0answers
55 views
Is there a tight bound on following binomial summations involving squares on arithmetic progressions?
The summations of interest is following:
$$\sum_{i=0}^{\lfloor\sqrt n\rfloor}\binom{n}{i^2}$$
$$\sum_{i\in\{a,q+a,2q+a\dots,\lfloor\sqrt n\rfloor\}}\binom{n}{i^2}$$
where $q<n$ and $a\in\{0,1,\dots,...
-2
votes
1answer
45 views
How does he get $3^kn^k/k!$ from that binomial formula? [closed]
How does he get $3^kn^k/k!$ from that binomial formula?
0
votes
4answers
77 views
Evaluating $\sum_{r \in \mathbb{N}} (n-2r+1)^2 \binom{n}{2r-1}$
I am seeking to evaluate the sum $$S=\sum_{r \in \mathbb{N}} (n-2r+1)^2 \binom{n}{2r-1} \\ =(n-1)^2 \binom{n}{1}+(n-3)^2 \binom{n}{3}+(n-5)^2\binom{n}{5}+\cdots$$
I re-wrote the sum as $$S=(n+1)^2\...
0
votes
1answer
56 views
Binomial Coefficient $\sum_{k=0}^n {2n \choose 2k}{2k \choose k}{2n-2k \choose n-k} $
I am trying to find the sum
$$\sum_{k=0}^n {2n \choose 2k}{2k \choose k}{2n-2k \choose n-k} $$
I know the closed-form answer and I could derive it based on the form of the answer in terms of the ...
0
votes
1answer
34 views
Let $u_n=\sum_{r=0}^n (-1)^r \frac{\binom nr}{x+r}$ at $x=2$. Then find the sum to infinity of $u_1+u_2..$
Can I get a hint on how to begin the solution? I tried all possible derivative/integral methods of forming the general sum using the expansion of $(1+x)^n$, but I am just not able to the get $2+r$ in ...
6
votes
3answers
209 views
Pascal's triangle curiosity
I noticed the following pattern in the rows of Pascal's triangle:
$$
1 = 11^0\\
11 = 11^1\\
121= 11^2\\
1331= 11^3\\
14641=11^4
$$
at this point I thought maybe this pattern would follow indefinitely, ...
-1
votes
0answers
33 views
Name of sequence $(-1)^k n!/k!, k\leq n$? [closed]
What is the name of the sequence $n!/k!$, $k\leq n$ ?
1
vote
2answers
50 views
Obtain the coefficient of $x^2$ in the expansion of $1+\frac{6}{2x+1}+\frac{5}{2-3x}$
Hello so this is a 2 part question and I managed to express that praction as a partial fraction which was equaled to $$1+\frac{6}{2x+1}+\frac{5}{2-3x}$$ I will add my work below I tried lot to Obtain ...
1
vote
0answers
46 views
Why $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k} = 4^k$? [duplicate]
I was checking some theoretical properties with a concrete example. At some point, I needed to use Wolfram Alfa in order to get the equality
$$\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k} = 4^k .$$
...
0
votes
0answers
35 views
General quotient rule for a couple of special functions
problem formulation
Given a discrete probability density $\{p(i)\}_{i=0}^\infty$, let $G(z)$ be the following power series (called probability generating function)
\begin{equation}G(z)\triangleq \sum_{...
3
votes
2answers
104 views
Expectation of X choose k
Let $X$ be a random variable, assume that we know $\mathbb{E}\left[ X \choose k \right] $.
Can I assume
$$ \mathbb{E}\left[ X \choose k \right] = {\mathbb{E}\left[ X \right]\choose k}$$ as k is not ...
0
votes
1answer
32 views
How to solve this (binomial?) series?
Im struggling with this equation. Could someone maybe explain how to get this solution?
$ \sum_{k=1}^{\infty} \binom{-k}{k-1} (p(p-1))^{k-1} = \frac{1}{2p-1}$
My first idea was to use the binomial ...
2
votes
1answer
27 views
Arithmetically weighted sum of half of the combinatorial numbers
I would like to see a proof for the identity
$$\sum_{k=1}^n k\binom{2n}{n+k} = \frac{n}{2}\binom{2n}{n}$$ This was suggested by the OEIS sequence (https://oeis.org/A002457), but I haven't been able to ...
0
votes
1answer
59 views
Show that ${n \choose \lambda n} p^{\lambda n}q^{ \mu n}\approx \frac{2^{-nD\left(\lambda || p\right)}}{\sqrt{2\pi \lambda \mu n}}$
I have the following problem:
Use the Stirling formula $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}$ to show that
$${n \choose \lambda n} p^{\lambda n}\left(1-p\right)^{\left(1-\lambda\right)...
3
votes
2answers
87 views
How do I show that $ \sum_{r=0}^q {n \choose q-r} {n-q+r \choose r}(-1)^r = 0 $? [duplicate]
I am hoping to show that
$$ \sum_{r=0}^q {n \choose q-r} {n-q+r \choose r}(-1)^r = 0 $$
for integers $n \geq 1$ and $1 \leq q \leq n$.
I've worked out a few examples and it seems reasonable that it ...
4
votes
2answers
72 views
Calculate $\sum_{i=0}^\infty i\binom{i+10}{i}(\frac{1}{2})^i$
I'm not great with summation and its various techniques, so go easy on me. If someone can point me in the right direction I would be very grateful.
This is the sum in display mode: $$\sum_{i=0}^\infty ...
1
vote
1answer
46 views
Can't understand why (n-1)choose(-1) equals zero.
I have tried to wrap my head around the idea but I can't seem to get it, and google yields no coherent explanation. Would appreciate some clarification about this.
2
votes
4answers
111 views
Words of length $10$ in alphabet $\{a,b,c\}$ such that the letter $a$ is always doubled
Compute the number of words of length $10$ in alphabet $\{a,b,c\}$ such that letter $a$ is always doubled (for example "$aabcbcbcaa$" is allowed but "$abcbcaabcc$" is forbidden).
...
2
votes
1answer
90 views
If $p\geq 5$ is Prime, Prove that $\binom{p^2}{p}-p$ is a multiple of $p^5$
If $p\geq 5$ is Prime, Prove that $$\binom{p^2}{p}-p$$ is a multiple of $p^5$
I started using the fact that:
$$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$$
So we have:
$$\binom{p^2}{p}-p=\frac{p^2}{p}\...
1
vote
1answer
59 views
Combinatorial proof of a sum with binomial coefficients
I would like to prove $\sum_{k=0}^{n}{k {n \choose k}}=n2^{n-1}$ with a combinatorial proof, once I already know to prove it algebrically. I thought about it in the following way:
Consider a set $S=\{...
-1
votes
2answers
36 views
Generalising $\sum_{r=0}^{n}r^{k}{n\choose r}$ for $k\in \mathbb{Z^{+}}$
I am trying to generalise the closed form expression for $k$ of the following sum using diffferentiation techniques.
$$\sum_{r=0}^{n}r^{k}{n\choose r}$$
We know the following results through trivial ...
