### yspm's blog

By yspm, history, 19 months ago, happyguy656 just became a Grandmaster and he wants you to help him to prove the below equation:

$\sum_{i=1}^{n} i\binom {n-1}{n-i}\begin{Bmatrix} {n-i}\\{k-1}\end{Bmatrix}=\begin{Bmatrix}n \\ k\end{Bmatrix}+(n-1)\begin{Bmatrix}{n-1}\\ k\end{Bmatrix}$

Let $\binom nm$ be $0$ when $n<m$ and n,k are given integers Comments (15)
 » What do curly braces stand for here?
•  » » It means Stirling numbers of the second kind
•  » » Thank you for asking and it stands for the second kind Stirling number
 » I think it counts the number of ways to partition the set of $n$ elements into $k$ subsets and label an element from the subset that contains the first element. Firstly, the right-hand side. You can label $1$ in any partition of $n$ into $k$ subsets -- this corresponds to the first summand. When the subset with the first element contains other elements, you can count these cases as labeling one of $n-1$ elements first, partitioning the set of $n - 1$ elements into $k$ subsets, and inserting $1$ into a subset that contains the labeled element. As for the left-hand side. You set aside the first element, choose $i - 1$ element from the remaining $n - 1$ elements to be in the subset with the first element, label one of the $i$ elements, and then partition remaining $n - i$ elements into $k - 1$ subset.
•  » » Thank you for answering my question.Btw is there any direct ways with math derivation to prove it?