# Tag Info

Accepted

### Reason for breakdown of a nice binomial identity

$\def\des{\operatorname{des}}$Let $\des(\pi)$ be the number of descents of the permutation $\pi$. Then for any permutation $\pi$ in $S_k$, we have \begin{equation*}\binom{xy+k-\des(\pi)-1}{k} =\sum_{\...
• 14.4k
Accepted

### New binomial coefficient identity?

In terms of hypergeometric series, the sum is $_3F_2(-n, 1+n, 1/2;1,3/2;1)$ and the identity is a special case of Saalschütz's theorem (also called the Pfaff-Saalschütz theorem), one of the standard ...
• 14.4k
Accepted

### Prove that expression is integer

It equals $$\binom{2m}{m+k}\frac{3m-1-2k^2}{2m-1}=-(m-1)\binom{2m}{m+k}+4m\binom{2m-2}{m+k-1}.$$ I got it by expanding $3m-1-2k^2=2(m^2-k^2)-(2m^2-3m+1)=2(m-k)(m+k)-(2m-1)(m-1)$.
• 90.9k
Accepted

### Looking for a combinatorial proof for a Catalan identity

By the ballot theorem, $\frac{k}{n} \binom{2n}{n+k}$ is the number of Dyck paths, i.e. $(1,1), (1,-1)$-walks in the quadrant, from the origin to $(2n-1, 2k-1)$. You need to concatenate a pair of those ...
• 3,335
Accepted

• 8,981

• 4,710

### Sum of 'the first k' binomial coefficients for fixed $N$

Here's one from an old paper of mine. It has the property of being precise all the way from the middle to the end. Define $$Y(x) = e^{x^2/2}\int_x^\infty e^{-t^2/2}dt.$$ Define $x=(2k-n)/\sqrt{n}$. ...
• 34.8k
Accepted

### p-adic valuation for multinomial coefficients

Denote the sum of the digits of $n$ in base $b$ by $S(n)$. Then the number of carries when adding $k_1+k_2$ is $$\frac{1}{b-1}\big(S(k_1)+S(k_2)-S(k_1+k_2)\big).$$ This shows that the number of ...
• 82.6k
Accepted

### A combinatorial identity involving generalized harmonic numbers

The identity \begin{align} \sum_{s=1}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s }{s+1}H_{s}^{(2)}=\frac{2(-1)^m}{m+1}\sum_{s=1}^m H_{s}^{(2)}. \tag{1} \end{align} is equivalent to the following ...
• 4,710
Accepted

• 39.1k