Questions tagged [binomial-coefficients]

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

Filter by
Sorted by
Tagged with
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} ( \...

1
2 3 4 5 6