How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$?

Question

How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$ are there for each $S$?

$x_i$ and $S$ are non-negative integers.

My Computer Science prof also said that this can be solved with a recursive algorithm, how is this done?

Answer 1

To reformulate, you are asking for the number of partitions of $S$ with distinct parts. There is a generating series for this. Let $q(s)$ be the number you are counting, then $$Q(x)=\sum_nq(n)x^n=\prod_{i=1}^\infty(1+x^i)$$ For a fixed $S$, you can just compute the coefficient of $x^S$ in the product $$Q_S(x)=(1+x)(1+x^2)(1+x^3)\cdots(1+x^S).$$ For example, for $S=4$, the coefficient of $x^4$ in $$(1+x)(1+x^2)(1+x^3)(1+x^4)$$ is 2, so there are two such sums. For $S=5$, the coefficient of $x^5$ in $$(1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)$$ is 3.

These notes are useful.

Answer 2

If $Q(m,k)$ denotes the number of distinct $k$ partitions of $m$ and $P(m,k)$ denotes the number of $k$ partitions (not necessarily distinct) of $m$, then we have the recurrence relation \begin{align*} P(m,k) = P(m-1, k-1) + P(m-k, k) \end{align*} and \begin{align*} Q(m,k) = P\left(m - \frac{1}{2}k(k-1), k\right) \end{align*} What we need is $Q(S, n)$ and can be calculated recursively. For example, \begin{align*} Q(17,4) &= P(11,4) \\ &= P(10,3) + P(7,4) \\ &=P(9,2) + P(7,3) + P(6,3) + P(3,4) \\ &= 4 + P(6,2) + P(4,3) + P(5,2) + P(3,3) \\ &= 4 + 3 + 1 + 2 + 1 \\ &= 11 \end{align*}