All Questions
Tagged with co.combinatorics binomial-coefficients
265 questions
0
votes
1
answer
127
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}(...
- 4,928
0
votes
0
answers
85
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
168
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 ...
- 4,928
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 ...
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 ...
- 15.8k
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
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 + ...
- 25
6
votes
0
answers
751
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
1
vote
1
answer
141
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
205
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
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,928
0
votes
1
answer
157
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,405
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, ...
- 4,928
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 ...
- 187
11
votes
1
answer
681
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 ...
- 56.9k
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,\...
- 15.6k
8
votes
1
answer
319
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,295
1
vote
1
answer
336
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
238
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 ...
- 24.2k
8
votes
3
answers
921
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
92
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 ...
- 203
0
votes
0
answers
244
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,810
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 ...
- 34.3k
3
votes
1
answer
392
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
302
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.5k
2
votes
0
answers
70
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,928
7
votes
1
answer
286
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
81
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
4
votes
2
answers
268
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.9k
1
vote
0
answers
78
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 ...
- 11
1
vote
1
answer
318
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 ...
- 57
4
votes
1
answer
505
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 {...
- 57
7
votes
1
answer
167
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,612
5
votes
3
answers
441
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+...
- 17.9k
0
votes
1
answer
150
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?
- 11
1
vote
1
answer
171
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 $...
- 1,295
0
votes
1
answer
199
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 ...
- 135
3
votes
0
answers
274
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,889
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
4
votes
1
answer
377
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 \...
- 1,889
2
votes
1
answer
383
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\...
- 155
5
votes
4
answers
917
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(...
- 155
0
votes
1
answer
167
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
1
vote
1
answer
332
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, ...
- 891
0
votes
1
answer
260
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?
- 573
3
votes
0
answers
144
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 ...
- 13.4k
1
vote
1
answer
211
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\...
2
votes
3
answers
742
views
Asking for a proof for a sum of products of binomials: an "interesting" identity?
The following identity must have received alternative proofs, including a combinatorial argument by David Callan as found at Bijections for the Identity $4^n = \sum_{k = 0}^n \binom{2k}k\binom{2(n - k)...
- 43.2k