What's the underlying combinatoric idea behind $(k-1)!\binom{n}{k}=\sum_{i=1}^{n-k+1}\frac{\left(n-i\right)!}{(n-k+1-i)!}$?

Question

According to my CAS the following identity holds:

$$(k-1)!\binom{n}{k}=\sum_{i=1}^{n-k+1}\frac{\left(n-i\right)!}{(n-k+1-i)!}$$ Here we can set $$\left|\binom{\{1,..,n\}}{k}\right| = \binom{n}{k}$$ i.e. $\binom{\{1,..,n\}}{k}$ consists of all $k$-element subsets of $\{1,..,n\}$.

However, I'm struggling to find the underlying idea of how to express the sum as a disjunct union (or any other idea)

Answer 1

So, $\binom{n}{k}(k-1)!$ is equal to the number of $k$-cycles one can make using $n$ elements.

To see this, approach directly via multiplication principle, first by selecting which $k$ elements are used in the $k$-cycle, by finding which element is smallest in the cycle, then arranging the remaining elements after it.

---

To count this a different way, break into cases based on the value of the smallest element in the cycle.

Place that element and all smaller than it in the front of a permutation and permute the remaining $n-i$ elements and place these after.

Now... we only wanted a cycle of length $k$, so let us consider only the sequence starting from $i$ until $i+k-1$ and we will call this our $k$-cycle.

We will have overcounted the number of $k$-cycles like this however based on the number of arrangements of the trailing terms that aren't used in our $k$-cycle. So, dividing by that amount, $(n-i-(k-1))!$ corrects the count.

For example if $i=4$, $k=4$ and $n=10$, one of the available arrangements would be $$\color{grey}{1~2~3~}\underline{\color{blue}{4}~6~5~7}~\color{red}{8~10~9}$$ and our cycle is $(4~6~5~7)$. The grey numbers at the beginning are those numbers smaller than $i$ and must appear in increasing order. The blue number is our smallest element in the cycle and the designating point where the cycle begins. The numbers in red could be rearranged and still give rise to the same cycle in the end.

This gives us exactly $\dfrac{(n-i)!}{(n-i-(k-1))!}$ cycles of length $k$ whose smallest element in the cycle is $i$. Ranging over all possible values of $i$ gives the result.

Answer 2

The identity is equivalent to proving that $${n \choose k} = \sum \limits_{i=1}^{n-k+1} \frac{(n-i)!}{(n-i-(k-1))! (k-1)!}.$$ Note that the RHS is simply $$\sum \limits_{i=1}^{n-k+1} {{n-i} \choose {k-1}}.$$ This identity is known as the Hockey-stick theorem, and can be proven with induction as well as Pascal's identity, or in a variety of other methods. For more information, see here: https://en.wikipedia.org/wiki/Hockey-stick_identity