# 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_{\...
• 16.2k
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 ...
• 16.2k
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,545
Accepted

• 10k
Accepted

### A combinatorial identity

This is the answer to the first question, I wrote a long answer to Question 2 as a separate answer. Note that $A:=\sum_{k_i>0,k_1+\dots+k_n=K}\frac{K!}{n!k_1!\dots k_n!} \prod k_i^{k_i-1}$ is a ...
• 102k

• 5,282

### Are (55, 165, 495, 1485) and (286, 1716, 10296, 61776) the only geometric sequences of length 4 among non-trivial binomials?

(Partial results.) For the case of integer ratio, there are only two sequences of 4 binomials in geometric progression for which the largest is at most $10^{17}$. Namely, 55,165,495,1485 found by ...
• 37.2k
Accepted

### binomial coefficients are integers because numerator and denominator form pairs?

The kind of pairing sought does not always exist. Take, for example, $$\binom{8}{4}=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}.$$ The pair of $4$ must be $8$, the pair of $3$ must be $6$, and ...
• 96.9k
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 ...
Accepted

• 102k

### Analogue of Fermat's "little" theorem

Here's a straightforward proof, using generating functions, though it's not as elegant as Ofir's. We have $$\sum_{a=0}^\infty\binom{a}{j}x^a =\frac{x^j}{(1-x)^{j+1}}.$$ Setting $j=(p-1)k$ and ...
• 16.2k
Let's re-index the sum on the LHS of the problem (for the below convenience) so that $$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-k}(v-1)^k =\frac{v}s\sum_{k=0}^{s-1}\binom{2s}k(s-k)(v-1)^k.$$ Or, ...
A well-known upper bound, for $k\le N/2$, is $$\sum_{i=0}^k {N\choose i} \le 2^{N H(k/N)},$$ where $H$ is the binary entropy function $$H(x) = -x\log_2(x)-(1-x)\log_2(1-x).$$ This bound was ...