Existing summation approach for computation of combination?

34 Views Asked by At

Recently, I bumped into an interesting approach to alternately calculate the combinations. But I am not sure if there is such theory already existing for generic combinations with arbitrary factorials.

Say, now we are going to evaluate $\binom{N}{p}$ with $p=3$. Instead of factorials, the summation of products can be used. $$\binom{N}{3}=\frac{N!}{(N-3)!3!}=\sum_{i=1}^N(i-1)(N-i)$$ which can be readily proved as \begin{align} \sum_{i=1}^N(i-1)(N-i)&=-N^2+(N+1)\sum_{i=1}^Ni-\sum_{i=1}^Ni^2\\ &=-N^2+(N+1)\frac{N(N+1)}{2}-\frac{N(N+1)(2N+1)}{6}\\ &=N\frac{3(N+1)^2-6N-(N+1)(2N+1)}{6}\\ &=\frac{N(N-1)(N-2)}{6}. \end{align}

Otherwise, this can be thought in this way. We need to select three numbers from $1,2,\ldots,N$. So we just need to sum up all the cases from our choices. If we step from the first ($i=1$) to the last ($i=N$) and the other two are just the left and right, so the smaller numbers have $i-1$ possibilities, and the larger ones $N-i$ which then arrives $(i-1)(N-i)$ cases for each $i$. The sum of these steps are just exactly what we usually call $\binom{N}{3}$.