# Calculate number of solutions for $\sum_{i=1}^k i\cdot x_i = n$ [duplicate]

Is there a general method to find the number of non-negative integral solutions for $$\sum_{i=1}^k i\cdot x_i = n$$

• I have no good answer, but it seems to me that you are opening the door to the theory of integer partitions. – Sangchul Lee Oct 7 '17 at 17:40
• – Sil Oct 7 '17 at 18:03

$$\sum_{i=1}^k i\cdot x_i = n$$ can be rewritten as $$1 \le y_1 \le y_2 \le \ldots \le y_m \le k,\,\, \sum_{j=1}^m y_j = n$$ where $m$ is not fixed. This is a restricted partition (specifically a partition of $n$ into parts not exceeding $k$), and the values you seek are tabulated in the Online Encyclopedia of Integer Sequences as A026820.
Note in particular that OEIS gives the formula $T(n,k) = T(n,k-1) + T(n-k,k)$ which has a simple combinatoric explanation: a solution to $$\sum_{i=1}^k i\cdot x_i = n$$ either has $x_k = 0$, in which case it's a solution to $$\sum_{i=1}^{k-1} i\cdot x_i = n$$ or it has $x_k > 0$, in which case it's a solution to $$\sum_{i=1}^k i\cdot (x_i - [i = k]) = n-k$$
For small $k$, closed forms have been enumerated by Doron Zeilberger, although he would prefer to credit his computer, Shalosh B. Ekhad. A brief explanation is given in a joint paper with Andrew Sills.