In the previous lesson, we used the cut-the-rope model to count positive integer solutions to the equation $x_1 + x_2 + \cdots + x_k = n$. We have also pointed out that this model cannot be used to count non-negative integer solutions. That said, the model can be modified a little bit to be fit for the case of non-negative solutions. Instead of making the cut, let's put a knife where it attempts to make the cut.

In this model, the numbers of balls separated by the knives represent the values of corresponding $x_i$s. Then the number of non-negative integer solutions to $x_1+x_2+\cdots + x_k =n$ is $$C_{n+k-1}^{k-1}$$

The solution can be expressed by this counting language: "arrange $n$ balls and $(k-1)$ knives in a row", or equivalently, "select $(k-1)$ places for the knives among $(n+k-1)$ choices".

It is important to emphasize that, when working on a problem,

• Do remember the model and use it
• Do not blindly apply the final formula

Competition math is never about merely remembering exotic formulas. Blindly applying formulas without fully analyzing and understanding a problem is a sure way to get tricked!