# Questions tagged [binomial-coefficients]

The binomial-coefficients tag has no usage guidance, but it has a tag wiki.

272
questions

**2**

votes

**1**answer

70 views

### Combined identity perturbation

I found the interesting inequality when I study hypergraph 2-coloring
$$\sum_{i+j=k} \binom{r-1}{i}\binom{r-1}{j}(1-p)^i(1+p)^j \leq \binom{2r-2}{k}$$
$0\leq i, j < r$, $0\leq p \leq 1$. I want to ...

**4**

votes

**1**answer

117 views

### A binomial coefficient identity involving two parameters

In a recent calculation I obtain a result involving the following expression depending on two integers $n,m\geq 0$:
$$S(n,m):=\frac{(n+m+1)!}{n!m!}\sum_{l=0}^{n+m}\frac{1}{n+m-l+1}\sum_{\substack{j+k=...

**1**

vote

**0**answers

42 views

### How prove this combinatorial-identities

if $n\ge 1$ be postive integers,and $x,y,z$ be any real numbers,such $x+y+z=n-1$,for any real number $a$.show that
$$\dfrac{(-4)^n}{\binom{2x}{n}}\sum_{r+s=n,r,s\in Z}\dfrac{\binom{y}{r}\binom{y-a}{r}...

**1**

vote

**1**answer

109 views

### Does this series, related to the Hasse/Ser series for $\zeta(s)$, converge for all $s \in \mathbb{C}$?

I have asked this question at math stack exchange, however it did not get any traction. Still curious about the answer though.
Numerical evidence suggests that:
$$\lim_{N \to +\infty} \sum_{n=1}^N\...

**4**

votes

**1**answer

93 views

### Alternating binomial sum asymptotics

Let
$$
S_k=\sum_{j=0}^{\alpha k}(-1)^j\binom{k/2}{j}\binom{\alpha k^2-j k}{k}
$$
where $\alpha\in(0,1/2)$ is a constant.
I'm interested in understanding the asymptotic behaviour of $S_k$.
It would ...

**1**

vote

**0**answers

91 views

### Bell polynomial with variables 1 and 0

Let $B_{n,k}(x_1,\cdots,x_{n-k+1})$ be the Bell polynomial.
If $x_1=\cdots=x_{n-k+1}=1$, we know that $B_{n,k}(x_1,\cdots,x_{n-k+1})=S(n,k)$, where $S(n,k)$ is the Stirling number of second kind.
...

**0**

votes

**1**answer

107 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)^...

**1**

vote

**0**answers

77 views

### Divisibility properties of linear combinations of binomial coefficients [closed]

Let $p$ be a prime and $a_0,\ldots,a_n\geq 0$ be integers. Define
$$
S(a_0,\ldots,a_n)=\sum_{k=0}^n a_k\binom{n}{k}.
$$
I am trying to find out how much we know about
$$
v_p(S(a_0,\ldots,a_n)),
$$
...

**5**

votes

**2**answers

399 views

### An upper bound for the G.C.D. of $\binom{a}{3}$ and $\binom{b}{3}$

I can't seem to find anything in the literature on how to estimate the g.c.d. of $\binom{a}{k}$ and $\binom{b}{k}$. In particular, I would like to know why $\gcd(\binom{a}{3}, \binom{b}{3})\leq b \...

**2**

votes

**0**answers

102 views

### Analogues over finite fields of certain integers defined multiplicatively in $\mathbb Z$

For any irreducible polynomial $f$ of degree $d$ in finite field $\mathbb F$ we have that $$x^{|\mathbb F|^d}-x\equiv0\bmod f$$ and thus the polynomial $x^{|\mathbb F|^d}-x$ is the analog of factorial ...

**12**

votes

**1**answer

344 views

### Yet another real-rooted polynomial

In this entry I asked for the real-rootedness of a polynomial, and two very interesting answers were given: one using Malo's theorem and the other a clever rewriting of the expression using Jacobi ...

**-1**

votes

**1**answer

112 views

### Evaluation of $\int \prod_{j=1}^u \frac{x+j}{j-x}~dx$

Let $I_{n,k} = \frac{(n+k)!}{k!(k-1)!(n-k)!}$. This is a sort of generalization of the Apéry's numbers, with $I_{n,n} =$ the $n$-th Apéry number. I am studying integrals of the form:
$$f_u(x)=\int \...

**19**

votes

**2**answers

1k views

### Real rootedness of a polynomial

Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by:
$$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$
I've found with Sage that for every $...

**1**

vote

**1**answer

268 views

### Find closed-form expression to $f(n)$

Let
$ \forall n\in\mathbb N.\quad f(n)=
\begin{cases}
\min_{a\in\{\lceil n/2\rceil, \lceil n/2\rceil+1,\dots, n-1\}} \frac 1 4 \binom n a f(a) & \text{if $n\geq 4$}\\
1 & \text{else}
\end{...

**1**

vote

**2**answers

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

**2**

votes

**1**answer

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

**2**

votes

**0**answers

169 views

### For human proofs of two novel combinatorial identities

For $n=0,1,2,\ldots$, let us define the polynomial
$$S_n(x):=\sum_{k=0}^n\binom{x/2}k\binom{(x-1)/2}k\binom{-(x+1)/2}{n-k}\binom{-(x+2)/2}{n-k}.$$
Such polynomials occur in some series for $1/\pi$ ...

**2**

votes

**1**answer

118 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**

vote

**1**answer

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

**0**

votes

**1**answer

151 views

### A combinatorics question: $\lim\limits_{n \to \infty} \frac1{2^{2n}} \sum\limits_{k=1}^n \sum\limits_{i=0}^{k-1} \binom nk \binom ni = \frac12$ [closed]

Am trying to show that $\lim_{n \rightarrow \infty} \frac{1}{2^{2n}} \sum_{k=1}^n \sum_{i=0}^{k-1} \binom{n}{k} \binom{n}{i} =0.5.$
I think that the above result is true but am not sure how to prove ...

**2**

votes

**0**answers

53 views

### Counting binary vectors that satisfy given distance constraints

Let's start with a warm up problem.
Suppose I am given two binary vectors $x, y \in \{0, 1\}^n$ of length $n$ that differ in exactly $r$ places, i.e. $||x-y||_0=r$, i.e. their hamming distance is $r$...

**4**

votes

**1**answer

199 views

### On the sum $\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k}$

Let $n$ be a non-negative integer.
Does there always exist a polynomial $P_n(a,b)$ such that for all integers $a > b \geq n/2$ we have
$$
\sum_{k=b}^{a-1} \binom{2k+1+n}{2n+1}\binom{2a-1}{a+k} = \...

**1**

vote

**2**answers

281 views

### Closed form of $\prod_{i=0}^{N}\big(i!\big)^{{N}\choose{i}}$

I have made a question here about closed form of the following:
$$\prod_{k=0}^{N}\big(k!\big)^{{N}\choose{k}}$$
I know that there is a known closed form for,
$$\prod_{i=0}^{N}\big(i!\big)=G(N+2)$$
...

**6**

votes

**1**answer

334 views

### Two conjectural series for $\pi$ involving the central trinomial coefficients

For each $n=0,1,2,\ldots$, the central trinomial coefficient $T_n$ is defined as the coefficient of $x^n$ in the expansion of $(x^2+x+1)^n$. It is easy to see that $T_n=\sum_{k=0}^{\lfloor n/2\rfloor}\...

**3**

votes

**5**answers

333 views

### Non-trivial alternating sums of binomial coefficients

Consider a binary vector $a_0, a_1,\,\dots\,, a_n$ and an equation
$$\sum_{i=0}^n a_i \cdot (-1)^i {n \choose i} = 0.$$
You can satisfy this trivially when
1) all $a_i$ are 0, or
2) all $a_i$ are ...

**0**

votes

**1**answer

83 views

### Terminology and approximation to logarithm of a sum of products of binomial coefficients

Denote $$T(m)=\sum_{1\leq n_m\leq n_{m-1}\leq\dots\leq n_2\leq n_1\leq m}\prod_{i=1}^{m}\binom{n_i}{n_{i+1}}.$$
Is there a name for this kind of summation and is there a good estimate for $\ln T(m)$ ...

**0**

votes

**2**answers

189 views

### Interpolating asymptotic expression for logarithm of middle binomial sums

Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$.
We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(...

**4**

votes

**2**answers

397 views

### Showing this formula counts these things

I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being ...

**4**

votes

**0**answers

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

**7**

votes

**3**answers

364 views

### Asymptotics of multinomial coefficients

Binomial coefficients have a well known asymptotics (https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas) given by $$\binom nk\sim\binom{n}{\frac{n}{2}} e^{-d^2/(2n)} \...

**6**

votes

**0**answers

194 views

### Two conjectural congruences for Franel numbers

Recall that the Franel numbers are given by
$$f_n:=\sum_{k=0}^n \binom{n}{k}^3\ \ \ (n=0,1,\ldots).$$
Question. How to prove my following conjecture?
Conjecture. For each odd prime $p$, we have
$$\...

**2**

votes

**0**answers

72 views

### Closed form for unusual recurrence

We have for $k>0$, $n>0$, $m\geqslant0$
$$p_k(n,m)=k(n-1)!\sum\limits_{s=0}^{n-1}\frac{p_{k-1}(s+1,m+1)+p_{k-1}(m+1,s)}{s!}$$
also
$$p_0(n,m)=\begin{cases}
(n-1)!,&\text{$n>0, m=0$}\\
0,&...

**7**

votes

**0**answers

172 views

### Does Morley's congruence characterize primes greater than $3$?

In 1895 Morley showed that $$\binom{p-1}{(p-1)/2}\equiv(-1)^{\frac{p-1}2}4^{p-1}\pmod{p^3}$$
for any prime $p>3$.
In 2009, I formulated the following conjecture concerning the converse of Morley's ...

**4**

votes

**1**answer

176 views

### How far do I have to go for the tail of a binomial distribution with small $p$ to be $O(1/n)$?

Let $n$ be a large integer, $p$ be a small number (say, $p=C/n$ for some constant $C \ll n$), and consider the tail of the binomial distribution $B(n,p)$, after $T$:
$$
\delta = \sum_{s=T}^{n} p^s (1-...

**0**

votes

**1**answer

117 views

### Showing equality of Eberlein polynomials

I have thought about the following question a long time and still got no progress.
Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...

**0**

votes

**1**answer

93 views

### Any ideas for the following limit of partial sums of binomial coefficients?

Let $a$ be an odd integer $≥3$. It appears that: $$\lim_{n\rightarrow\infty}\frac{1}{2^{n}}\sum_{m=0}^{\left\lfloor n\frac{\ln2}{\ln a}\right\rfloor }\binom{n}{m}=\begin{cases}
1 & \textrm{if }a=3\...

**6**

votes

**1**answer

178 views

### What is the growth rate of the products of binomial coefficients?

Question 1: Are the following empirically observed relationships true
$$
{n \choose 1^a}{n \choose 2^a}{n \choose 3^a}\cdots {n \choose m^a}
\sim \exp\bigg(\frac{2n^{1 + \frac{1}{a}}}{a+3}\bigg)
$$
...

**1**

vote

**0**answers

41 views

### Mean value of a function with binomial coefficients as weights

Is the following true?
Let $a$ be a positive integer and let $t_n$ be a sequence of numbers. We define the binomial mean of $t_n$
$$
\beta_{t_n,a} = \frac{1}{2^n t_n}\sum_{r^a \le n} \binom{n}{r^a}...

**0**

votes

**0**answers

122 views

### Number of primes skipped by binomial coefficients?

Take $$B(l,n)=\binom{n+l}{n}$$ and $\mathcal P(t)=\{p\mbox{ prime}:p|t\}$.
What is the cardinality of $\mathcal P(B(l,n))$?
What is minimum cardinality of $L\subseteq\{1,\dots,n\}$ such that $$\...

**4**

votes

**3**answers

331 views

### Closed form $\int_{0}^{\frac{r}{2}} {\binom{n}{p} \binom{n-p}{r-2p} 2^{r-2p}}{\binom{2n}{r}^{-1}} \ \text{d}p$

Note: This is exact copy of my Math.SE question, which I am reposting here, as despite bounty it did not receive any answers.
Let there be $n$ pairs of shoes in a box.
The the probability that from ...

**1**

vote

**2**answers

122 views

### Monotonicity of $M$-sequence

Consider the following definition in the second page of this article:
For any two integers $k,n\ge 1$, there is a unique way of writing
$$n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\dots+\binom{a_i}{i}...

**7**

votes

**1**answer

269 views

### Voyage into the golden screen (sequence defined by recurrence relation)

We start from A004718 named "The Danish composer Per Nørgård's "infinity sequence", invented in an attempt to unify in a perfect way repetition and variation"
$$a(2n) = -a(n), \qquad a(2n+1) = a(n) + ...

**8**

votes

**1**answer

349 views

### Reciprocal sum of binomials and divisibility by $3$

We all know that $\sum_{k=0}^n\binom{n}k$ is not divisible by $3$.
QUESTION. Is it true that the numerator of $a_n$ (in reduced form) is never divisible by $3$?
$$a_n=\sum_{k=0}^n\frac1{\binom{n}...

**6**

votes

**0**answers

101 views

### Q-analogue of an inequality

Pick integers $b\geq a \geq 0$ and $k\geq j\geq 0$.
It is not super-difficult to prove the inequality
$$
\binom{kb}{ka}^j \geq \binom{jb}{ja}^k.
$$
This is actually quite a nice inequality that was ...

**0**

votes

**3**answers

205 views

### How to calculate$ \sum \limits_{k=0}^{m-n} {m-k-1 \choose n-1} {k+n \choose n}$?

How to calculate $$\sum\limits_{k=0}^{m-n} {m-k-1 \choose n-1} {k+n \choose n}.$$

**3**

votes

**3**answers

342 views

### How to calculate: $\sum\limits_{k=0}^{n-m} \frac{1}{n-k} {n-m \choose k}$

How to calculate:
$$\sum _{k=0}^{n-m} \frac{1}{n-k} {n-m \choose k}.$$

**4**

votes

**3**answers

155 views

### A clean upper bound for the expectation of a function of a binomial random variable

I wonder if there is a closed-form, or clean upper bound of this quantity: $\mathbb{E}[|X/n-p|]$, where $X\sim B(n,p)$.

**12**

votes

**3**answers

1k views

### Does the set $\{\binom x3+\binom y3+\binom z3:\ x,y,z\in\mathbb Z\}$ contain all integers?

The Gauss-Legendre theorem on sums of three squares states that
$$\{x^2+y^2+z^2:\ x,y,z\in\mathbb Z\}=\mathbb N\setminus\{4^k(8m+7):\ k,m\in\mathbb N\},$$ where $\mathbb N=\{0,1,2,\ldots\}$.
It is ...

**8**

votes

**1**answer

628 views

### A curious inequality concerning binomial coefficients

Has anyone seen an inequality of this form before? It seems to be true (based on extensive testing), but I am not able to prove it.
Let $a_1,a_2,\ldots,a_k$ be non-negative integers such that $\sum_i ...

**2**

votes

**0**answers

164 views

### A binomial coefficient identity

i'm unable to prove the following : $\forall n$ integer $\geq 3$,
$ \displaystyle \displaystyle \sum_{s=1}^n \sum_{j=n-s+1}^n \displaystyle \frac{ (\binom n j )^2 \binom {n+j} n }{s-n+j} ( \...