yspm's blog

By yspm, history, 3 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • +47
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What do curly braces stand for here?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    It means Stirling numbers of the second kind

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Thank you for asking and it stands for the second kind Stirling number

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Thank you for answering my question.

    Btw is there any direct ways with math derivation to prove it?

»
3 months ago, # |
  Vote: I like it +64 Vote: I do not like it

Please send pic of this handsome guy, otherwise I will deny to answer your question.

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I think it's 961G and had already been discussed in the editorial.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How Elegia's mind works!

    But can it be proved with Combinatorial equations……perhaps I can understand the edtorial's explanation.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You should also check the comments below the editorial.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Err..my comment should be downvoted.Thank you!

        EI ls txdy!

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Would you please explain the last step of the equivalent transformations?

        I understand the Combinatorial meaning of it but I failed to access wikipedia

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

emmm,Is happyguy656 your friend or your other account?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    uh....Please ignore my strange user name

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      His really id is happyguy666 but was occupied by others then he changed one