The binomial-coefficients tag has no usage guidance, but it has a tag wiki.
10
votes
4answers
546 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
249 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
172 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
310 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
392 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
332 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
146 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-...
10
votes
0answers
237 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
99 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
139 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
124 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
140 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
169 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
635 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
191 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
340 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
200 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
114 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
71 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
389 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
268 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
41 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
151 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
170 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
406 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 ...
1
vote
0answers
135 views
Asymptotics for partial sum of product of binomial coefficients
Crossposted from https://math.stackexchange.com/questions/2605895/asymptotics-for-partial-sum-of-product-of-binomial-coefficients
For some fixed $0<p<1$, let $np\leq c<n$ and $2np\leq x< ...
3
votes
0answers
167 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
234 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
181 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
111 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
266 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
67 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
145 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
157 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
231 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
190 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
427 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
215 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
199 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
335 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 ...
