Questions tagged [binomial-coefficients]
For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.
427 questions
37
votes
3
answers
2k
views
How to prove the identity $L(2,(\frac{\cdot}3))=\frac2{15}\sum\limits_{k=1}^\infty\frac{48^k}{k(2k-1)\binom{4k}{2k}\binom{2k}k}$?
For the Dirichlet character $\chi(a)=(\frac a3)$ (which is the Legendre symbol), we have
$$L(2,\chi)=\sum_{n=1}^\infty\frac{(\frac n3)}{n^2}=0.781302412896486296867187429624\ldots.$$
Note that this ...
- 215
11
votes
3
answers
557
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 31
0
votes
1
answer
129
views
Closed form for $\sum\limits_{k=0}^{n} [\operatorname{wt}(k) = m]$ where $\operatorname{wt}(n)$ is the binary weight of $n$
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of $1$'s in binary expansion of $n$).
Let $a(n,m)$ be the family of integer sequences such that
$$
a(n,m) = \sum\limits_{k=0}^{n} [\operatorname{wt}(...
- 7,226
0
votes
0
answers
86
views
How to prove the following equation (involving multiple binomial coefficients sum)?
I encountered the equation below, encountered a problem that has been bothering me for a long time
Does anyone have an idea how to prove it? I would be extremely grateful to you if you come up with an ...
- 41
0
votes
1
answer
169
views
Partial sums of binomial coefficients and related family of polynomials
Let $a(n)$ be A302117. Here
$$
a(n) = 4(n-1)a(n-1) - \frac{1}{3}\prod\limits_{k=0}^{n-1}(2k-3), \\
a(0) = 0.
$$
Let
$$
T(n,k) = \sum\limits_{i=0}^{k} \binom{n}{i}.
$$
Let $P_n(z)$ be the family of ...
- 34.3k
4
votes
0
answers
168
views
How to prove the following equation (which involves binomials and determinant of 2×2 matrices)?
I have tried many ways to prove the following equation, such as the method of induction and expanding all the terms in the summation,but things got more complicated.I could not find an appropriate ...
- 188k
0
votes
2
answers
115
views
Upper bounds on quotients of binomial coefficients
Let $\gamma>1$ be a real number and let $n\in \mathbb{N}$.
Define $f\colon\mathbb{N}\to[0,1]$
$$
f(n_0) = \frac{\binom{n-n_0}{m}}{\binom{n}{m}},
$$
where
$$
m = \Big\lfloor{\frac{n}{\lceil\gamma ...
- 128k
0
votes
1
answer
98
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 13.2k
9
votes
1
answer
1k
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 ...
CommunityBot
- 1
8
votes
3
answers
642
views
Combinatorial identity with connection coefficients and falling factorial $\langle i x\rangle_n$
Let $j, k ,n$ be nonnegative integers such that $0 \leq j, k \leq n \leq k +j $. Pick integer $m$ such that $0 \leq m \leq k + j - n$.
Let $\langle x \rangle_m$ denote the falling factorial $x(x-1)\...
- 10.5k
16
votes
0
answers
309
views
Randomized Pascal's triangle: What is the average of all the numbers?
This question was posted on MSE. It received some interesting responses, but no definite answer.
Let's build a variation of Pascal's triangle. We write $1$'s going down the sides, as usual. Then for ...
- 3,527
3
votes
2
answers
403
views
Closed form for product of Stirling numbers of the second kind
What does the following expression evaluate to:
\begin{equation}
\sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix}
\end{...
- 18.4k
1
vote
0
answers
138
views
Eisenstein triples (and triangles with rational sides and a rational-degree angle) in Pascal's triangle
This question leads to a follow-up: are there any Eisenstein triples (satisfying $a^2\pm ab+b^2=c^2$) in one row of Pascal's triangle apart from the following:
$\binom{23}{8}^2+\binom{23}{8}\binom{23}{...
- 2,370
8
votes
2
answers
664
views
A coincidence concerning Fermat primes, binomial sums, and eta quotients?
Let $w_k$ be a primitive k th root of unity, where k is a power of 2. In response to a question, Robert Israel gave the solution,
$$\sum_{n=0}^\infty \frac{(-1)^n}{\binom{kn}{kn/2}} = \frac{2^k}{2^...
- 12.6k
5
votes
0
answers
183
views
On the polynomials $\sum_{k=0}^n\binom{n+k}k^m q^k$
A sequence of polynomials
$$P_0(q),\ P_1(q),\ P_2(q),\ \ldots$$
with real coefficients is called $q$-log-convex if for each $n=1,2,3,\ldots$ every coefficient of the polynomial $P_{n+1}(q)P_{n-1}(q)-...
- 15.6k
22
votes
1
answer
1k
views
We have $\binom{62}{26}^2+\binom{62}{27}^2=\binom{62}{28}^2$. How many other Pythagorean triples are contained in a single row of Pascal's triangle?
At MSE I asked, "Does any row of Pascal's triangle contain a Pythagorean triple?" The answer is yes; the example $\binom{62}{26}^2+\binom{62}{27}^2=\binom{62}{28}^2$ was given. In that ...
- 13.4k
24
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
...
- 14.6k
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 ...
CommunityBot
- 1
4
votes
1
answer
378
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 \...
- 34.3k
0
votes
0
answers
30
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,068
4
votes
2
answers
218
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)$ ...
- 34.3k
0
votes
1
answer
170
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 + ...
- 34.3k
6
votes
0
answers
214
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 ...
- 13.4k
6
votes
0
answers
752
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. ...
- 541
8
votes
5
answers
1k
views
Closed form for binomial coefficient sum
As part of a proof in finite group theory, I'm looking for a closed
form for the expression
$$\sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2}.$$
Any help — especially with reference or proof — would be
...
- 63.9k
10
votes
0
answers
598
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}$.
...
- 6,969
4
votes
4
answers
780
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 ...
- 128k
12
votes
1
answer
730
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 ...
CommunityBot
- 1
0
votes
0
answers
174
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 ...
- 175
1
vote
1
answer
142
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 ...
- 109k
4
votes
0
answers
207
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?
- 869
1
vote
0
answers
73
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,938
22
votes
8
answers
13k
views
Lower bound for sum of binomial coefficients?
Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
3
votes
1
answer
127
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.7k
0
votes
1
answer
403
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*}%...
- 1,091
0
votes
1
answer
158
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,\...
- 34.3k
0
votes
2
answers
309
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 ...
CommunityBot
- 1
7
votes
1
answer
527
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, ...
- 981
12
votes
5
answers
835
views
A divisibility of q-binomial coefficients combinatorially
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...
- 3,761
10
votes
4
answers
1k
views
Binomial coefficient in Andrews' partition book
First of all, I think MathOverflow is a very great community to discuss math, either basic or advanced, and I'm glad to participate here. It's my first post, so I'm sorry if i did anything wrong, and ...
- 4,713
5
votes
3
answers
325
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=...
- 43.2k
5
votes
3
answers
943
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(...
- 513
2
votes
1
answer
236
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 ...
- 5,624
4
votes
1
answer
252
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 ...
- 12.3k
0
votes
2
answers
140
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)...
- 128k
18
votes
2
answers
3k
views
Binomial supercongruences: is there any reason for them?
One of the recent questions, in fact
the answer
to it, reminded me about the binomial sequence
$$
a_n=\sum_{k=0}^n{\binom{n}{k}}^2{\binom{n+k}{k}}^2,
\qquad n=0,1,2,\dots,
$$
of the Apéry ...
- 1,446
2
votes
5
answers
949
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 ...
- 1,440
13
votes
1
answer
468
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,\...
- 188k
3
votes
1
answer
829
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 ...
- 105k
3
votes
1
answer
437
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}\...
- 2,821