1
$\begingroup$

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?

  • 0
    yes, r is fixed.2012-05-02

1 Answers 1

2

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.