Questions tagged [binomial-coefficients]
The binomial-coefficients tag has no usage guidance, but it has a tag wiki.
272
questions
2
votes
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
5answers
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
1answer
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
2answers
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
2answers
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
0answers
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
3answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
2answers
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
1answer
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
1answer
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
0answers
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
3answers
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
3answers
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
3answers
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
3answers
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
1answer
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
0answers
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} ( \...
