Questions tagged [binomial-coefficients]
For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.
79 questions
5
votes
2
answers
379
views
Asymptotic rate for $\sum\binom{n}k^{-1}$
This MO question prompted me to ask:
What is the second order asymptotic growth/decay rate for the sum
$$\sum_{k=0}^n\frac1{\binom{n}k}$$
as $n\rightarrow\infty$?
- 43.2k
5
votes
1
answer
685
views
Summing ratio of ratio of partial sums of binomial coefficients
I would like to approximate the following when $n \gg k$.
$\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
The formula can be re-written ...
- 83
4
votes
0
answers
168
views
How to prove the following equation (which involves binomials and determinant of 2×2 matrices)?
I have tried many ways to prove the following equation, such as the method of induction and expanding all the terms in the summation,but things got more complicated.I could not find an appropriate ...
- 41
4
votes
1
answer
505
views
How to calculate this summation $\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $?
Question: How to calculate this summation $S=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $? Where $m<n_1,m<n_2$
Remark1: When $a=b$, I know the above summation $S=a^m\sum_{k=0}^m {...
- 57
4
votes
0
answers
312
views
Positivity of a finite sum involving Stirling numbers of the first kind
Past days I've been trying to prove that certain polynomials have positive coefficients. After a lot of thinking, I came up with a formula for each coefficient individually, and they are not that ugly....
- 1,889
4
votes
2
answers
7k
views
Partial Sum of the Binomial Theorem [duplicate]
The binomial theorem states $\sum_{k=0}^nC_n^kr^k=(1+r)^n$. I am interested in the function \begin{equation}
\sum_{k=0}^mC_n^kr^k, \quad m<n
\end{equation}
for fixed $n$ and $r$, and both $m$ and $...
- 41
3
votes
1
answer
194
views
Effective Realization of GCD of middle binomials?
So, it is well-known that
$$ \gcd \left(\binom{m}{k}\mid 1\leq k\lt m \right) = e^{\Lambda(m)}$$
which can incidentally be sparsified for prime $p$
$$ \gcd \left(\binom{p^{r+1}}{1},\binom{p^{r+1}}{p^...
- 731
3
votes
0
answers
144
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
- 13.4k
3
votes
0
answers
151
views
Combinatorial interpretation of inverse modulo $2$ binomial transform of A284005
My question is related to the following:
Sum with products turned into subsequences
We have an identity
$$a(n, -1) = \sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\...
- 4,938
3
votes
3
answers
493
views
Show that the ratio of limits converges to the nearest Riemann zeta zero except when the ratio is a singularity
Let $h(s,n)$ be:
$$h(s,n)=\lim_{c\to 1} \, \frac{(-1)^{n-2}}{(n-2)!}\zeta (c)^{n-2} \sum _{k=1}^{n-1} \frac{(-1)^{k-1} \binom{n-2}{k-1}}{\zeta ((c-1) (k-1)+s)}$$
and let $g(s,n)$ be:
$$g(s,n)=\lim_{c\...
- 1,183
3
votes
0
answers
585
views
Sum of binomial coefficients weighted by a lower incomplete regularized gamma function
The following summation turned up in the course of my research:
$$S_n=\sum_{k=0}^n {n \choose k}\lambda^k P(k,t)$$
where $P(k,t)=\frac{1}{\Gamma(k)}\int_{0}^t e^{-x}x^{k-1}dx$ is the lower ...
- 907
2
votes
1
answer
909
views
Upper bound of sum of binomial coefficients
I am looking for an upper bound - up to constant factor - for:
$\sum_{k=t}^{t+l} {n \choose k} \cdot 2^{-n}$ where:
The values of $t$ are between: $\frac{n}2+\sqrt{n} \leq t \leq \frac{9n}{10}$. (...
- 23
2
votes
1
answer
236
views
An integer sequence related to Pascal’s triangle
We need someone expert in binomial coefficients (subject 11B65) to recognize the integer sequence generated by an iterative formula we have encountered while working on a project about Pascal’s ...
- 125
2
votes
1
answer
344
views
Show that $\sum_{i=0}^{2k} [ {n\choose i+1} + (-1)^{i+1}{n+i+1\choose i+1} ] \sum_{j=0}^i {i\choose j}(-1)^j (i+1-j)^{2k} =0.$
Let $u(k,j) = 1$ if $j=0$, $0$ if $j > k$, or else it is $j*u(k-1,j-1) +(j+1)*u(k-1,j) $. Prove that $ \sum_{i=0}^{2k} {n \choose i+1} u(2k,i) +\sum_{i=0}^{2k} {-n-1 \choose i+1} u(2k,i)=0. $ ...
- 1,109
2
votes
1
answer
147
views
Tight sublinear estimates for a triple partial binomial summation
Is there tight estimates for the following logarithmic summation ($\gamma,\gamma'\in(0,1)$ and $\mu,\mu'>0$)
$$\log_2\Bigg(\sum_{t=\frac{n^{}}2-n^\gamma\sqrt{\mu\ln n}}^{\frac{n^{}}2+n^\gamma\sqrt{...
- 1,826
2
votes
1
answer
235
views
Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution
$\mu=1+\epsilon$ where $\epsilon>0$ holds.
1.Is there a good bound for $$T=\frac{\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}^2}{2^n}?$$
This quantity can be ...
- 1,826
1
vote
1
answer
3k
views
Coefficients in the sum $\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j=n^{2m+1}, \ m=1,2,....$
Consider a sum $$\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j$$
which returns an odd power $n^{2m+1}$ of $n$, for $\ m=0,1,2,...$ given fixed $A_{0,m}, \ A_{1,m}, \ ..., \ A_{m,m}$. The ...
- 167
1
vote
0
answers
95
views
On level-$12$ of the McKay-Thompson series of the Monster and the Domb numbers
(This continues from level 10.) Given some moonshine functions $j_{N}$. There are nice descending and consistent relations for levels $6m$ with $m= 2,3,5,$
$$j_{12A} = \left(\sqrt{j_{12H}} + \frac{\...
- 12.6k
1
vote
0
answers
116
views
On level $6$ of the McKay–Thompson series of the Monster and Apéry numbers, et al
After the McKay–Thompson series of levels $1$, $2$, $3$, $4$ of the Monster were mentioned in this MO post, level $6$ has very interesting relations as well. (Level 10 is in this post.)
I. Level-6 ...
- 12.6k
1
vote
2
answers
165
views
A conjecture on 'truncated joint moments' of binomial coefficients under binomial distribution
This is similar in spirit to Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution but gives some total estimates. Though the other ...
- 1,826
1
vote
1
answer
124
views
Tight estimates for binomial summation
Is there tight estimates for the following logarithmic summation ($\gamma\in(0,1)$)
$$\ln\Bigg(\sum_{t=\frac{n^{}}2-\gamma n^\gamma}^{\frac{n^{}}2+\gamma n^\gamma}\sum_{\ell=\frac{n^{}}2-\gamma n^\...
- 1,826
1
vote
1
answer
2k
views
How to calculate such sum of product of binomial coefficient?
..I wonder if the following formula can be calculated?
$
\sum_{k=0}^m {m \choose k} {2k \choose n}
$
- 351
1
vote
2
answers
368
views
Closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$
For all natural numbers $a$, is there a known closed form of $ \sum_{i=1}^{n-k} {n-1-i\choose k-1}i^a + \sum_{i=1}^k {n-1-i\choose n-1-k}$, where $k$ is fixed?
For example, letting $k=1$ gives the ...
- 1,109
0
votes
1
answer
705
views
Asymptotic behaviour of Binomial Sum
I am interested in the behaviour of:
$\gamma_k=\sum_{i=0}^{k} {n \choose i}$
as n becomes large and where $k$ could potentially be a function of $n$ rather than a constant. One line of attack I can ...
- 103
0
votes
1
answer
330
views
Sum of the first m terms of the expansion $(x+y)^n$
Let $S(x, y, m, n) = \sum\limits_{i=0}^m \binom{n}{i}x^i y^{n-i}$, where $0 < m < n$. I want to derive the relation between $S(x, y, m, n)$ and $S(x, y, m, n-1)$.
Is there any formulas I can use?...
- 113
0
votes
2
answers
328
views
Closed form for a binomial product sum
Is there any closed formula for the binomial product sum
\begin{align*}
\sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{n-j+1, n-j+2, \cdots, n-1\}}}\binom{n}{i_1}\...
0
votes
0
answers
174
views
3D generalization of Gaussian q-binomial coefficient
It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...
- 34.3k
0
votes
1
answer
208
views
Local behavior of the Vandermonde convolution
An interesting combinatorial identity is the Vandermonde convolution identity:
$$ \sum_k {n\choose k}{m\choose s-k} = {n+m \choose s},$$
which can be proved by considering the coefficients in $(x+1)^{...
- 5,230
-1
votes
3
answers
312
views
Binomial Coefficients sum [closed]
Any idea on whether or not $$\sum_{i = 0}^b(-1)^i\binom{b}{i}\binom{a+b-i-1}{a-i}$$
has a closed formula on $a$ and $b$ (and on what it is, in case it does)?
It is supposed that $b \le a$.
- 369