# Questions tagged [binomial-coefficients]

The binomial-coefficients tag has no usage guidance, but it has a tag wiki.

**1**

vote

**1**answer

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

**4**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**4**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**5**answers

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