The binomial-coefficients tag has no wiki summary.
8
votes
1answer
414 views
What is $\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$
What is $$\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$$
4
votes
0answers
196 views
Double sum involving binomial coefficients
I came across a sum of binomial coefficients while trying to solve a problem involving $SU(2)$ group integrals. I am not able to solve it, nor I found a similar identity in the literature. I would ...
1
vote
0answers
151 views
An extrasensory perception strategy :-)
I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
3
votes
3answers
321 views
Estimating a sum involving binomial coefficients [refined]
Having some work done, here is a refined version of my initial question.
For integer $m>0$ and $0\le q\le m$, consider the sum
$$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$
I ...
0
votes
1answer
68 views
Bounded convolutions with binomial coefficients
I need to figure out a nice family of decaying functions such that
$\sum_{d=2}^k {k \choose d} f_k(d) \leq 1/k$ and $f_k(d)\geq f_k(d+1)$
How can I figure out what good candidates could be?
Any ...
1
vote
0answers
128 views
Asymptotic behaviour of sequence
I am interested in the sequence
$$a(n)=\sum_{k=0}^n {p(n-k)-1 \choose k}$$
where $p(n)=(r-1)n^2+(2r-1)n+r$ for some $r \in \mathbb{N}$ or more generally any polynomial equation.
When $r=1$ this ...
0
votes
1answer
219 views
Asymptotic growth for $\sum_{i=1}^{n-1}(n-i)\binom{k}{i}$ [closed]
For positive integers $n,k$, define $$f(n,k):=\sum_{i=1}^{n-1}(n-i)\binom{k}{i}.$$
What are upper and lower bounds of $f(n,k)$ by simpler terms? (e.g. finding bounds which are not a summation like ...
3
votes
1answer
210 views
Limit of sum of binomials
I'm trying to calculate the limit for the sum of binomial coefficients:
$$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$
Numerically it seems to ...
6
votes
3answers
511 views
Combinatorial identities
I have computational evidence that
$$\sum_{k=0}^n \binom{4n+1}{k} \cdot \binom{3n-k}{2n}= 2^{2n+1}\cdot \binom{2n-1}{n}$$
but I cannot prove it. I tried by induction, but it seems hard. Does anyone ...
2
votes
0answers
133 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 ...
1
vote
1answer
166 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 ...
0
votes
1answer
177 views
About the number of the elements of a set related with binomial coefficients
For $N\in\mathbb N$, let
$$P_l(N)=\# \{(n,m)|0\le n\le N, 0\le m\le n,\binom{n}{m}\not\equiv 0 \mod l\}.$$
Suppose that $\binom{n}{0}=1$ for $n\ge 0$ and that $\# S$ represents the number of the ...
8
votes
2answers
811 views
Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$
I found the following formula in a book without any proof:
$$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$
This does not seem to follow immediately from the basic ...
2
votes
3answers
551 views
An identity involving sum of probably binomial coefficients
How could I prove that
$$\sum _{m=v}^n \left(\left(\prod _{k=v}^{m-1} \frac{k^2}{m^2-k^2}\right)\left(\prod _{k=m+1}^n \frac{k^2}{k^2-m^2}\right)(-1)^{m-v}\right)=1$$
or, simplified,
$$\sum _{m=v}^n ...
0
votes
0answers
68 views
Congruences for generalized Franel numbers
Let us define generalized Franel numbers $f^{(m)}_n$ through recurrence relations:
$f^{(1)}_n=1$ for all $n$, and $$f^{(m)}_n=\sum\limits_{k=0}^n\binom{n}{k}^3f^{(m-1)}_k.$$ In fact ...
2
votes
1answer
146 views
Congruence for the Apery Numbers
Is it true that $$A_n\equiv (-1)^n\;\;(\mathrm{mod}\;3)\;\;?$$
Here $A_n$ is the Apery number:
$$A_n=\sum\limits_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2.$$
What is known about congruence properties ...
4
votes
1answer
317 views
Product of central binomial coefficients
I have a question about an equality involving products of central binomial coefficients. If $x_1,...,x_n$ and $y_1,...,y_n$ are positive integers, with $\sum_i x_i = \sum_i y_i$ and
$$ ...
4
votes
0answers
209 views
Recurrence relation for trinomial Apery numbers
It is well known (Beukers 1987) that the Apery numbers $$A_n\equiv A_n^{(2)}=\sum\limits_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2$$ satisfy the fancy recurrence relation
...
0
votes
0answers
81 views
Simplifying a finite difference sum that represents a model posterior to avoid numerical issues.
Problem
Is it possible to simplify/rewrite the following expression, preferably without explicit sums, such that it can be computed without numerical issues when the $n_*$ are in the range of ...
6
votes
2answers
442 views
Why are negative sets multisets? (Reference request)
It is easy to establish that
$$
\left({n\choose k}\right)=(-1)^k{-n \choose k},
$$
where the symbol on the left-hand-side counts the number of multisets of $k$ elements from $n$.
On the Wikipedia ...
4
votes
0answers
66 views
alternating sum with Barnes G functions
Let $B(n)=(n-2)!(n-3)!\cdots 1!$ denote the Barnes G-function.
I am pretty sure that
$$
\sum_{m=0}^{k^2-1}
(-1)^m\binom{k^2-1}m
\frac{G(k+n-m+1)}{G(n-m+1)G(k+1)(k^2)!}
= n-2k^2-2k
$$ when $k$ is ...
4
votes
1answer
216 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 ...
2
votes
0answers
164 views
Weighted sum of ratio of partial sum of binomial coefficients
I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$,
$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
2
votes
0answers
93 views
1
vote
0answers
288 views
Another identity involving sums of (alternating) binomial coefficients.
I have derived two different solutions to the same problem involving computing the expected time to find $k$ swaps when collecting coupons. However to me the two sums, although apparently numerically ...
1
vote
1answer
308 views
Estimate on sum of squares of multinomial coefficients
I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
...
17
votes
1answer
763 views
Solutions to $\binom{n}{5} = 2 \binom{m}{5}$
In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says:
On National Public Radio, the Weekend Edition program posed the
following probability problem: Given a certain number of ...
5
votes
1answer
390 views
Elementary proof for identity involving sums of binomials
Is there an elementary proof of this identity?
$$n + 1 - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+1-k}}{n^{n}} =1 + \sum_{k=1}^n \frac{n!}{(n-k)!n^k}\;?$$
The term on the right is the ...
1
vote
0answers
70 views
binomial transform, Hurwitz zeta function
For $j,n\in\mathbb Z_+$,
let
$$
L_{j,n}^{(t)}=
\sum_{m=0}^{n} \Bigl(-\frac 12\Bigr)^{n-m}{n\choose m}{m+j+1\choose m+1} \left(
\frac {1}{t+\frac 12}\right)^{m+j+2}
$$
and
$$
L_{j,n} ...
2
votes
2answers
399 views
Sum involving binomial coefficients
I have the following sum
$\sum_{j=1}^K {K \choose j} (-1)^{j+1}/j$. Now I can write this as the integral $\int_{-1}^0 \frac{(1+x)^K - 1}{x} dx$. However, I wonder whether there is a closed form ...
2
votes
2answers
127 views
A sum related to the Johnson association scheme
Hi everyone,
In the process of studying a problem in the Johnson association scheme I came across the following sum:
$$\sum_{k\geq 0}(-1)^k\binom{n}{k}\binom{a-k}{a-b}\binom{c+k}{b}.$$
All the ...
1
vote
2answers
517 views
An identity involving a sum of binomial coefficients
I am moving through a classic paper (On Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my ...
5
votes
2answers
400 views
Interpolating a sum of binomial coefficients using a sin function
While studying a problem about orthogonal polynomials I encountered the following
expressions
\begin{equation}
f(n)=\sum_{k=0}^{n}(-1)^k\binom{n+k}{2k} \frac{1}{k+1}\binom{2k}{k}
\end{equation}
and
...
0
votes
0answers
374 views
Calculating the Shapley value in a weighted voting game.
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
2answers
227 views
Multinomial Coefficient Estimates
Hello,
Let $B$ and $n$ be positive integers. Let $p_i \ge 0 $ be such that $\sum_{i=0}^{2B} p_i= 1$.
I am interested in asymptotics (in terms of $B$, $n$, and $p_i$) for the coefficients of
$
...
0
votes
1answer
251 views
Sum involving integer compositions and binomial coefficients
I came across an identity involving binomial coefficients. I'm not sure if I'm looking at the identity the wrong way but I am not aware if this identity is known and if there is an (easy) proof for ...
4
votes
0answers
232 views
A coincidence concerning Fermat primes, binomial sums, and eta quotients?
Let $w_k$ be a primitive k th root of unity, where k is a power of 2. In response to a question, Robert Israel gave the solution,
$$\sum_{n=0}^\infty \frac{(-1)^n}{\binom{kn}{kn/2}} = ...
4
votes
1answer
2k views
sum calculation
I would like to calculate, or bound from above, the following sum
$$
\sum_{i=0}^n(n-2i)^p{p \choose i},
$$
here $p\geq 2$.
Any references are very welcome.
Thank you.
2
votes
3answers
997 views
Estimating a partial sum of weighted binomial coefficients
There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$:
$$ \sum_{k=0}^{\alpha ...
0
votes
0answers
171 views
Asymtotic Complexity Analysis using logarithms and binomial coefficients
On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein et.al. they have the formula \begin{equation}\lim_{n \rightarrow \infty} ...
1
vote
1answer
264 views
(Asymptotics of) Sum involving alternating sign Chu-Vandermonde
While considering eigenvalues of a certain Cayley graph, I came across the following sum:
$$\sum_{r=0}^{d}\sum_{i=0}^{r} (-1)^{i} \binom{w}{i}\binom{n-w}{r-i}$$
where $d$, $w$, and $n$, are all ...
2
votes
2answers
784 views
alternating sum of binomial coefficients
I would like to know a closed formula for
$\sum_{j=0}^{p-n } (-1)^j\binom{n^2}{p-n-j}
\binom{n+j-1}j\binom{2n+j}{n+j+1}$, especially in the
case $p$ is near $n^2/2$. Similarly, I would like a closed ...
28
votes
3answers
2k views
A limit involving binomial coefficients?
Experimentation suggests the limit
$$\lim_{n\rightarrow\infty} (-1)^n\sum_{k=1}^n(-1)^k{n\choose k}^{-1/k}=\frac{1}{2}\ .$$
Does somebody have an idea for (a start of) a proof?
Added: There seem to ...
6
votes
0answers
295 views
Polynomials with presumably positive coefficients
The $q$-Pochhammer symbol
$(q) _ 0:=1$ and $(q) _ n:=\prod _ {j=1}^n (1-q^j)$ for $n > 0$ is clearly a polynomial in $q$ which has both positive and negative coefficients when $n>0$.
The ...
6
votes
3answers
442 views
Is there a closed formula for the generating function of some trinomial coefficients?
We learn in calculus how to obtain a sum of binomial coefficients \frac{(2d)!}{(d!)^2} in terms of a generating function
$\sum_{d \geq 0} \frac{(2d)!}{(d!)^2} x^d$
by the Taylor series of ...
36
votes
2answers
2k views
Alternating sum of square roots of binomial coefficients
Let
$$ c_n = \sum_{r=0}^n (-1)^r \sqrt{\binom{n}{r}}. $$
It is clear that $c_n = 0$ if $n$ is odd. Remarkably, it appears that despite the huge positive and negative contributions in the sum ...
6
votes
0answers
445 views
Does anyone know this sequence of polynomials?
A referee on a paper of mine showed me the following recurrence for polynomials $P_{n,k}\in\mathbb Q[q,q^{-1}]$ for $n\geq 0$ and $0\leq k\leq n/2$.
...
1
vote
1answer
289 views
Limit of an infinite series, related to (generalised Newton's) binomial expansion
How to calculate the infinite sum of the following series, related to binomial expansion for rational number, $r$:
...
6
votes
1answer
573 views
Sums of binomials with even coefficients
While looking for a closed form of a expression I worked myself to a formula that resembles the Vandermonde convolution, but is summed over even binomial coefficients only.
...
0
votes
2answers
802 views
non negative integer solutions : Diophantine Equations [closed]
I want to know the exact number of non-negative integer solutions of a1x1+a2x2+...akxk = n ...
I know that it is the co-efficient of x^n in (1-x^a1)^-1 * (1-x^a2)^-1 * ... (1-x^ak)^-1 ...
but whats ...
