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}$$
...
- 2,743
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)$ ...
- 481
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 + ...
- 15
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. ...
- 539
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 ...
- 579
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 ...
- 541
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?
- 85
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,...
- 4,606
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$, $\...
- 19.6k
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,\...
- 5,261
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, ...
- 4,606
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=...
- 173
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(...
- 481
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 ...
- 125
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 ...
- 125
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 ...
- 628
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 ...
- 187
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}$.
...
- 2,997
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}\...
- 31
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 ...
- 393
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 ...
- 55.7k
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 (...
- 111
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,\...
- 15.1k
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,253
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 ...
- 21
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 ...
- 23.6k
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 $ ...
- 63
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+...
- 509
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 ...
- 131
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{\...
- 12.2k
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 ...
- 12.2k
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$.
- 13.8k
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}{...
- 1,800
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 ...
- 33.2k
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(\...
- 53
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 ...
- 53
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}...
- 109
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$.
...
- 26.3k
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(...
- 4,606
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 ...
- 1
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 ...
- 135
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\...
- 11
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 ...
- 33
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$...
- 17.7k
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)$...
- 906
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 ...
- 16.8k
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}^\...
- 15.1k
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 ...
- 847
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}^\...
- 15.1k