Total number of solutions of an equation

Question

What is the total number of solutions of an equation of the form $x_1 + x_2 + \cdots + x_r = m$ such that $1 \le x_1 < x_2 < \cdots < x_r < N$ where $N$ is some natural number and $x_1, x_2, \cdots, x_r, m$ are integers?

Also, what would be the solution in the relaxed case where $x_1, x_2, x_3, \dots, x_r$ could be equal?

Answer 1

Presumably $m \ge 0$. Here are two ways of getting your answer.

1) If $F(N,m)$ is the number of such solutions, then by conditioning on the value of $x_r$ we have

$$F(N,m) = \sum_{x=1}^{\min(m,N-1)} F(x,m-x)\ \text{for}\ m \ge 1$$

with $F(N,0) = 1$, $F(1,m) = 0$ for $m \ge 1$.

2) $F(N,m)$ is the coefficient of $x^m$ in $\prod_{j=1}^{N-1} (1+x^j)$.

See also http://oeis.org/A053632.