29*. a) How many different positive integer solutions does the equation

$$
x_{1}+x_{2}+x_{3}+\ldots+x_{m}=n
$$

have?

b) How many different non-negative integer solutions does the equation

$$
x_{1}+x_{2}+x_{3}+\ldots+x_{m}=n
$$

have?

Note. A particular case of problem 29a) (corresponding to $m=3$) is problem 25.

At the end of this series of problems, we will present several general theorems concerning the partition of numbers into summands. The first three of these theorems belong to the greatest mathematician of the 18th century, a member of the Russian Academy of Sciences, Leonhard Euler (1707-1783), who obtained many important results in various fields of mathematics. A series of similar theorems on the partition of numbers into summands (including the theorems that form the content of problems 30a), b) and 31a)) is contained in Chapter XVI of Euler's remarkable book "Introduction to the Analysis of the Infinitely Small," ONTI, M.-L., 1936. This book is quite challenging but does not require the reader to have preliminary knowledge beyond the high school curriculum, making it accessible to a sufficiently persistent high school student. Euler proves his theorems using a very interesting general method (the "method of generating functions"); these proofs differ from the more elementary proofs provided in this book as solutions to problems 30 and 31.

In problems 30 and 31, representations of a number as a sum of summands that differ only in order are considered the same.
29. The first solution to problems a) and b). First of all, note that the number of positive (respectively non-negative) integer solutions to the equation

$$
x_{1}+x_{2}+\ldots+x_{m}=n
$$

is equal to the difference between the number of positive (non-negative) integer solutions to the inequality

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n
$$

and the number of positive (non-negative) integer solutions to the inequality

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n-1
$$

Furthermore, it is obvious that if

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n
$$

then

$$
\left(x_{1}-1\right)+\left(x_{2}-1\right)+\ldots+\left(x_{m}-1\right) \leqslant n-m
$$

from which it follows that the number of positive integer solutions to the inequality

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n
$$

is equal to the number of non-negative integer solutions to the inequality

$$
y_{1}+y_{2}+\ldots+y_{m} \leqslant n-m
$$

(if \(x_{1}, x_{2}, \ldots, x_{m}\) are positive integers, then \(x_{1}-1, x_{2}-1, \ldots, x_{m}-1\) are non-negative integers \(^{1}\)). Thus, the solution to problems a) and b) reduces to finding the number of non-negative integer solutions to the inequality

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n
$$

Now, note that if

$$
x_{1}+x_{2}+\ldots+x_{m} \leqslant n
$$

where \(x_{1}, x_{2}, \ldots, x_{m}\) are non-negative integers, then the largest number \(t_{m}\) in the following sequence of increasing numbers

$$
\begin{gathered}
t_{1}=x_{1}+1, t_{2}=x_{1}+x_{2}+2 \\
t_{3}=x_{1}+x_{2}+x_{3}+3, \ldots, t_{m}=x_{1}+x_{2}+x_{3}+\ldots+x_{m}+m
\end{gathered}
$$

does not exceed \(n+m\). On the other hand, if we have \(m\) distinct positive integers \(t_{1}, t_{2}, \ldots, t_{m}\) not exceeding \(n+m\), then we can construct a solution \(x_{1}, x_{2}, \ldots, x_{m}\) to the inequality \((***)\) in non-negative integers: for this, it is sufficient to assume that the numbers \(t_{1}, t_{2}, \ldots, t_{m}\) are arranged in increasing order \(^{2}\) and set

$$
\begin{gathered}
x_{1}=t_{1}-1, x_{2}=t_{2}-t_{1}-1 \\
x_{3}=t_{3}-t_{2}-1, \ldots, x_{m}=t_{m}-t_{m-1}-1
\end{gathered}
$$

These arguments show that the number \(N(n, m)\) of ways to choose \(m\) numbers from the \(n+m\) numbers \(1,2,3, \ldots, n+m\) is equal to \(C_{n+m}^{m}\).

1) Note that in the problem of finding the number of positive integer solutions to the equation \((**)\), it is reasonable to assume \(n > m\).

Now it is easy to write down the answers to problems a) and b). Specifically, according to the above:

a) The number of positive integer solutions to the equation

$$
x_{1}+x_{2}+\ldots+x_{m}=n
$$

is

$$
N(n-m, m)-N(n-1-m, m)=C_{n}^{m}-C_{n-1}^{m}=C_{n-1}^{m-1}
$$

(because by a known property of combinations \(C_{n-1}^{m-1}+C_{n-1}^{m}=C_{n}^{m}\)).

b) The number of non-negative integer solutions to this equation is

$$
N(n, m)-N(n-1, m)=C_{n+m}^{m}-C_{n+m-1}^{m}=C_{n+m-1}^{m-1}
$$

(because \(C_{n+m-1}^{m-1}+C_{n+m-1}^{m}=C_{n+m}^{m}\)).

The second solution to problems a) and b). Consider the segment \(MN\) of length \(n\). Each solution to the equation

$$
x_{1}+x_{2}+\ldots+x_{m}=n
$$

in positive (respectively non-negative) integers corresponds to a partition of this segment into \(m\) smaller segments, the lengths of which are expressed in positive (non-negative) integers. This allows us to provide a new solution to our problems.

a) The number of solutions to our equation in positive integers is equal to the number of ways to partition the segment \(MN\) into \(m\) smaller segments. If \(M_{1}, M_{2}, \ldots, M_{n-1}\) are points on our segment such that \(MM_{1}=\cdots M_{1}M_{2}=\ldots=M_{n-1}N=1\) (Fig. 37), then the number of ways to partition the segment \(MN\) into \(m\) segments is, obviously, the number of ways to choose \(m-1\) points of division from the \(n-1\) points \(M_{1}, M_{2}, \ldots, M_{n-1}\), i.e., it is equal to the number \(C_{n-1}^{m-1}\) of combinations of \(n-1\) elements taken \(m-1\) at a time.

b) Similarly, the number of solutions to our equation in non-negative integers is equal to the number of ways to choose \(m-1\) points of division from the \(n+1\) points \(M, M_{1}, M_{2}, \ldots, M_{n-1}, N\), which is equal to the number \(C_{n+m-1}^{m-1}\) of combinations of \(n+1\) elements taken \(m-1\) at a time (see the solution using generating functions for this problem).

Note. Comparing the two solutions to the problem, we can note that the second solution to problem a) is significantly simpler, perhaps, than the first solution. As for problem b),