Questions tagged [binomial-coefficients]
Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
4,504 questions
3
votes
0answers
19 views
Rational fraction expression for triangular powers of 2
Why does the following pattern hold?
$$1=1=2^0$$
$$\frac{2(2^2-1)}{3}=2=2^1$$
$$\frac{3^2(3^2-1)(3^2-2^2)}{3^2 \times 5}=8=2^3)$$
$$\frac{4^2(4^2-1)^2(4^2-2^2)(4^2-3^2)}{3^3 \times 5^2\times 7}=64=...
0
votes
0answers
22 views
Summation of combinatorial expression
While trying to solve a question, i think it just boils down to calculating
$$\sum_{i=1}^{k} {{n-k + 1} \choose i} \cdot 2^i$$
And since the constraints are very strict $n$ ~ $10^9$, $k$ ~ $10^3$, ...
0
votes
0answers
15 views
Closed form for a series involving binomial coefficients
I am unable to find a closed form for $\sum\limits_{r=1}^{min(n-k+1, k)} {2^r}{{n-k}\choose r-1}{{n-k+1}\choose r}$. Any help would be appreciated.
0
votes
0answers
35 views
Combinatorial Meaning of the Binomial Coefficient $s\choose k$?
I am wondering if there is a combinatorial meaning of the binomial coefficient $s\choose k$, which is defined as $${s\choose k}=\frac{s(s-1)(s-2)\cdots(s-k+1)}{k!},$$
where $s$ is a real number and $k$...
3
votes
0answers
46 views
Reasoning about the lower bound of ${{2n}\choose{n}}$
A standard lower bound is ${{2n}\choose{n}} > \frac{4^n}{2n}$. For example, see this Wikipedia article.
It occurs to me that for higher $n$ using elementary arguments, this can be greatly ...
3
votes
1answer
78 views
$\int_{-\infty}^{\infty}{x\choose t}dt=2^x$ for $x\geq0$??
I noticed that on Desmos, for $m>0$ and $x\geq0$, $$\int_{-m}^{m}{x\choose t}dt$$ closer and closer approximated $2^x$. So, does
$$\int_{-\infty}^{\infty}{x\choose t}dt=2^x$$
Assuming that ${x\...
1
vote
0answers
29 views
Verify this Proof: $\sum_{k=0}^{n}{n\choose k}=2^n$ via Taylor series
I've found this proof which I am quite proud of. Am I missing anything?
Theorem: $$\sum_{k=0}^{n}{n\choose k}=2^n$$
Proof:
Let $\beta\in\{t\in\Bbb R:t>0\}$, and $f(x)=x^\beta$ be continuous on ...
1
vote
0answers
19 views
Binomial's extensions
In some questions about polynomials, I've found the following formula:
$\binom{a}{k}=\sum_{j=0}^k\binom{a-b}{j}\binom{b}{k-j}$
This can be gotten of the coeficient of $x^k$ in $(1+x)^a$ and in $(1+x)...
6
votes
1answer
78 views
Calculating the $\sum_{x=1}^\infty\left[\prod_{k=0}^s{s\choose k}x^k\right]^{-1}$
Question: If $s \in \mathbb{N}$ is it true: $\sum_{x=1}^\infty\left[\prod_{k=0}^s{s\choose k}x^k\right]^{-1}={\zeta\left[{s+1 \choose 2}\right] \above 1.5pt \prod_{k=1}^s{s \choose k}};$ where $\...
0
votes
0answers
18 views
binomial coefficient [on hold]
Please help me solve this problem, I want to make sure I understand permutations correctly before I move on.
Question is: Assume you are choosing a class schedule and you need to take 2 science ...
2
votes
3answers
88 views
Proving If $k \le \left\lfloor \frac{n}{2} \right\rfloor$ then $\binom{n}{k-1} < \binom{n}{k}$
So I'm trying to do a proof for this problem:
If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} < \binom{n}{k}}$$
I can do it algebraically but ...
-1
votes
1answer
34 views
Prove by induction… With exponent and factorial [on hold]
Could someone please help me to prove this by induction?
$$ \left(1+\frac{1}{1}\right) ^1\cdot \left( 1+\frac{1}{2}\right)^2\cdot...\cdot\left( 1+\frac{1}{n-1}\right)^{n-1}=\frac{n^n}{n!}, $$ for $...
0
votes
0answers
26 views
Estimating a double series
I am having problems to analyse the behavior (for big $m$) of a (kind of) double series (a little difficult one). The problem is the following:
Fix $N\in\Bbb N$ and take $p\in \Bbb N$ as big as you ...
1
vote
1answer
22 views
How can I find the Coefficent of a term when I am multiplying two binomial expansions?
For Example, what is the coeffecint of $x^{-1}$ in the expansion of
$$
(\frac{1}{2x}+3x)^5(x+1)^4\text{?}
$$
How can I find the coefficient without expanding by hand?
-2
votes
1answer
87 views
Evaluating the sum of $\sum_{k=0}^n \binom{n}{k}^2$ [duplicate]
I don't know if this question is trivial but let me put it in the first place.
I'm trying to find the sum of $\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n-1}^2+\binom{n}{n}^2$ or ...
0
votes
0answers
18 views
How to calculate the probability of rolling X or less on Y dice
For example, if I have 3 (six-sided) dice and I want to know the probability of rolling 4 or less, how would I calculate that? I want to use a spreadsheet and take as input X and Y, so I'm looking ...
10
votes
1answer
144 views
+50
Coefficients of binomial continued fractions
For a natural number $n$, let
$$
\begin{equation}
\beta_n(z)=\frac{(1+z)^n+(1-z)^n}{(1+z)^n-(1-z)^n}.
\end{equation}
$$
Then the coefficients of the numerator and denominator of $\beta_n$ are binomial....
3
votes
1answer
47 views
Double sum of binomial coefficients quotients
How to prove the following formula?
$$\sum_{j=0}^{n-1} \sum_{k=0}^{j} \frac{{n}\choose{k}}{{n-1}\choose{j}} = 2^{n-1}\sum_{j=0}^{n-1} \frac{1}{{n-1}\choose{j}}$$
I tried induction and manipulating ...
1
vote
1answer
43 views
Combinatorial interpretation of alternating sum involving binomial coefficients
I was working on proving the following fact of probability. Suppose $A_1,\dots,A_n$ are events, and define
\begin{align*}
S_1 &= \sum_{1\le i \le n}P(A_i) \\
S_2 &= \sum_{1\le i < j \le n}P(...
1
vote
3answers
41 views
Prove central binomial coefficient upper bound
I am trying to prove that $\binom{2n}{n} < \frac{4^n}{\sqrt{2n}}$. I tried induction, but with no effect (all I can get to is $(2n+1)(2n+2) < 4\sqrt{n(n+1)}$ which is false)
1
vote
1answer
35 views
Calculate central q-Binomial coefficient
Is there any way to calculate the central q-Binomial coefficient efficiently.
For example, $$\binom{2n}{n}_1=\frac{(2n)!}{(n!)^2}$$
First few values of $\binom{2n}{n}_2$ are $1,3,35,1395,200787,...
1
vote
1answer
110 views
How do you define the PMF for 5 cosses of a fair coin and a biased coin?
Joe has two coins, $A$ and $B$, in front of him. The probability of Heads
at each toss is $p=.5$ for coin $A$ and $q = .9$ for coin $B$. Joe chooses
one of the two coins at random with both ...
0
votes
1answer
52 views
limits involving scary roots of binomial coefficients products
Calculate the following limit :
$$ \lim_{n\to \infty}\left[\frac{\sqrt[n+1]{^{n+1}C_{1}\cdot^{n+1}C_{2}\cdots^{n+1}C_{n+1}}}{e^{\frac{n+1}{2}}(n+1)^{-\frac{3}{2}}}-\frac{\sqrt[n]{^{n}C_{1}.^{n}C_{2}\...
2
votes
1answer
69 views
Prove $\binom{n}{2}+\binom{n}{3}\cdot7+\binom{n}{4}\cdot7^2+…+7^{n-2}\in \mathbb{Z}$ for all $n\geq 2$
If $X=\{8^n-7n-1:n\in \mathbb{N}\}$ and $Y=\{49(n-1):n\in \mathbb{N}\}$ then show that $X⊂Y$
While solving the problem
$$8^n-7n-1=(1+7)^n-7n-1\\
=49\bigg[\binom{n}{2}+\binom{n}{3}\cdot7+\binom{n}{4}\...
0
votes
4answers
56 views
How to prove divisibility of a number using the binomial expansion? [closed]
I have the following problem:
Prove that $6^n-1$ is always divisible by 5 using the binomial expansion of $(5+1)^n$.
How can I do this? I don't know how to begin, as I don't see how the binomial ...
1
vote
3answers
46 views
Why does $(x+y)^p=x^p+y^p$ over $\mathbb{Z_2}$?
My first thought was to expand it with the binomial theorem and then see that all the coefficients are $0$ mod 2 except the first and the second, but this is not true, unless i'm missing something. ...
0
votes
3answers
67 views
Evaluating a Binomial Coefficient Limit: $\lim_{n\to\infty} 2^{-2n} \binom{2n}{n}$.
Can anyone quickly help me evaluate the limit:
$$\lim_{n\rightarrow\infty} 2^{-2n} \binom{2n}{n}$$
I know it follows from Stirling's approximation, but I cannot quite arrive at the answer.
Thanks....
1
vote
0answers
38 views
Proof of $\sum_{i=0}^{k}{{n-i-1}\choose {k-i}}={n\choose k}$ [duplicate]
So, I would like to prove the following:
$$\forall n,k\in\mathbb{N}_0, n\geq k+1: \sum_{i=0}^{k}{{n-i-1}\choose {k-i}}={n\choose k}$$
First of, i exploited trivial symmetry of the binomial ...
2
votes
1answer
75 views
+50
Determinants of products of binary matrices and binomial coefficients
Consider two binary semi-infinite matrices with obvious patterns:
$$
C=
\begin{bmatrix}
1 &0 &0 &0 &0 &0 &0 &\cdots\\
1 &0 &0 &0 &0 &0 &0 &\...
-1
votes
2answers
52 views
Finite sums in Pascal's triangle [closed]
Today I was solving finite sums in Pascal's triangle see here
Here are some examples for finite sums in wikipedia: enter link description here
But I couldn't solve these two ones:
Prove that $$\...
2
votes
1answer
40 views
Calculate probability using inclusion-exclusion and deduce formula for binomial coefficicient
We choose uniformly a group of $k$ people selected from $n$. For $m \leq k$, calculate using inclusion-exclusion the probability that $m$ special people are in the group and then deduce that
\begin{...
0
votes
0answers
37 views
Finding the sum of Binomial Coefficients
The question says to find the value of $$\binom{n}{1} \cdot \left( \sum ^1 _ {r=0} \binom{1}{r}\right) + \binom{n}{2} \cdot \left( \sum ^2 _ {r=0} \binom{2}{r}\right) + \binom{n}{3} \cdot \left( \sum ^...
0
votes
1answer
37 views
Calculating Pascal's Triangle N-th row - why does this work? [closed]
I encountered this solution to the problem in the title (calculate Pascal's Triangle $N$-th row). The main point is the calculation within the loop - I am trying to figure out the meaning of it:
...
0
votes
2answers
54 views
Probability of getting full house in five-card poker when cards in suite is missing
What is the probability of getting full house in five-card poker given the following cards are missing?
Missing cards: $\heartsuit$2, $\heartsuit$5, $\heartsuit$10, $\heartsuit$Jack, $\heartsuit$King
...
3
votes
1answer
72 views
An application of this binomical identity $ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} $
I need a clarification on this manner, in terms of "When do I apply this form of
identity". I managed to proove it algebraically and combinatorially, using
"Pascal's triangle". so a proof is not ...
0
votes
1answer
36 views
Are there combinatorial identities for the sum of “equal step sampled binomial coefficients”?
Are there combinatorial identities for the sum of "equal step sampled binomial coefficients" ?
Here "equal step sampled binomial coefficients", I referred to something like:
${\displaystyle {\binom ...
0
votes
0answers
58 views
Polynomial coefficients for $\prod\limits_{i=1}^{n - 1}\frac{N-i}{N}$
Given,
$$
\prod\limits_{i=1}^{n - 1}\frac{N-i}{N},
$$
such that $n \leq N$, I know the first two terms of the expansion are
$$
1 - \frac{{n \choose 2}}{N}.
$$
What is the general formula for ...
1
vote
1answer
41 views
How to mathematically prove: $\sum_{x = r}^{n} C(x , r) = C(n+1 , r+1)$.
The RHS is equal to the number of ways of selecting $r+1$ out of $n+1$ objects.
If I sum the number of selections when the $(r+1)$th (i.e. the last) selection is the at the $(x+1)$th position, I get ...
2
votes
3answers
52 views
Finding a particular coefficient in a polynomial
I'm trying to get the coefficient of $x^6$ of this polynomial product:
$$x^2(1+x+x^2+x^3+x^4+x^5)(1+x+x^2)(1+x^2+x^4).$$
I know with infinite series, you can use the closed form solution of the ...
4
votes
2answers
116 views
Proving formula sum of product of binomial coefficients
I have to proof the following formula
\begin{align}
\sum_{k=0}^{n/2} {n\choose2k} {2k\choose k} 2^{n-2k} = {2n\choose n}
\end{align}
I tried to use the fact that ${2n\choose n} = \sum_{k=0}^{n} {n\...
2
votes
0answers
24 views
Simplify a weighted average with enumerations as weights
Could you help me simplifying the following expression:
$$\forall l \ge 0, \forall n_1,n_2 \gt 0, \forall k_1 \in [[0,n_1l]],\forall k_2 \in [[0,n_2l]],$$
$$m_{l,n_1,n_2}(k_1,k_2) = \frac{\sum_{i=0}^l ...
29
votes
3answers
1k views
Questions on a self-made theorem about polynomials
I recently came up with this theorem:
For any complex polynomial $P$ degree $n$:
$$ \sum\limits_{k=0}^{n+1}(-1)^k\binom{n+1}{k}P(a+kb) = 0\quad \forall a,b \in\mathbb{C}$$
Basically, if $P$ ...
12
votes
1answer
258 views
What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?
What is known about the asymptotics, lower and upper bound of the sum of the binomial coefficients
$$
S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}
$$
where the sum runs ...
-2
votes
2answers
47 views
Binomial Coefficients Proof Help
I'm having trouble doing these proofs. So far I've changed the N choose R into its factorial form and have simplified but I'm stuck.
$\left( \begin{array} { c } { n } \\ { r } \end{array} \right) = \...
5
votes
4answers
85 views
Proving $\sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = -1$ by induction
I would like to prove this $$\sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = -1$$ for all $n \in \mathbb{N} $.
I started by replacing consecutively $n$ by $1, 2, 3$, one at a time, and verified that all of ...
3
votes
3answers
81 views
How to find the value of $r$ such that $\frac{1}{\binom{9}{r}} - \frac{1}{\binom{10}{r}} = \frac{11}{6\binom{11}{r}}$?
Find the value of $r$:
$$\frac{1}{\dbinom{9}{r}} - \frac{1}{\dbinom{10}{r}} = \frac{11}{6\dbinom{11}{r}}$$
I'm not sure where I should take this problem in order to isolate $r$. I seem to get many ...
2
votes
0answers
64 views
Reference request for some determinants of binomial coefficients
Let $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ be a Catalan number and $n$ and $k$ be non-negative integers.
Consider the following identities:
$$ \det\left(\binom{i+j+k}{2j}\right)_{0 \leq i,j\leq {n-1}}=\...
2
votes
1answer
52 views
Is there a general formula for the sum of combinations?
I am learning statistics, and I'm doing some stuff with combinations. Some of the questions I have seen have answers which are equal to a sum of combinations. It made me wonder, is there a formula for ...
3
votes
2answers
88 views
Number of ways to add up $1$s, $0$s and $-1$s to a given number
I stumbled upon this problem when preparing a lecture about random walks. The problem is as follows:
Suppose we have a sequence of $n$ numbers, and each of them can be $1$, $0$ or $-1$. What is the ...
2
votes
1answer
39 views
Proof of Gaussian coefficients identity
I want to show the identity $\bigl[\!\begin{smallmatrix} n \\ k \end{smallmatrix}\!\bigr]_q=\bigl[\!\begin{smallmatrix} n-1 \\ k-1 \end{smallmatrix}\!\bigr]_q+q^k\bigl[\!\begin{smallmatrix} n-1 \\ k \...
