Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

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