# Tagged Questions

**0**

votes

**1**answer

72 views

### Maximize combinatorial sum for boolean function

I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...

**1**

vote

**0**answers

94 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...

**2**

votes

**1**answer

164 views

### Combinatorial sum (Author and generalization?)

In a book I have met one interesting equation (without reference):
$$\frac{m!}{n!}\sum_{i=0}^n(-1)^i{n\choose{i}}{x+m+n-i\choose{m}}=\begin{cases}
x+n+1,\, if \,m=n+1
\\
1,\, if \,m=n
\\
...

**0**

votes

**0**answers

85 views

### Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = ...

**4**

votes

**0**answers

238 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

**0**answers

156 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

**3**answers

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

**2**

votes

**2**answers

301 views

### Asymptotic behaviour of sequence

I am interested in the sequence
$$a(n)=\sum_{k=0}^n {p(n-k) \choose k}$$
where $p(n)$ is a polynomial equation.
When $p(n)=n$ this reduces to the Fibonacci sequence, but what about when $p(n)$ is ...

**6**

votes

**3**answers

530 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

**0**answers

159 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

**1**answer

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

**7**

votes

**2**answers

844 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

**3**answers

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

**4**

votes

**1**answer

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

**6**

votes

**2**answers

449 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

**0**answers

67 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

**1**answer

228 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

**0**answers

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

**1**

vote

**1**answer

343 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

**1**answer

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

**2**

votes

**2**answers

430 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

**2**answers

135 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

**2**answers

545 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

**2**answers

424 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

**0**answers

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

**4**

votes

**1**answer

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

**3**answers

1k 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 ...

**2**

votes

**1**answer

277 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

**2**answers

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

**6**

votes

**0**answers

299 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

**3**answers

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

**6**

votes

**1**answer

589 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

**2**answers

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

**7**

votes

**3**answers

746 views

### Binomial coefficient in Andrews' partition book

First of all, i think MathOverflow is a very great community to discuss math, either basic or advanced, and i'm glad to participate here. It's my first post, so i'm sorry if i did anything wrong, and ...

**4**

votes

**1**answer

485 views

### What is the degree of a symmetric boolean function?

(previous title " Zero sum of binomials coefficients - a stronger version ")
This is a stronger version of another question.
Is there an $N\in \mathbb N$ and a sequence of non-constant functions $ ...

**8**

votes

**2**answers

531 views

### Zero sum of binomial coefficients

Is there a function $p:\mathbb N\to \{ 1,-1 \} $ and a fixed $N\in \mathbb N$ such that for every $n \geq N$ we get:
$\sum _{i=0} ^{n} p(i)\binom {n}{i}=0$
?
Obviously $p(i)=(-1)^i$ works for ...

**3**

votes

**1**answer

613 views

### Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums
$$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$
$$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$
...

**0**

votes

**2**answers

617 views

### Cosine of a Partial Sum

Does anyone know of a closed formula for $cos(\displaystyle\sum_{n=0}^m a_{n})$? I've seen formulas for $cos(\displaystyle\sum_{n=0}^\infty a_{n})$ and $tan(\displaystyle\sum_{n=0}^m a_{n})$, but the ...

**0**

votes

**1**answer

1k views

### The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that:
the product of non-adjacent vertices is constant.
the greatest common ...

**8**

votes

**7**answers

3k views

### Lower bound for sum of binomial coefficients?

Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case ...

**9**

votes

**3**answers

1k views

### Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence
$$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$
with initial condition $R_0^0 = 1$ and ...

**3**

votes

**2**answers

3k views

### Combinatorial proof of a recurrence for the Catalan numbers

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers:
$$
C_{n+1}=\frac{4n+2}{n+2} C_n.
$$
Thanks!~

**17**

votes

**3**answers

2k views

### Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello.
I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer ...

**31**

votes

**4**answers

2k views

### Integer-valued factorial ratios

This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
...

**9**

votes

**3**answers

2k views

### Showing a matrix is negative definite [formerly Showing a sum is always positive]

For each $d$, I have a matrix $M$ with values
$$
M_{ij} = \begin{cases}
\frac{4ij}{d} - \binom{2d}{d} & i \neq j & \\\\
\frac{4i^2}{d} - \binom{2d}{d} -
...

**11**

votes

**5**answers

837 views

### Asymptotics of a Bernoulli-number-like function

Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and
$$f(n,k) = ...

**2**

votes

**3**answers

500 views

### Variant of binomial coefficients

I've recently come across a variant of the binomial polynomials, and I'm curious if anyone has seen these before. If so, I'd love a reference, a name, etc.
First recall the following. If z is a ...