Questions tagged [binomial-coefficients]

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

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

1
2 3 4 5
7