# Questions tagged [binomial-coefficients]

For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.

390
questions

2
votes

2
answers

146
views

### Sign-reversing involution for $q$-binomial coefficient at $q=-1$

Consider the q-binomial coefficient $\binom{n}{k}_q$.
One combinatorial way to define it is as follows. Let $W_{n,k}$ be the set of binary words of length $n$ with $(n-k)$ 0's and $k$ 1's. An ...

6
votes

1
answer

308
views

### A summation involving fraction of binomial coefficients

I need to prove the following statement.
Let $ n, g, m, a ,t$ be integers. Prove that the following statement is true for all $ n \geq g(1+2m)+1 $, $ g\geq 2t $, $ m\geq t $, $ 0\leq a <t $, and $ ...

8
votes

3
answers

718
views

### Alternating Sum Involving Catalan Numbers

I was wondering if anyone knew how to obtain a simpler closed form of the following sum(or had any other insights regarding it):
$$\sum_{k=0}^n (-1)^k{n \choose k} C_{2n-2-k} $$
Here $C_n = \frac{1}{n+...

0
votes

0
answers

72
views

### Solving a Catalan-like recursion of polynomials, related to the KdV energies

I am working on a PDE problem. The goal is to connect the higher order energies of the Gross-Pitaevskii equation to those of the Korteweg-de-Vries equation. As these higher order energies are ...

0
votes

0
answers

76
views

### On level-$12$ of the McKay-Thompson series of the Monster and the Domb numbers

(This continues from level 10.) Given some moonshine functions $j_{N}$. There are nice descending and consistent relations for levels $6m$ with $m= 2,3,5,$
$$j_{12A} = \left(\sqrt{j_{12H}} + \frac{\...

1
vote

0
answers

86
views

### On level $6$ of the McKay–Thompson series of the Monster and Apéry numbers, et al

After the McKay–Thompson series of levels $1$, $2$, $3$, $4$ of the Monster were mentioned in this MO post, level $6$ has very interesting relations as well. (Level 10 is in this post.)
I. Level-6 ...

0
votes

2
answers

149
views

### How fast does this summation grow?

$n,i\in\mathbb N$.
The summation in question is
$$\sum_{k=1}^n\prod_{l=1}^k\binom{2^n}{2^l}^i.$$
How fast does this grow? I am specifically looking at $i=1,2$.

0
votes

0
answers

180
views

### Looking for a combinatorial proof of an identity

I've come up with an interesting combinatorial identity (thanks to P. Belmans who precomputed the numbers and pointed out to me that they correspond to OEIS A002697):
$$
\sum_{i=0}^{n-1}\binom{n+1-i}{...

1
vote

0
answers

123
views

### 3D generalization of Gaussian q-binomial coefficient

It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...

11
votes

1
answer

1k
views

### New method to compute square roots [closed]

In 2011 when I was in school I created a formula to calculate square roots... For $x\in\mathbb{R}$ with $x>0$ the following holds:
$$\sqrt{x} = \sum_{n=0}^{\infty}\frac{\left(\prod_{k=1}^{n}\left(\...

3
votes

1
answer

371
views

### A combinatorial identity involving binomial coefficients

When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement
the following identity
$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose ...

0
votes

0
answers

207
views

### An alternating sum involving a product of binomial coefficients

I encountered the sum below, where $c_{1}$, $c_{2}$, $c_{3}$, $c_{4}$ and $d$ are some given positive constants. Does anyone have an idea how to simplify it?
$$
\sum\limits_{k=1}^{d} \frac{(-1)^{k-1}k}...

3
votes

0
answers

123
views

### Irreducibility of polynomials associated to binomial coefficients

Let $n \geq 2$.
Let $M_n$ be the $(n+1) \times (n+1)$ matrix with entries $\binom{l}{k}$ for $0 \leq l,k \leq n$ and $U_n=M_n + M_n^T$ and let $f_n(x)$ denote the characteristic polynomial of $U_n$.
...

2
votes

0
answers

65
views

### Integer coefficients such that $T(n,k)=R(n,k)-R(n,k-1)$

Let $a(n)$ be A000085, i.e., the number of self-inverse permutations on $n$ letters, also known as involutions; number of standard Young tableaux with $n$ cells. Here
$$a(n) = a(n-1) + (n-1)a(n-2), a(...

0
votes

2
answers

152
views

### Integer solutions of system of inequalities

I am trying to solve a problem in combinatorics and I came up with the following system of inequalities:
$0\leq x<y<z\leq n$ and $x+y<n$ and I am trying to count the number of integer ...

7
votes

1
answer

233
views

### A reference for a sum found in Gould's Combinatorial Identities book

On p. 49 in Gould's book Combinatorial Identities, the author states that the sum $$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{2n}{2k}^{-1}$$ "... arises naturally in a statistical problem; it ...

1
vote

0
answers

75
views

### Maybe with the multinomial theorem

I'm looking for some idea to prove
\begin{equation*}
\sum_{\substack{ \left( s_{0},\ldots ,s_{r-1}\right) \in \left\{ \mathbb{N}%
\cup \left\{ 0\right\} \right\} ^{r}, \\ \sum_{a=0}^{r-1}\left( a+1\...

3
votes

1
answer

106
views

### Why is this alternating sum involving Catalan numbers $\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0$ for all $t$?

I need the result that for all $t$,
$$\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0,$$
where $C_{t-i-1}$ is the $(t-i-1)$-th Catalan number. I've checked for $t$ up to ...

13
votes

1
answer

540
views

### A congruence for a product of binomial coefficients?

For every prime $p\geq 5$ one seems to have the congruence
$$(-1)^{(p-1)/2}\prod_{k=0}^{p-1}{p-1\choose k}\equiv 1-p+\frac{3}{2}p^2-\frac{7}{6}p^3\pmod{p^4}\ .$$
(I have checked all primes up to $5000$...

4
votes

0
answers

91
views

### Greatest common divisors of some binomial coefficients

This is cross-posted from math.stackexchange.
While making some computation, I stumbled upon a curious relation among some binomial coefficients.
Consider the sequence of binomial coefficients $a(k,n)$...

4
votes

2
answers

195
views

### (Conceptual) proof and/or interpretation of a $q$-binomial identity

There is a $q$-binomial identity that I encountered in one paper I am reading (https://arxiv.org/abs/1910.06193) which probably admits a very simple proof that I do not see: for two nonnegative ...

9
votes

1
answer

312
views

### Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers

The classical rational Ramanujan-type series for $1/\pi$ have the following four forms:
\begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1}
\\\sum_{k=0}^\...

3
votes

2
answers

372
views

### Binomial coefficient congruence modulo $p^n$

I am interested in the following congruence
$$\binom{ap^n}{bp^n}\equiv \binom{a}{b}\pmod{p^n}$$
I am aware that by some reference in a book the above it should actually hold modulo $p^{3n}$; the ...

4
votes

0
answers

267
views

### What is the exact value of the series $\sum_{k=0}^\infty \binom{2k}k^4/256^k$?

By Stirling's formula $n!\sim\sqrt{2\pi n}(n/e)^n$, we have
$$\binom{2k}k\sim\frac{4^k}{\sqrt{k\pi}}$$
and hence
$$\frac{\binom{2k}k^4}{256^k}\sim\frac1{k^2\pi^2}.\tag{1}$$
So the series
$$\sum_{k=0}^\...

1
vote

0
answers

66
views

### Closed-form expression for combinatorial summation with a quadratic exponent?

In a current project, I have encountered sums of the form $$A_N(\theta_1,\theta_2) = \sum_{x=0}^{N}{N \choose x} \theta_1^x \theta_2^{x^2}$$ for $\theta_1$ and $\theta_2$ positive reals. My current ...

1
vote

1
answer

306
views

### How to calculate this limit (if exist)?

I have just asked the calculation of the following summation see here $$S(a,b,m,n_1,n_2)=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k}, $$
which is motivated by the calculation of the ...

4
votes

1
answer

373
views

### How to calculate this summation $\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $?

Question: How to calculate this summation $S=\sum_{k=0}^m a^k b^{m-k} {n_1\choose k} {n_2\choose m-k} $? Where $m<n_1,m<n_2$
Remark1: When $a=b$, I know the above summation $S=a^m\sum_{k=0}^m {...

1
vote

0
answers

86
views

### polynomial approximation of hypergeometric function 2F1

I have the following function $T(k_1,k_2)$ resulting from multiphoton transition matrix elements calculations:
$T(k_1,k_2)=\gamma^{-k_2}\sum_{j=0}^{k_1}(j+2)_{l+1}\binom{k_1}{j}(k_1+1)_3(\gamma-1)^{j}{...

7
votes

1
answer

158
views

### A formula for the generating function of Hoggatt binomials or of some Young tableaux

Let ${\left\langle\matrix {n \cr k}\right\rangle}_r$ denote the $r-$Hoggatt binomials defined by
$${{\left\langle\matrix {n \cr k}\right\rangle}_r=\frac{\langle n \rangle_r!}{\langle k \rangle_r! \...

5
votes

3
answers

362
views

### How to calculate the sum of general type $\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k- n + a \choose r }$?

QUESTION. How to calculate the sum of such general type?
$$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose r }. $$
Some particular examples
$$\sum_{k=0}^n {n\choose k} {n\choose k+a} = ...

29
votes

1
answer

2k
views

### Reason for breakdown of a nice binomial identity

One has the nice identities
$${xy\choose 1}={x\choose 1}{y\choose 1},$$
$${xy+1\choose 2}={x+1\choose 2}{y+1\choose 2}+{x\choose 2}{y\choose 2}$$
and
$${xy+2\choose 3}={x+2\choose 3}{y+2\choose 3}+4{x+...

0
votes

1
answer

111
views

### Number of ways to write a finite set of cardinality n as the union of r distinct binary subsets [closed]

I want to know the number of ways to write a finite set of cardinality $n$ as the union of $r$ distinct two-element subsets. Is there a nice formula in binomial coefficients?

2
votes

1
answer

144
views

### Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

For $b,w \geq 0$ let $K_{b+1,w+1}$ be the complete bipartite graph with vertices $a_1,...,a_{b+1}$ on the left hand side and $c_1,...,c_{w+1}$ on the right hand side. For given $1 \leq d \leq w$ and $...

2
votes

0
answers

195
views

### Question on globally convergent formulas for the Riemann zeta function $\zeta(s)$

Consider the following two formulas for $\zeta(s)$
$$\zeta(s)=\underset{K\to\infty}{\text{lim}}\left(\frac{1}{1-2^{1-s}}\sum\limits_{n=0}^K \frac{1}{2^{n+1}}\sum\limits_{k=0}^n \binom{n}{k} \frac{(-1)^...

20
votes

3
answers

3k
views

### Analogue of Fermat's "little" theorem

Let $p$ be a prime, and consider $$S_p(a)=\sum_{\substack{1\le j\le a-1\\(p-1)\mid j}}\binom{a}{j}\;.$$
I have a rather complicated (15 lines) proof that $S_p(a)\equiv0\pmod{p}$. This must be
...

0
votes

1
answer

148
views

### upper bound on sum of product of binomial coefficients

For positive integers $\ell < m < n$, consider a partition of $[2n]$ into two $n$-element sets $(X,Y)$. How many ways are there to choose an $m$-subset $A \subset [2n]$ such that the size of the ...

3
votes

0
answers

259
views

### Inequalities for Motzkin polynomials

Let us denote by $M_{n}(t)$ the $n$-th Motzkin polynomial. It is defined by $M_1(t) = M_2(t) = 1$ and
$$ M_{n}(t) = \sum_{i=0}^{\lfloor n/2\rfloor } \frac{1}{n-1-i} \binom{n-1-i}{i} \binom{n-1}{i+1} t^...

-1
votes

1
answer

321
views

### Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?

In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by
\begin{equation*}%...

2
votes

0
answers

177
views

### Counting permutations with a fixed number of descents and an extra condition

I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...

2
votes

0
answers

105
views

### Divisibility based on central binomial coefficients

For some prime $p$, it is a standard approach based on Kummer's criterion to bound the number of positive integers $n<X$ for some parameter $X$, such that $p\nmid \binom{2n}{n}$. However, if we ...

1
vote

1
answer

338
views

### Lower bound and limit of a sum with binomial coefficients

Let
$$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$
$$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$
$$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...

5
votes

4
answers

772
views

### Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$
$$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$
$$C_k = \frac{\sum_{i=1}^k(...

0
votes

1
answer

151
views

### Restrictions on exponents in multinomial formula

From the multinomial formula we have
$$(x_1 + x_2 + \dotsb + x_m)^n
= \sum_{k_1+k_2+\dotsb+k_m=n, \ k_1, k_2, \dotsc, k_m \geq 0} {n \choose k_1, k_2, \dotsc, k_m}
\prod_{t=1}^m x_t^{k_t}\,.$$
I ...

1
vote

1
answer

227
views

### Inequalities between sums of products of certain binomial coefficients

I am a PhD student. During my researches, I often have to deal with inequalities involving sums of binomial coefficients, where the sums are indexed by some set of integer compositions. For example, ...

3
votes

2
answers

227
views

### An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$:
$$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq
\frac{1}{3}.$$
I have been struggling with ...

0
votes

1
answer

185
views

### Proof for alternating binomial sum over even powers

I have numerical evidence that
$$ \sum_{k=1}^n (-1)^k\frac{k^{p}}{n+k}\binom{2n-1}{n-k}=0 $$
For $p=2,4,6...2n-2$.
How could this be proved?

5
votes

2
answers

290
views

### Extended binomial coefficients and the gamma function

For which $(a,b,n) \in \mathbb{Z}^3$ satisfying $a+b=n$ does $\frac{\Gamma(z+1)}{\Gamma(x+1)\Gamma(y+1)}$ approach a limit as $(x,y,z) \rightarrow (a,b,n)$ in $\mathbb{C}^3$, and what is that limit? (...

3
votes

0
answers

137
views

### Flat polynomials with factors of big height

Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...

0
votes

1
answer

184
views

### A binomial product sum that turns out to be 1

The binomial product sum
\begin{align*}
\sum\limits_{\substack{i_1> i_2> \cdots > i_k\\i_1, i_2, \cdots, i_k \in \{1, 2, \cdots, n-1\}}}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots\...

0
votes

1
answer

246
views

### Sum of the first m terms of the expansion $(x+y)^n$

Let $S(x, y, m, n) = \sum\limits_{i=0}^m \binom{n}{i}x^i y^{n-i}$, where $0 < m < n$. I want to derive the relation between $S(x, y, m, n)$ and $S(x, y, m, n-1)$.
Is there any formulas I can use?...