IntegerSolution Intermediate

Problem - 4768

Let $n \ge k$ are two positive integers. Given function $x_1+x_2+\cdots + x_k =n$,

  1. Find the number of positive integer solutions to this equation.
  2. Find the number of non-negative integer solutions to this equation.
  3. Explain the relation between these two cases. i.e. is it possible to derive (2) from (1), and vice versa?

(1) Using the cut-the-rope technique, we find the answer is $C_{n-1}^{k-1}$.

(2) Using the knives-and-balls technique, we find the anser is $C_{n+k-1}^{k-1}$.

These two basic technqiues are discussed in the book  Counting  and course 20 - Combinatorics (Counting). Indeed, these two results can be derived from each other.  To see these, let $y_i = x_i -1$ where $x_i$ is positive and $y_i$ is non-negative. Then, the equation $$x_1+x_2+\cdots x_k= n$$ is equivalent to the equation $$y_1 + y_2 + \cdots + y_k = n-k$$

Accordingly, the number of corresponding solutions must be the same. We already know the number of positive integer solutions to the first equation is $C_{n-1}^{k-1}$. Meanwhile, the number of non-negative integer solutions with $y_i$ is $C_{(n-k)+k-1}^{k-1}$. They are indeed the same.

report an error