# Questions tagged [binomial-coefficients]

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

417
questions

0
votes

0
answers

26
views

### Are there any numerically-plausible perfect binary code parameters besides (90,2)? [duplicate]

(Formerly on Math StackExchange here, without much progress.)
In order for a perfect binary code on $n$ symbols to correct $k$ errors, we need the sum
$${n\choose 0}+{n\choose 1}+\ldots+{n\choose k}$$
...

3
votes

2
answers

210
views

### how to prove identity for nth derivative of $(\text{arctanh}(x))^j$?

this question asked on MSE
I worked on integral problem and I got that
$$ \int_0^1 \frac{x^n}{\ln \left(\frac{1-x}{1+x} \right) } dx=-\frac{2}{(n+1)!}\sum_{j=1}^{n+1}F(n,j) \eta'(-j)$$
where $\eta(x)$ ...

0
votes

1
answer

163
views

### Summation of binomial coefficients with alternating signs

For a fixed $\alpha > 1$ and integer $n$, I want to provide some bounds or scaling results for the following summations
$$S_1(n,\alpha) = \sum_{k = 1}^{n} {n \choose k} (-1)^{k + 1} k / (\alpha k + ...

6
votes

0
answers

748
views

### For all $n\in \mathbb{N}$, How to find $\min\{ m+k\}$ such that $ \binom{m}{k}=n$?

I asked this question on MSE here.
Most numbers in pascal triangle appear only once (excluding the duplicates in the same row of the Pascal's triangle) but certain numbers appear multiple times. ...

4
votes

4
answers

595
views

### Bounding a binomial coefficient using the binary entropy function

I'm reading that recent paper on a new bound for diagonal Ramsey and am stuck at the attached "Fact 12.1", which is "standard".
Could anyone please point me to a source for this ...

1
vote

1
answer

129
views

### Asymptotics on sum of product of binomial coefficients

I'm interested in the behavior of the summation
$$S(a,b)=\sum_{k\ge 0}\binom{a-k}{k}\binom{b}{k}.$$
For a fixed $\delta>0$, I would like asymptotic bounds on $S(a,\delta a)$.
With $\delta=1$, this ...

4
votes

0
answers

187
views

### Who first considered "Pascal Triangle"? [closed]

Arnold was used saying in his talks,
"Pascal’s triangle, so called, because it was by Chinese discovered"!
How much is he right?

1
vote

0
answers

68
views

### Alternating sum of integer coefficients of the triangles related to Eulerian numbers and binomial transforms

Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$ or $k \leqslant 0$ such that
$$
W(n, k, m) = (k+m-1)W(n-1,...

3
votes

1
answer

121
views

### Bijective proof of deteminant formula for Hankel matrix of central binomial coefficients

Is there a nice bijective proof of the fact that the determinant of the $(n+1)$-by-$(n+1)$ Hankel matrix whose respective entries are the central binomial coefficients $0 \choose 0$, $2 \choose 1$, $\...

0
votes

1
answer

138
views

### Generalized Multinomial Formula

During a computation, the following came up, and I was wondering if there is a generalized multinomial formula which can handle expressions of the following form:
Let $n\in \mathbb{N}_+$ and $w_1,\...

7
votes

1
answer

517
views

### Suitable closed form for the A079501

Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).
The sequence begins with
$$
1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, ...

5
votes

3
answers

312
views

### A closed form (or tight upper bound) for $\sum_{j=0}^{2m} (-1)^j (m-j)^{2m+2k} \binom{2m}{j}$

I'm seeking a closed-form expression to the sum
$$ \sum_{j=0}^{2m} (-1)^j (m-j)^{2m+2k} \binom{2m}{j} $$
where for positive integers $m$ and $k$, we know $m \gg k$. Loosely, $k \sim \log(m)$.
When $k=...

5
votes

3
answers

919
views

### How to find the coefficient of $x^k$ in the expression $\prod_{p=1}^n (x^p+1)^p$?

I tried to find the indefinite integral
$$ f_n(x)=\int \prod_{k=1}^n \cos^k(kx) \, dx$$
by using Euler's formula and put $x=\frac{\ln y}{2i}$ I got
$$ f_n(x)=-i2^{-\frac{n(n+1)}{2}-1}\int y^{-\frac{n(...

2
votes

1
answer

233
views

### An integer sequence related to Pascal’s triangle

We need someone expert in binomial coefficients (subject 11B65) to recognize the integer sequence generated by an iterative formula we have encountered while working on a project about Pascal’s ...

4
votes

1
answer

238
views

### About the exact origin of a binomial congruence

Given a prime $p$ and an integer $0 \leq k \leq p-1$, a famous congruence on binomial coefficients states:
$$\binom{p-1}{k} \equiv (-1)^k \pmod{p}$$
It is generally taught as a consequence of Pascal’s ...

0
votes

2
answers

133
views

### Asymptotic bound of a simple alternating binomial sum

I'm a rather inexperienced researcher, I've been stuck on a question for a while. I would like to find the largest $N = f(n)$ that satisfies the following inequality:
$$\sum_{j = 0} ^ n p^{n - j} (-1)...

2
votes

5
answers

936
views

### Binomial series

I am interested in the limit $\frac{\sum_{k=0}^n \sqrt{k}\cdot\binom{n}{k}}{\sqrt{n}\cdot2^n}$ as $n$ goes to infinity. Any reference or argument?
In general what do we know about the asymptotic ...

3
votes

1
answer

760
views

### binomial coefficients are integers because numerator and denominator form pairs?

I've heard of a claim that when calculating the binomial formula with integer input:
$\mathrm{Bin}(n,k):=\prod^k_{i=1}\frac{n+1-i}{i}\in \mathbb{N}\ (\forall n,k\in\mathbb N)$
each denominator divides ...

10
votes

0
answers

565
views

### Does the interior of Pascal's triangle contain three consecutive integers?

This question defeated Math SE, so I am posting it here.
Consider the interior of Pascal's triangle: the triangle without numbers of the form $\binom{n}{0},\binom{n}{1},\binom{n}{n-1},\binom{n}{n}$.
...

3
votes

1
answer

429
views

### Identities for Bernoulli numbers

I arrived at this formula by inductive reasoning, but I don’t know how to prove it.
For any natural numbers $m$ and $k=0,1,2,\ldots, m-1$, $B_i$ - Bernoulli numbers we have:
$$\sum_{i=0}^k (-1)^{k-i}\...

24
votes

2
answers

2k
views

### Are (55, 165, 495, 1485) and (286, 1716, 10296, 61776) the only geometric sequences of length 4 among non-trivial binomials?

Let's define non-trivial binomial coefficients as values of $\binom{n}{k}$, where $n$ and $k$ are positive integers such that $2 \le k \le \frac{n}{2}$. (Therefore, $6$ is the smallest non-trivial ...

11
votes

1
answer

670
views

### Solve $\binom{n}{k}=m$ for $(n,k)$

For an integer $m>0$, put $X(m)=\{(n,k):4\leq 2k\leq n \text{ and } \binom{n}{k}=m\}$. Is there an efficient method to calculate $X(m)$? Is there a uniform upper bound for $|X(m)|$?
By ...

0
votes

1
answer

171
views

### Question in a paper by Erdős on divisibility properties of central binomial coefficient

In Erdős, Graham, Ruzsa, and Straus - On the prime factors of $\binom{2n}n$, at the beginning of the proof of theorem 1, they consider the case where $\log p$ and $\log q$ are commensurable numbers (...

13
votes

1
answer

450
views

### Four new series for $\pi$ and related identities involving harmonic numbers

Recently, I discovered the following four new (conjectural) series for $\pi$:
\begin{align}\sum_{k=1}^\infty\frac{(5k^2-4k+1)8^k\binom{3k}k}{k(3k-1)(3k-2)\binom{2k}k\binom{4k}{2k}}&=\frac{3\pi}2,\...

8
votes

1
answer

315
views

### Why does this combinatorial sum vanish?

We define the coefficients $c_{k,k-i}$ of ${n \choose k}$ by the following easy expansion:
\begin{align*}
& {n \choose k} = \frac{1}{k!} n(n-1) \dots (n-k+1) = \frac{1}{k!} \prod\limits_{t=...

1
vote

1
answer

324
views

### sum of binomial coefficient approximation by geometric series

I follow a subject almost like this link:
Sum of 'the first k' binomial coefficients for fixed $N$
$$
f(N,k) = \sum^{k}_{i=0} \binom{N}{i} .
$$
Michael Lugo suggest a way with geometric series ...

2
votes

2
answers

224
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

432
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

864
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

86
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 ...

1
vote

0
answers

91
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

110
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 ...

1
vote

2
answers

164
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

239
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}{...

0
votes

0
answers

169
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

386
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

282
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}...

4
votes

0
answers

134
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

69
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

291
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

281
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

79
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

126
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

577
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

111
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

254
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 ...

10
votes

1
answer

419
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

640
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

276
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}^\...