2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

$$\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$$

Closed forms are available by applying the work of Bruiner and Ono on weak Maass forms, but I suspect that that is currently not within your reach, and I know it's not within mine.

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.

$\endgroup$
  • $\begingroup$ The recurrence will be good enough for me. Thanks! $\endgroup$ – Sid Oct 8 '17 at 10:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.