Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The 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 ...