Questions tagged [binomial-coefficients]
The binomial-coefficients tag has no usage guidance, but it has a tag wiki.
1
vote
1answer
59 views
Asymptotic upper bound for partial binomial-like sum
I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic ...
10
votes
4answers
569 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 ...
5
votes
4answers
258 views
partial alternating sum involving binomial coefficients
I came across the following alternating sum
$$
\sum_{k=0}^n (-1)^k \binom{2n}{k} (n-k)^r,\quad 1\leq r < n.
$$
It seems that when $r$ is an even integer the sum is $0$ and when $r$ is an odd ...
3
votes
1answer
179 views
Reference request for some determinants of binomial coefficients
Let $C_{n}=\binom{2n}{n}\frac{1}{n+1}$ be a Catalan number. I am interested in books or papers where the following identities occur:
$$\det\left(\binom{i+j+1}{i-j+1}\right)_{0 \leq i,j\leq {n-1}}=C_{n}...
4
votes
1answer
316 views
Approximation a sum involving log and binomial coefficient
I am wondering about the asymptotic approximation of the following expression:
$$S=\sum^{N}_{i=0}\log\Bigg[\binom{\binom{N+1}{i}}{t_i}\Bigg]$$
where
$$t_i=\binom{N}{i}-\binom{N-k}{i-k}+\binom{N-k}{i-...
16
votes
2answers
404 views
Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$
Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, ...
12
votes
1answer
335 views
A matrix identity related to Catalan numbers
Let $$C_n=\frac{1}{2n+1}\binom{2n+1}{n}$$ be a Catalan number. It is well-known that $$(\sum_{n\ge{0}}C_n x^n)^k=\sum_{n\ge{0}}C(n,k)x^n$$ with $$C(n,k)=\frac{k}{2n+k}\binom{2n+k}{n}.$$
It is also ...
1
vote
3answers
147 views
Estimate for the binomial coefficients and bounds from below for the Beta function
Let $n\ge p\in \mathbb N$ and let $\binom{n}{p}$ be the binomial coefficient. I believe that
$$
\binom{n}{p}\le 2^n\sqrt\frac{2}{π n}.
$$
Question: is that true? Of course I would like it as a non-...
11
votes
0answers
272 views
Conjectural nonvanishing of some combinatorial sums (6j symbols)
From various considerations and with the help of J. Van der Jeugt, I was led to conjecture the following property of a class of Wigner 6j-symbols:
for any integers $k,m$ with $m\ge k\ge 2$,
$$
\left\{...
3
votes
0answers
108 views
Bounding a sum of products of binomial coefficients
I am trying to understand the following sums for $k\le n$ :
$$
\sum_{s=0}^{k} \begin{pmatrix} 2n-s/2\\ s\end{pmatrix}\begin{pmatrix} 2n-3s/2\\ k-s\end{pmatrix}
$$
$$
\sum_{s=0}^{k} \begin{pmatrix} ...
4
votes
0answers
146 views
For a combinatorial proof of a symmetric identity
In my paper Supercongruences involving dual sequences [Finite Fields Appl. 46(2017), 179-216], I gave a new symmetric identity which states that if $x+y=-1$ then
$$\sum_{k=0}^n(-1)^k\binom xk^2\binom{...
1
vote
1answer
125 views
$\lim_{k\to\infty}{n\choose k}2^{1-{k\choose2}}$, where $n=\max\{n\in\mathbb{N}:{n\choose k}2^{1-{k\choose2}}<1\}$
How do you prove $\lim_{k\to\infty,k\in\mathbb{N}}{n\choose k}2^{1-{k\choose2}}=1$, where $n=\max\{n\in\mathbb{N}:{n\choose k}2^{1-{k\choose2}}<1\}$? The expression ${n\choose k}2^{1-{k\choose2}}$ ...
8
votes
0answers
145 views
For $q$-analogues of a known curious identity
In 2002 I published the folllowing curious combinatorial identity:
$$(x+m+1)\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}i-\sum_{i=0}^m\binom{x+i}{m-i}(-4)^i=(x-m)\binom xm.$$
My original proof is ...
8
votes
0answers
174 views
Proof of Dixon's identity only using Chu-Vandermonde
For any integers $a,b,c\ge 0$,
one has the well known identity or "Dixon's Theorem":
$$
\sum_{k\in\mathbb{Z}} (-1)^k
\left(\begin{array}{c}a+b\\a+k\end{array}\right)
\left(\begin{array}{c}b+c\\b+k\end{...
25
votes
0answers
733 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 ...
5
votes
2answers
201 views
Asymptotic rate for $\sum\binom{n}k^{-1}$
This MO question prompted me to ask:
What is the second order asymptotic growth/decay rate for the sum
$$\sum_{k=0}^n\frac1{\binom{n}k}$$
as $n\rightarrow\infty$?
1
vote
1answer
345 views
References on Power Sums
Consider a recent arXiv preprint 1805.11445. The author of 1805.11445 has done an overview of classical problem of simplifying of power sum
$$\sum_{1\leq k\leq n}k^m, \ (n,m)\geq 0, \ m=\mathrm{const}...
7
votes
0answers
207 views
Is every integer $n>1$ the sum of two squares and two central binomial coefficients?
Those integers $\binom{2n}n\ (n=0,1,2,\ldots)$ are called central binomial coefficients. By Stirling's formula,
$$\binom{2n}n\sim \frac{4^n}{\sqrt{n\pi}}\ \ \ \ (n\to+\infty).$$
Of course, the ...
2
votes
0answers
115 views
Can this sum be majorized?
Suppose that, we have some real numbers $r_1,r_2,\dots,r_m \in [0,1]$; and we study a sum,
$$
S_1= \sum_{i=1}^m \binom{m}{i}(-1)^{i-1}f(r_i),
$$
for $f:[0,1]\to[0,1]$ a concave bijection. Now, take ...
1
vote
3answers
74 views
Weighted sum of binomials with $r$-th power of lower index
Given $r\in(0,1),$ what is the best upper (asymptotic) bound for the following expression
$$S(n,r):=\sum_{k=0}^n{n\choose k}k^r?$$
Holder's inequality gives $S(n,r)\le 2^n(\frac{n}{2})^r$ but I guess ...
1
vote
1answer
414 views
Coefficients in the sum $\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j=n^{2m+1}, \ m=1,2,…$
Consider a sum $$\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j$$
which returns an odd power $n^{2m+1}$ of $n$, for $\ m=0,1,2,...$ given fixed $A_{0,m}, \ A_{1,m}, \ ..., \ A_{m,m}$. The ...
12
votes
1answer
277 views
Some more binomial coefficient determinants
The setup is similar to this question, but generalizes the size of the Hankel matrix. We'll define
$$d(n,k,r):=\det\left(\binom{2i+2j+k+r}{i+j}\right)_{i,j=0}^{kn-1}.$$
Edit: Thanks to Johann ...
6
votes
3answers
1k views
Is there a generalization (surely there is) of this simple combinatorial identity?
I was just doing some algebra on a paper and obtained: $$\sum_{l=0}^{n-1} {{n+l} \choose l}={2n \choose {n+1}}$$
Are there some generalizations of this identity?
One possible generalization would be ...
26
votes
2answers
1k views
Some binomial coefficient determinants
It is well known that for $n>0$
$$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$
Computer experiments suggest that more generally
$$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...
0
votes
0answers
42 views
Minimum space needed to compute a binomial coefficient
What is the minimum space required by an algorithm that, given as input two integers $n \geq k \geq 0$, performing only integer operations of addition, subtraction, multiplication, and division, ...
-3
votes
1answer
163 views
How to prove the combinatorial equality? [closed]
Please, help me to understand following convolution (or give a reference):
$$
\sum_{R=0}^N \binom{R}{r} \binom{N-R}{n-r} = \binom{N+1}{n+1}
$$
Why is it true?
Thank you!
0
votes
0answers
71 views
Name of an equivalence identity on sums of weighted binomial coefficients
In my research, I have encountered the following equivalence identity:
For $a,b,n\in \mathbb{N}$, the equivalence
$$
\left({\sum_{0\leq w < b}n^w}\right)^a \substack{\equiv\\n^b} \sum_{0\leq w ...
0
votes
1answer
172 views
Could the sequence A287326 be generalized in order to receive expansion of natural power n>3? [closed]
The sequence https://oeis.org/A287326 - is Binomial distributed triangular array, that shows us necessary items to expand perfect cube $n^3$. Summation of $n$-th row of Triangle A287326 from $0$ to $n-...
2
votes
3answers
438 views
Sum of products of binomials
Sums of products of binomial coefficients often have simpler expression which do not involve any summation. Examples are the elementary $$\sum_{i=0}^k\binom{a}{i}\binom{b}{k-i}=\binom{a+b}{k}$$ or the ...
3
votes
0answers
171 views
Periodicity of $a_n={n \choose z}\ mod \ y$? [closed]
If I have a integer sequence defined as $a_n={n \choose z}\ mod \ y$ for $n,\ x, \ y \in \mathbb Z$, I have found that it is periodic with length: $y\prod_{k=1}^z gcd(e^{\Lambda(k)},y)$, where $\...
20
votes
2answers
2k views
New binomial coefficient identity?
Is the following identity known?
$$\sum\limits_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n+k}{n-k}\binom{2k}{k}=
\frac{1}{2n+1}$$
I have not found it in the following book:
Henry Wadsworth Gould, ...
2
votes
1answer
235 views
What is the expected number of missing random integers?
Consider $n$ numbers randomly generated by independent generators that can produce integers from $0$ to $n$. How many of these integers will be missing on average for large $n$? If $p_{k,n}$ is the ...
2
votes
1answer
185 views
A question about Pascal triangle
There is a number $n \in \mathbb{N}, \ n > 1, n < 2^k$. How to prove this statement:
$n$ is included into Pascal triangle not more than $2k -2$ times?
0
votes
1answer
112 views
Divisibility criterion of binomial coefficients
If $r\in\Bbb Z_{\geq0}$ and $m$ is odd then let $2^\ell\mid\binom{m}{2^r}$ and $2^{\ell+1}\nmid\binom{m}{2^r}$.
Is there a way to find if $\ell$ is even or odd without computing $\binom{m}{2^r}$ (...
-2
votes
2answers
268 views
Combinatorial proof of identity [closed]
The following admits of many (easy) proofs, but I am seeing no purely "bijective" argument:
$$
\sum_{j=n}^N \binom{j}{n} = \binom{N+1}{n+1}.
$$
Any ideas?
1
vote
2answers
68 views
“Super” multinomial coefficients
Define $\binom{a_1,...,a_n}{b_1,...,b_m}=\Pi_i(a_i!)/\Pi_j(b_j!)$. (WLOG null-pad to have $m=n$ and sort descendingly.) It's natural to ask when the value is an integer. Since I am working with "...
0
votes
0answers
86 views
Tartaglia distribution
I do not know if this question is elementary of advanced. Let me start by describing the two dimensional case in word.
Take the Tartaglia (or Pascal, or Bernoulli, or whatever name you want to give ...
2
votes
0answers
142 views
Reference request for a binomial identity
I stumbled upon the following (perhaps well-known) identity for a positive integer $k$:
$$\sum_{j=0}^n\frac{1}{(k-1)j+1}\binom{kj}{j}\binom{k(n-j)}{n-j}=\frac{1+kn}{1+(k-1)n}\binom{kn}{n}.$$
Could ...
9
votes
0answers
149 views
Some quotients of Hankel determinants
This question has been inspired by Hankel determinants of binomial coefficients.
For a sequence $\{h_{n}\}_{n=0}^{\infty}$ denote by $H_n$ the Hankel matrix
$$H_{n}:=\begin{pmatrix}
h_{0} & h_{...
2
votes
2answers
294 views
Estimation of a combinatorial sum when $n$ is large
Suppose $c,t$ are such that, $0< c< 1$ constant and $cn\leq t \leq n$.
I want to have an estimation of
$\sum _{i=0}^{cn} {cn\choose {i}}{(1-c)n \choose t-i} 2^{t-i}$
when n goes to infinity.
...
2
votes
0answers
161 views
Rank of Truncations of Block Binomial Coefficient Matrices
I am trying to compute the ranks of sub-matrices of matrices of a block Pascal type:
$$
M^{(n, m)} = \begin{bmatrix}
L_{n} & 0 & 0 & \ldots & 0 \\
ZL_{n-1} & L_{n-1} &...
6
votes
1answer
242 views
Prefix sums of Pascal triangle = powers of two
The circle division problem asks for the number of (bounded) regions obtained after choosing $n$ points in general position on a circle and then cutting along all segments connecting the points (cut ...
30
votes
3answers
1k views
Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$
In my research, I found this identity and as I experienced, it's surely right. But I can't give a proof for it.
Could someone help me?
This is the identity:
let $a$ and $b$ be two positive integers; ...
5
votes
0answers
200 views
Q-binomials at roots of unity
As the title says, given a general $q$-binomial $\binom{n}{k}_q$,
is there some general result regarding its value at a root of unity, $q = \exp(2\pi i r/N)$?
15
votes
4answers
2k views
A combinatorial identity
I hope this is a suitable MO question. In a research project, my collaborator and I came across some combinatorial expressions. I used my computer to test a few numbers and the pattern was suggesting ...
5
votes
2answers
434 views
Is there a simple proof of the following binomial Identity (part 2)?
This is a related question to the one I posted on MO earlier:
Is there a simple proof of the following Identity for $\sum_{k=m-1}^l(-1)^{k+m}\frac{k+2}{k+1}{\binom l k}\binom{k+1}m$?
It arose in the ...
9
votes
1answer
226 views
Inverse of a matrix with binomial entries
This is closely related to this question: Eigenvalues of a matrix with binomial entries.
We consider the matrix:
$$M_{ij} = 4^{-j}\binom{2j}{i}$$
where it is understood that the binomial ...
9
votes
1answer
202 views
Eigenvalues of a matrix with binomial entries
I am trying to determine the eigenvalues and eigenvectors of the following matrix:
$$M_{ij} = 4^{-j}\binom{2j}{i}$$
where it is understood that the binomial coefficient $\binom{m}{k}$ is zero if $k&...
4
votes
2answers
360 views
Sum of weighted binomial coefficients
Given positive integers $n$ and $k$, ($1\leqslant k\leqslant n-1$), and a real constant $s\in(0,1)$, I'm considering the following summation:
$$\sum_{i=0}^{n-k}(-1)^i\binom{n-k}{i}(k+i)^s$$
My goal is ...
20
votes
5answers
2k views
Bernoulli sum meets golden number
Let $B_n$ denote the Bernoulli numbers and let $\phi=\frac{1+\sqrt{5}}2$ be the golden ratio.
I encountered the following infinite sum and would like to ask:
Question. Is this true? If so, any ...
