happyguy656 just became a Grandmaster and he wants you to help him to prove the below equation:

Let $$$\binom nm$$$ be $$$0$$$ when $$$n<m$$$ and n,k are given integers

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 184 |

2 | adamant | 177 |

3 | awoo | 176 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 163 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 148 |

happyguy656 just became a Grandmaster and he wants you to help him to prove the below equation:

Let $$$\binom nm$$$ be $$$0$$$ when $$$n<m$$$ and n,k are given integers

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/10/2023 00:49:08 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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?

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

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

How Elegia's mind works!

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

You should also check the comments below the editorial.

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

EI ls txdy!

Comment downvoting — done

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

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

emmm,Is happyguy656 your friend or your other account?

uh....Please ignore my strange user name

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