Questions tagged [binomial-coefficients]
The binomial-coefficients tag has no usage guidance, but it has a tag wiki.
308
questions
3
votes
1answer
346 views
Conjecture on bernoulli numbers and binomial coefficients
Crossposted from
https://math.stackexchange.com/questions/4116414/conjecture-on-bernoulli-numbers-and-binomial-coefficients
In playing around with some formulas, I have come up with the following ...
0
votes
2answers
188 views
In search of a combinatorial proof for a multinomial sum
There is this sequence listed on OEIS - named Domb numbers. I'm curious about
QUESTION. Is there a direct combinatorial proof for the identity
$$\sum_{k=0}^n\binom{n}k^2\binom{2k}k\binom{2n-2k}{n-k}
=...
2
votes
1answer
169 views
Evaluations of three series involving binomial coefficients
Question. How to prove the following three identities?
\begin{align}\sum_{k=1}^\infty\frac1{k(-2)^k\binom{2k}k}\left(\frac1{k+1}+\ldots+\frac1{2k}\right)=\frac{\log^22}3-\frac{\pi^2}{36},\tag{1}
\end{...
6
votes
0answers
154 views
Looking for a combinatorial proof for an identity involving $q$-Catalan triangles
Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...
12
votes
5answers
2k views
Looking for a combinatorial proof for a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the familiar Catalan numbers.
QUESTION. Is there a combinatorial or conceptual justification for this identity?
$$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^...
0
votes
0answers
80 views
Sum of binomials with power coefficients
I have a sum of the form
$$f(n) = \sum_{i=0}^{ \lfloor \log_2 n \rfloor} \sum_{j=0}^{i} \binom{n}{2^j}.$$
Is there a closed formula or an approximation for this expression? What if $n = 2^m$ is a ...
0
votes
1answer
97 views
Maximum-average prefix of binomial coefficients
For $k\in\mathbb N$, let
$$
f(k)=\max_{j\in\{1,\dots,k\}}\left\{\frac{\sum_{i=0}^{j-1}\binom{k}{i}}{j} \right\}.
$$
Is there a way to express $f(k)$ explicitly?
If not, what is $\lim_{k\to\infty}f(k)$?...
0
votes
0answers
121 views
Binomial coefficient in a binomial coefficient
I am doing some research in combinatorics, and I found that I have to consider the following binomial coefficient :
$$ \binom{\binom{i}{j}}{k} $$
(In fact, I have to take the product for fixed $i,k$ ...
3
votes
2answers
226 views
Is there a combinatorial reason for variable-independence of this binomial-coefficient identity?
Consider the following identity
$$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$
It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ...
1
vote
1answer
112 views
An ambitiouser binomial coefficients sum
I asked how to calculate $$\sum_{i = 0}^b(-1)^i\binom{b}{i}\binom{a+b-i-1}{a-i}$$ and got amazing answers. A bit later, however, I figured I needed something rather more complicated: I need to find ...
-1
votes
3answers
190 views
Binomial Coefficients sum [closed]
Any idea on whether or not $$\sum_{i = 0}^b(-1)^i\binom{b}{i}\binom{a+b-i-1}{a-i}$$
has a closed formula on $a$ and $b$ (and on what it is, in case it does)?
It is supposed that $b \le a$.
6
votes
2answers
309 views
Closed form for $\sum_{j=0}^{\infty}{\alpha \choose j} {\beta \choose j}x^j$
As stated, I wonder if there is a closed form for the generating function $F_{\alpha,\beta}(x):=\sum_{j=0}^{\infty}{\alpha \choose j} {\beta \choose j}x^j$ where $\alpha,\beta \in\mathbb{N}$. Calling ...
6
votes
1answer
340 views
Numbers $k$ with $\{\binom nk:\ n\in\mathbb N\}$ dense in $\mathbb Z_p$ for any prime $p\le k$
Let $k$ be a positive integer and let $p$ be a prime. In my 2011 PAMS paper joint with my former student W. Zhang [Proc. Amer. Math. Soc. 139(2011), 1569-1577], we studied when $$S(k)=\left\{\binom nk:...
3
votes
1answer
226 views
Sum of product of binomial coefficients
I would like to compute the following sum:
$$
\sum_{k=0, \, k =odd}^{\min\{2n, m\}} {2n \choose 2n-k}{2m-2n \choose m-k}
$$
So far I can prove that
$$
\sum_{k=0, \, k =odd}^m {2n \choose 2n-k}{2m-2n \...
8
votes
1answer
403 views
What is known about sums of the form $\sum_{n=2}^{\infty}[\zeta(n)-1]^{p} $?
A fair bit is known about rational zeta series. This includes identities like $$ \sum_{n=2}^{\infty} [\zeta(n) -1] = 1 . $$
Many more identities can be found in articles by e.g. Borwein and Adamchik &...
5
votes
1answer
266 views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
7
votes
0answers
202 views
Estimating the alternating sum $\sum_{j \ge 1} (-1)^j e^{-j^2} j^k$
I have been trying to get a lower bound on the following alternating sum but without much success:
$$
\sum_{j=1}^T (-1)^j e^{-j^2} j^k .
$$
For small values of $k$, this is easy because the first term ...
7
votes
0answers
312 views
Do generalizations of the identity $\sum_{n=k+2}^{\infty} \binom{n-1}{k} (\zeta(n) -1) = 1 $ exist?
On p. 263 of Borwein's paper entitled “Computational Strategies for the Riemann zeta function”, the following identity is stated: $$\sum_{n=k+2}^{\infty} \binom{n-1}{k} (\zeta(n) -1) =1 . \qquad \...
2
votes
1answer
141 views
Do identities exist for the binomial series $\sum_{k=m+1}^{n+1} \binom{k}{m} \binom{n+1}{k-1} $?
While examining the product of two upper triangular matrices, I've found that the $(m,n)$'th entry of the resulting matrix amounts to: $$\sum_{k=m+1}^{n+1} \binom{k}{m} \binom{n+1}{k-1} $$ when $n \...
1
vote
1answer
147 views
Poisson-like random walk expressed as Bernoulli-like random walks (splitting scheme)
In our problem we have the transition density for $x,y\in \mathbb{Z}$ and $t\in \mathbb{N}$
$$R_{t}(x,y):=e^{-t}\frac{t^{x-y}}{(x-y)!}1_{x\geq y},$$
which is the Poisson distribution pdf. (This is ...
1
vote
1answer
134 views
Are there variations of Ramaswami's formula for the analytic continuation of the Riemann zeta function?
On p. 286 of Borwein's paper entitled "Computational Strategies for the Riemann zeta function", the author mentions a formula due to Ramaswami: $$(1-2^{1-s})\zeta(s) = \sum_{n=1}^{\infty} \...
3
votes
1answer
195 views
Combinatorial Summation $\frac{1}{n} \sum_{k=n+1}^{2n} (k-n)\binom{2n}{k}$ [closed]
For a particular problem, I reached until this point where eventually I have to prove this summation
$$
\frac{1}{n} \left ( \binom{2n}{n+1} + 2\binom{2n}{n+2} + 3\binom{2n}{n+3} + \dots + n\binom{2n}{...
1
vote
0answers
83 views
Upper bound $\sum_{i=1}^m \sum_{j=1}^n p_{i,j}(1-p_{i,j})$
Let
$$p_{i,j} = \frac{\sum_{l=i}^{i+j-1} {l-1 \choose i-1} {m+n-l \choose m-i}}{{m+n \choose n}}$$
I am interested in approximating/upper bounding the sum
$$ \sum_{i=1}^m \sum_{j=1}^n p_{i,j}(1-p_{i,j}...
10
votes
4answers
663 views
Are there any identities for alternating binomial sums of the form $\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} $?
In equations (20) - (25) of Mathworld's article on binomial sums, identities are given for sums of the form $$\sum_{k=0}^{n} k^{p}{n \choose k}, $$ with $p \in \mathbb{Z}_{\geq 0}$. I wonder whether ...
1
vote
0answers
129 views
An explicit solution to the congruence $x^2\equiv 14(\frac 3p)-(\frac p3)-12\pmod {p}$?
Let $p>3$ be a prime, and let $(\frac{\cdot}p)$ be the Legendre symbol. Then
$$14\left(\frac 3p\right)-\left(\frac p3\right)-12=\begin{cases}1&\text{if}\ p\equiv1\pmod{12},
\\-25&\text{if}\ ...
2
votes
3answers
397 views
Show that the ratio of limits converges to the nearest Riemann zeta zero except when the ratio is a singularity
Let $h(s,n)$ be:
$$h(s,n)=\lim_{c\to 1} \, \frac{(-1)^{n-2}}{(n-2)!}\zeta (c)^{n-2} \sum _{k=1}^{n-1} \frac{(-1)^{k-1} \binom{n-2}{k-1}}{\zeta ((c-1) (k-1)+s)}$$
and let $g(s,n)$ be:
$$g(s,n)=\lim_{c\...
6
votes
0answers
155 views
Some conjectural congruences involving Domb numbers
The Domb numbers are given by
$$D_n=\sum_{k=0}^n\binom{n}{k}^2\binom{2k}k\binom{2(n-k)}{n-k}\ \ \ (n=0,1,2,\ldots).$$
Such numbers have combinatorial interpretation, see, e.g., http://oeis.org/A002895....
0
votes
0answers
47 views
Interlaced binomial expansion
For $a_1,a_2,\ldots,a_n < 1$ let
$$f(a_1,a_2,\ldots,a_n) = \sum_{k_1,k_2,...,k_n = 1}^\infty \frac{(k_1 + k_2)!}{k_1! k_2!} \frac{(k_2 + k_3)!}{k_2! k_3!}\ldots \frac{(k_{n-1} + k_{n})!}{k_{n-1}! ...
5
votes
1answer
144 views
A $q$-analogue of a characterization of polynomials by binomial coefficients
Considering the binomial coefficient $\binom{x}{m}$ as a polynomial in $x$, the span of $\binom{x}{0}, \binom{x}{1}, \ldots, \binom{x}{d}$ is exactly the polynomials of degree $\le d$. A closely ...
3
votes
2answers
133 views
Partial sums of signed binomial coefficients
I don't know if this is true or not but I want this to be true and so far I don't have any counterexample.
Let $i$ be odd. Do there exist coefficients $a_k \in \{0,1\}$ such that
$$\sum_{k=1}^{i-1} (-...
2
votes
0answers
234 views
Bijective proof of a combinatorial identity: $\sum\limits_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m$
Identity
\begin{equation}
\sum_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m \tag{1}
\end{equation}
was used in an answer here. As shown in that answer, (1) easily reduces to
\begin{...
6
votes
0answers
135 views
An inequality related to the numbers of faces of polytopes with d+2 facets
I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
0
votes
1answer
88 views
Solve equation involving binomial coefficient
I have a problem that leads to the following equation:
$${x \choose k} = N$$
For some unknown $x$ and known constants $k$ and $N$. Here all numbers are natural numbers. I can solve this analytically ...
5
votes
1answer
273 views
Bounding the probability that two binomials are equal
Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.
Let $B_{n,p}$ denote the usual binomial random ...
2
votes
1answer
161 views
A good estimate for a binomial sum
Are there good estimate for the sums
$$1.\quad\quad\quad\quad\quad\sum_{i=1}^k\frac{\binom{2k}{i}}{i!}$$
$$2.\quad\quad\quad\quad\quad\sum_{i=1}^k\frac{\binom{2k}{i}\binom{2k}{2k-i}}{i!(2k-i)!}=\sum_{...
0
votes
2answers
194 views
Solving a recurrence relation involving binomial coefficients
This question originates from a graph neural network architecture (see 1) in which an edge-labelled graph $G=(V,E,\eta)$ of size $|V|=n$ with $\eta:E\to \mathbb{R}^{s_0}$ is represented as a "tensor''...
4
votes
1answer
87 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
129 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=...
3
votes
1answer
303 views
How to prove this combinatorial identity?
If $n \in \mathbb N \setminus \{0\}$ and $x,y,z \in \mathbb R$ such that $x+y+z=n-1$, show that
$$\dfrac{(-4)^n}{\binom{2x}{n}}\sum_{r+s=n,r,s\in Z}\dfrac{\binom{y}{r}\binom{y-a}{r}\binom{z}{s}\binom{...
1
vote
1answer
132 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\...
5
votes
1answer
115 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
99 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
115 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
90 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)),
$$
...
6
votes
2answers
431 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
106 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
394 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
118 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 \...
21
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
432 views
Find closed-form expression to $f(n)$
For all $n \in \mathbb{N}$, set
$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{otherwise}
\...
