### 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

• +47

 » 19 months ago, # |   +4 What do curly braces stand for here?
•  » » 19 months ago, # ^ |   +36 It means Stirling numbers of the second kind
•  » » 19 months ago, # ^ |   +19 Thank you for asking and it stands for the second kind Stirling number
 » 19 months ago, # |   +29 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.
•  » » 19 months ago, # ^ |   +9 Thank you for answering my question.Btw is there any direct ways with math derivation to prove it?
 » 19 months ago, # |   +64 Please send pic of this handsome guy, otherwise I will deny to answer your question.
 » 19 months ago, # |   +29 I think it's 961G and had already been discussed in the editorial.
•  » » 19 months ago, # ^ |   0 How Elegia's mind works!But can it be proved with Combinatorial equations……perhaps I can understand the edtorial's explanation.
•  » » » 19 months ago, # ^ |   +8 You should also check the comments below the editorial.
•  » » » » 19 months ago, # ^ |   -11 Err..my comment should be downvoted.Thank you!EI ls txdy!
•  » » » » » 19 months ago, # ^ |   +11 Comment downvoting — done
•  » » » » 19 months ago, # ^ |   0 Would you please explain the last step of the equivalent transformations?I understand the Combinatorial meaning of it but I failed to access wikipedia
 » 19 months ago, # |   0 emmm,Is happyguy656 your friend or your other account?
•  » » 19 months ago, # ^ |   0 uh....Please ignore my strange user name
•  » » » 19 months ago, # ^ |   0 His really id is happyguy666 but was occupied by others then he changed one