Skip to main content

Questions tagged [binomial-coefficients]

For questions involving the coefficients involved in the binomial theorem. $ \binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

Filter by
Sorted by
Tagged with
1 vote
1 answer
21 views

$(1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j$

Let $n$ and $a$ be natural numbers. How to prove the following for $x \in [0, 1)$? $$ (1-x)^{n+a} \sum_{j=0}^\infty \binom{n+j-1}{j}\binom{n+j}{a} x^j = \sum_{j=0}^a \binom{n}{a-j}\binom{a-1}{j} x^j $$...
ploosu2's user avatar
  • 9,458
2 votes
2 answers
68 views

Deriving equation (3-66) of Papoulis and Pillai

$$ \mbox{The identity is}\quad P_{2n+2} = P_{2n} + {2n \choose n}p^{n+2}q^n - {2n \choose n+1}p^{n+1}q^{n+1} $$ $\displaystyle\mbox{where}\ P_{2n} = \sum_{k=n+1}^{2n}{2n \choose k}p^kq^{2n-k} \quad$ ...
Poi's user avatar
  • 21
0 votes
0 answers
27 views

$ (1 + z^2)w'' - 2w = 0 $ in complex space

Find the linearly independent solutions of the equation $(1 + z^2)w''-2w = 0$ in the vicinity of the point $0$. Attempt: To find the linearly independent solutions to the differential equation: $(1 + ...
Markus's user avatar
  • 1
1 vote
0 answers
37 views

number theory, binomial coefficients divisibility

Let $p$ be a prime number greater than $3$ and $n$ a positive integer. Suppose $\nu _p(n) = r$. Prove that $\dbinom{np}{p} - n$ is divisible by $p^{3+r}$ The problem is here: https://poti.impa.br/...
amkpm90's user avatar
  • 352
3 votes
1 answer
47 views

The upper bound of $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}$

As the title mentioned, I want to calculte \begin{equation} \sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}. \end{equation} Note that if $m=n$, the result is simply 1. However, when $m<n$, this seems to ...
Jobs Adam's user avatar
  • 163
-3 votes
0 answers
57 views

$\sum_{i=1}^n(-1)^{n-i}(i-x)^{n-1}{n-1\choose i-1}$ doesn't seem to depend on $x$ [closed]

Experimenting with a computer, the sum $$\sum_{i=1}^n(-1)^{n-i}(i-x)^{n-1}{n-1\choose i-1}$$ doesn't seem to depend on $x$. Is that right? Why?
kara890's user avatar
  • 85
2 votes
0 answers
101 views

How to calculate an upper bound for $\sum_{k=0}^n \binom{n}{k} \frac{(-x)^k}{\sqrt{k+a}}$

As the title mentioned, I want to get a closed-form result of \begin{equation} \sum_{k=0}^n \binom{n}{k} \frac{(-x)^k}{\sqrt{k+a}}, \end{equation} where $x\in[0,1]$ is a real number, and $a$ is a ...
Jobs Adam's user avatar
  • 163
1 vote
1 answer
72 views

Combinatoric equation involving three unknowns

Find $n\in\mathbb{N^*}$ and $p, q \in\mathbb{Q}$, such that: $$(pn+q)\binom{nk+1}{k}+(qn+p)\binom{nk+2}{k-1}+(pn+q)\binom{nk+1}{k-1}=\binom{nk+2}{k+1}$$ for $\forall k\in\mathbb{N^*}$ Here's my ...
fikooo's user avatar
  • 409
2 votes
1 answer
35 views

Prove $\lim_{n\to\infty}\binom{n}{k}\left(\frac{\mu}{n}\right)^{k}\left(1-\frac{\mu}{n}\right)^{n-k}=\frac{\mu^k}{e^\mu\cdot{k!}}$

The problem is to prove the following equality: $$\lim_{n\to\infty}\binom{n}{k}\left(\frac{\mu}{n}\right)^{k}\left(1-\frac{\mu}{n}\right)^{n-k}=\frac{\mu^k}{e^\mu\cdot{k!}}$$ This is what I have ...
Aidan Hyde's user avatar
4 votes
1 answer
132 views

What is the name of this combinatorial identity?

In the course of my physics research, I appear to have stumbled onto the following combinatorial identity: $${dn\choose m}=\sum_{\vec k} {n \choose \vec k}\,\prod_{j=0}^d {d \choose j}^{k_j},$$ where $...
David Raveh's user avatar
  • 1,835
1 vote
0 answers
44 views

Integer expression with binomial coefficients [closed]

I am trying to prove that $$ \mbox{for any natural}\ k, n,\ \mbox{where}\ k \ge n,\quad \frac{\left(2k + 1\right)\left(k + n\right)!} {\left(2n + 1\right)!\left(k - ...
Vika's user avatar
  • 467
1 vote
0 answers
19 views

Relation between mean and $\beta$ parameter of discrete Boltzmann distribution with degeneracies

I am trying to compute the mean $\bar{E}$ of a Boltzmann distribution $$ p(\pmb{x}) = \frac{1}{Z} e^{-\beta E(\pmb{x})}, $$ knowing that there is a total of $N$ microstates $\pmb{x}$ and $[\alpha N]$ ...
edfi's user avatar
  • 21
0 votes
2 answers
60 views

Lower Bound on the ratio of binomial coefficients

Let $k,n,m$ be integers such that $k>n>m$. I am interested in providing a tight lowerbound on $$ A(k,n,m)=\frac{\binom{k-m}{n-m}}{\binom{k}{n}} $$ This term arises in a probability problem that ...
MMH's user avatar
  • 714
4 votes
2 answers
157 views

Estimate a sum of binomial coefficients

I should know this by the time, but: can someone tell me how to rigorously compute the leading order (including the constant) of the following sum: $$\sum_{ 1\leq k \leq n/3 } {2 k \choose k} {n-2k-1 ...
Olivier's user avatar
  • 1,247
4 votes
1 answer
75 views

Identity regarding the sum of products of binomial coefficients.

Consider the following toy problem Person A and Person B have $n$ and $n+1$ fair coins respectively. If they both flip all their coins at the same time, what is the probability person B has more ...
Demetri Pananos's user avatar
2 votes
1 answer
56 views

Closed form for a sum of binomial coefficients

Let $m,n,r\in\mathbb{N}\cup\{0\}.$ I am interested in finding a closed form for the sum $$\sum_{i=0}^m{{n+i}\choose{r+i}}.$$ Let $f(m,n,r)$ denote the above sum. We may make a few trivial observations....
aqualubix's user avatar
  • 2,105
-1 votes
2 answers
196 views

Proving $n! = \sum_{j=0}^n (-1)^j \binom{n}{j}(x+n-j)^n$ for any $x \in \mathbb{R}$ [closed]

How to prove the formula $$n! = \sum_{j=0}^n (-1)^j \binom{n}{j}(x+n-j)^n$$ for all $x \in \mathbb{R}$? I tried to use the binomial formula, but I am stuck with the problem. Thank you in advance for ...
phibqt310's user avatar
-3 votes
1 answer
80 views

Expansion of a function $(1-x)^{-n}$ [closed]

Write the expansion of the series: $(1-x)^{-n}$. I haven’t got the solution
Srinivasa Reddy's user avatar
2 votes
3 answers
80 views

What is the number of lattice paths of length 16 from the point (0,0) to (8,8) that go through (4,4) but don't go through (1,1), (2,2), (3,3)

what is the number of lattice paths of length 16 from $(0,0)$ to $(8,8)$ that go through $(4,4)$, don't go through $(1,1), (2,2), (3,3)$, and don't go over $y=x$? Here's what I tried: since we can't ...
user avatar
1 vote
2 answers
90 views

Alternating sum involving binomial coefficients

I want to prove that $$ \sum_{i=0}^{n}{n\choose i} \frac{\left(1 + \alpha i\right)^{n} \left(-1\right)^{n - i}}{n!} = \alpha^{n}. $$ This is a guess based on the computations for $n = 0,1,2,3$. Do you ...
stackQandA's user avatar
0 votes
1 answer
29 views

How to Derive the Binomial Coefficient Upper Bound and Final Inequality in "Scheduling Multithreaded Computations by Work Stealing"?

In the paper Scheduling Multithreaded Computations by Work Stealing under the section "Atomic accesses and the recycling game", it mentions the binomial coefficient approximation: $$ \binom{...
grzhan's user avatar
  • 3
0 votes
0 answers
32 views

Finding the sum of a series using the binomial theorem [duplicate]

If $(1+x+x^2)^n = a_{0} + a_{1}x+a_{2}x^2 + ... + a_{2n}x^{2n}$, prove that $a_{0}^2-a_{1}^2+a_{2}^2+...+(-1)^{n-1}a_{n-1}^2= \frac{1}{2}a_{n}(1-(-1)^na_{n})$. I was able to find the value of $a_{0}^2-...
CallousCalculus's user avatar
1 vote
2 answers
66 views

Find constant for asymptotic equivalence (Stirling's formula)

Find constant $A$ such that $C_{n^2}^{n} \sim A\frac{n^{2n}}{n!}$ Writing $C_{n^2}^{n}$ using Stirling's formula gives $C_{n^2}^{n} \sim \frac{n^{2n}}{\sqrt{2\pi}\sqrt{n-1}} \sim \frac{n^{2n}}{\sqrt{2 ...
John Doe's user avatar
1 vote
0 answers
61 views

Closed expression for $\sum _{m=1}^n{{n+m}\choose n} $ [duplicate]

I was given a problem in University: Let $n\in \mathbb N $. Find a closed expression for the following sum $\sum _{m=1}^n{n+m\choose n}$. I expressed binomials ${n+m}\choose {n}$$=\frac{(n+1)(n+2)......
Hrackadont's user avatar
1 vote
3 answers
141 views

Evaluate: $\sum_{i=1}^{\lfloor (n+1)/2\rfloor}i\binom{n-i+1}{i}$

Is there a closed form of the expression $$ \sum_{i = 1}^{\left\lfloor\left(n + 1\right)/2\right\rfloor} i\binom{n - i + 1}{i} $$ My Attempt: From what I observe it is a situation where there are $n/...
Maverick's user avatar
  • 9,481
4 votes
0 answers
121 views

Calculating $\sum\limits_{k=0}^n\binom{n}{k}/\left(2^k+2^{n-k}\right)$

I am trying to find a closed form for $\sum\limits_{k=0}^n\frac{\binom{n}{k}}{2^k+2^{n-k}}$. I saw on quora that integration can be used to rewrite portions of such equations, and so I attempted this. ...
plywood98's user avatar
2 votes
1 answer
60 views

How to apply Vandermonde's Identity regarding summation bounds ? $\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\binom{-k-j-2}{n-j-k}$

from the answer: Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$ this happens from step 4 to 5: $$ \sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\...
Mr. Doge's user avatar
  • 123
2 votes
3 answers
267 views

A game requires 2 players opposite 2 other players, with 6 people available, how many distinct games can take place?

There are 6 people. A game that requires one pair vs another pair to play is to take place - how many unique games can take place? My Way: 6C2 pairs = 15, and 15C2 distinct matche between each ...
rummy rummyrum's user avatar
2 votes
2 answers
84 views

Limit of $\sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k$ as $n\to \infty$ (and $k=n$)

Question Find $\lim_{n\to \infty} P(n,n)$ where $$ P(n,k) = \sum_{j=0}^n (1-j){n\choose j} \frac{1}{(n-1)^j}\left( \frac{n-j}{n} \right)^k. $$ The origin of this sum is from this question. The ...
ploosu2's user avatar
  • 9,458
2 votes
1 answer
75 views

Prove the following combinatorics equality [duplicate]

$$\mbox{Prove the equality:}\quad \binom{n}{k + m + 1} = \sum_{j = k + 1}^{n - m} \binom{j - 1}{k}\binom{n - j}{m} $$ for $m + k < n$. I tried to prove this using combinatorics and doing some ...
perenqi's user avatar
  • 169
4 votes
1 answer
41 views

Combinatorial proof that $\sum_{k=1}^{n} k {2n \choose n+k}=\frac{1}{2}n{2n \choose n}$ [duplicate]

I'd like to find a combinatorial/algebraic proof of the identity: $$\sum_{k=1}^{n}k{2n \choose n+k}=\frac{1}{2}n{2n \choose n}$$ The only proof of this that I've been able to find on the Internet, ...
N. S.'s user avatar
  • 81
5 votes
2 answers
337 views

Sum of iid random variables

Iid random variables $Y_1, Y_2, \dots, Y_{50}$ take only the values $0$, $1$ and $2$ with probabilities $\mathbb{P}(Y_i = 0) = \mathbb{P}(Y_i = 1) = \frac{4}{9}, \mathbb{P}(Y_i = 2) = \frac{1}{9}$. ...
ABlack's user avatar
  • 578
4 votes
1 answer
131 views

Reducing product of powers of logarithm

I am trying to show that $$(\log(a))^n (\log(b))^m = P(\log(a^ib^j)), \quad i,j \in \{-1,0,1\}$$ where $P$ is a polynomial and $n \ge m \ge 1$ are natural numbers. Using Binomial identities for the ...
Sam's user avatar
  • 3,260
0 votes
1 answer
94 views

Seeking Reference for Identity Involving Binomial Coefficients [closed]

I'm seeking a reference for the following identity: Given positive integers $a_i,b_i$ for $i=1,\ldots,k$ satisfying the conditions: \begin{align} a_1&\leq b_1\\ a_1+a_2&\leq b_1+b_2\\ &\...
Jivid's user avatar
  • 555
-1 votes
0 answers
54 views

how to prove $\binom{n}{k}\binom{k}{m}=\binom{n}{m}\binom{n-m}{k-m}=\binom{n}{k-m}\binom{n-k+m}{m}$ ($m\leq k\leq n$) by story

$\binom{n}{k}\binom{k}{m}=\binom{n}{m}\binom{n-m}{k-m}=\binom{n}{k-m}\binom{n-k+m}{m}$. ($m\leq k\leq n$) is very easy to verify. We can write $\binom{n}{k}\binom{k}{m}=\frac{n!}{k!(n-k)!}\times\frac{...
Ginkgo's user avatar
  • 145
1 vote
0 answers
29 views

At what values ​of $p$ will the chain be recurrent?

Consider a Markov chain on $\mathbb{Z}$ with $p_{i,i+2} = p$ and $p_{i,i−1} = 1 − p$. At what values ​​of $p$ will the chain be recurrent? I know that a chain is recurrent if for any state $j$ $$\sum\...
ABlack's user avatar
  • 578
2 votes
4 answers
152 views

A Combinatoric Identity Involving Binomial Coefficients: $\sum^{n}_{r=1} {n \choose r} (-1)^r \frac{2^r-1}{2r}= \sum^{n}_{r=1}\frac{(-1)^r}{2r}$

Recently I came across this combinatoric identity: $$ \begin{equation} \sum^{n}_{r=1} {n \choose r} (-1)^r \frac{2^r-1}{2r} \end{equation} = \sum^{n}_{r=1}\frac{(-1)^r}{2r} $$ I have verified that ...
Slice's user avatar
  • 23
-4 votes
0 answers
25 views

Summation of coefficient [duplicate]

I wish to calculate : $\sum_{r=0}^{p}\binom{n-r}{r}$ where $p=n/2$ if n is even and $p=(n-1)/2$ where n is an even number.
Vijay's user avatar
  • 3
1 vote
1 answer
51 views

Hint for a combinatorial proof of $n! \binom{n-1}{k-1} = \sum_{j=0}^n \overline{s}_{n,j} \tilde{S}_{j,k}$

To clarify notation, we have $\overline{s}_{n,j}$ the unsigned Stirling numbers of the first kind, meaning the number of permutations on an set with $n$ elements that has exactly $j$ cycles. $\tilde{S}...
Dominic Michaelis's user avatar
1 vote
2 answers
203 views

How to prove that for $a,b \in \mathbb{C}$, $\sum\limits_{k=0}^n \binom{a}{k}\binom {b}{n-k}= \binom{a+b}{n}$?

This exercise came from Complex Analysis by Freitag and Busam 1.2.11. $$\binom{a}{n}:= \prod_{j=1}^n\frac{a-j+1}{j} $$ Show: $\sum\limits_{\nu=0}^{\infty}\dbinom{\alpha}{\nu} z^\nu$ is absolutely ...
pie's user avatar
  • 5,917
1 vote
0 answers
30 views

Proving an Identity on Partitions with Durfee Squares Using $q$-Binomial Coefficients and Generating Functions

Using the Durfee square, prove that $$ \sum_{j=0}^n\left[\begin{array}{l} n \\ j \end{array}\right] \frac{t^j q^{j^2}}{(1-t q) \cdots\left(1-t q^j\right)}=\prod_{i=1}^n \frac{1}{1-t q^i} . $$ My ...
Allison's user avatar
  • 195
0 votes
0 answers
35 views

Finding $\sum_{r=0}^n \binom{k}{2r}$ to solve a problem [Black Book by Vikas Gupta]. [duplicate]

The question goes as such: The number $N = {}^{20}C_{7}-{}^{20}C_{8}+{}^{20}C_{9}-{}^{20}C_{10}+.....-{}^{20}C_{20}$ is divisibly by: (A)$3$ $ $ (B)$4$ $ $ (C)$7$ $ $ (D)$19$ There are ...
Bongo Man's user avatar
  • 322
0 votes
1 answer
74 views

Expressing a combination as sums of three terms or more, analogous to Pascal's identity

Are there any ways to express binomial coefficients as the sum of three or more terms, similar to how Pascal's Identity breaks a combination into the sum of two terms by relating two adjacent binomial ...
someone's user avatar
  • 11
6 votes
2 answers
261 views

Counting bit strings with given numbers of higher-order bit flips

Background information Bit flips Given a bit string, we say that bit flip happens when $0$ changes to $1$ or $1$ changes to $0$. To find bit flips, we can shift the string by $1$ and xor that new ...
Valeriy Savchenko's user avatar
2 votes
1 answer
152 views

Finding Closed Forms for a System of Recurrence Relations

I am working on a problem that involves a system of recurrence relations with two functions, $A'$ and $A''$. The relations are defined as follows: $$ \begin{align*} A'_{n,k,m} &= A'_{n-1,k-1,m} + ...
Valeriy Savchenko's user avatar
1 vote
3 answers
79 views

Combinatorical identity $\sum_{k = d-i}^d (-1)^{k-d+i} \binom{k}{d-i} \cdot \binom{n}{d-k} = \binom{n-d+i-1}{i}$

How do we proove the following ugly identity of binomial coefficients? $$\sum_{k = d-i}^d (-1)^{k-d+i} \binom{k}{d-i} \cdot \binom{n}{d-k} = \binom{n-d+i-1}{i}$$ First I thought we could use ...
Lukas's user avatar
  • 141
0 votes
0 answers
38 views

Understanding the Derivation of a Formula Involving Binomial Coefficients and Factorials

I'm studying a formula that involves binomial coefficients and factorials, and I'm struggling to understand how it was derived. The image below is a screenshot from the paper. They are taking the ...
Dotman's user avatar
  • 316
5 votes
2 answers
153 views

$\sum_{n=1}^{\infty} \frac{n 4^n}{(2 n-1)^2(4 n+1)(4 n+3)} \frac{\binom{2 n}{n}}{\binom{4 n}{2 n}}=\frac{4(1+\sqrt{2})}{225}$ [closed]

I want to show that $\sum_{n=1}^{\infty} \frac{n 4^n}{(2 n-1)^2(4 n+1)(4 n+3)} \frac{\binom{2 n}{n}}{\binom{4 n}{2 n}}=\frac{4(1+\sqrt{2})}{225}.$ I tried manipulating the terms in the sum, but that ...
Sam's user avatar
  • 3,260
0 votes
1 answer
89 views

summation of series (might include binomial)

For $a>0$ and $b>a+1$, then $\sum_{n=1}^\infty \frac{a(a+1)...(a+n-1)}{b(b+1)...(b+n-1)}$. I've tried writing the numerator and denominator in terms of factorial then multiplied and divided by n!...
Looping outlaw's user avatar
5 votes
2 answers
85 views

Similarity between Combinatorial Series and Recursions

I was evaluating the sum $$a_n = \sum_{k=0}^{n} {2n+1 \choose 2k+1} 2^{3k}$$ The method I went about was treating $$a_n = \frac{1}{2\sqrt{2}} \sum_{k=0}^{n} {2n+1 \choose 2k+1} (2\sqrt{2})^{2k+1} \\ ...
omega's user avatar
  • 53

1
2 3 4 5
156