Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n \gt 0$ and $0 \lt a_1 \leq a_2 \leq \dots \leq a_k$ are integers. I know how to find the number of solutions to the equation:
$$a_1 + a_2 + \dots + a_k = n$$
where $n$ is a given positive integer and $a_1$, $a_2$, $\dots$, $a_n$ are positive integers. The number of solutions to this equation is:
$$\binom{n - 1}{k - 1}$$
This can be imagined as $n$ balls arranged on a straight line and selecting $k - 1$ gaps from a total of $n - 1$ gaps between them as partition boundaries. The $k - 1$ partition boundaries divide the $n$ balls into $k$ partitions. The number of balls in the $i$th partition is $a_i$.
Now, I don't know how to find the number of solutions to the same equation when we have an additional constraint: $$0 < a_1 \leq a_2 \leq \dots \leq a_k.$$ Could you please help me?
 A: While there is no closed form for the number of partitions of $n$ into $k$ parts, these numbers are not hard to compute. First let's get rid of the awkward initial strict inequality: by setting $a'_i=a_i-1$ we get $0\leq a'_1\leq\cdots\leq a'_k$ and $a'_1+\cdots+a'_k=n-k$. This means we want to count weak partitions of $m=n-k$ into $k$ parts, where weak means the parts can be $0$. Now forming a Young diagram by putting $a'_i$ squares in row $k+1-i$, we are counting Young diagrams with $m$ squares that fit in the first $k$ rows. This is the same as counting Young diagrams with $m$ squares and columns of length at most $k$, or counting partitions of $m$  into parts (arbitrarily many) of size at most $k$.
Now such partition problems have easy generating series. In this case the number we want is the coefficient of $X^m$ in the product of formal power series:
$$
  \frac1{(1-X)(1-X^2)\cdots(1-X^k)} = \prod_{i=1}^k\frac1{1-X^i}.
$$
Multiplying a power series by $\frac1{1-X^i}$ is obtained by adding, in an increasing order, to each coefficient of $X^j$ with $j\geq i$, the coefficient of $X^{j-i}$ (the latter is in general already modified during this run). Thus the following little program (in C++) computes you number in the final entry of the array $c$:
int m = n-k;
vector<int> c(m+1,0); c[0] = 1; // series with m+1 coefs, set to unity
for (int i=1; i<=k; ++i)
  for (int j=i; j<=m; ++j)
    c[j] += c[j-i];
int count = c[m];

A: Number of solutions is $S(n, k)$.
If $a_1=1$, we need the number of solutions of: $a_2+⋯+a_k=n-1$, which $S(n-1, k-1)$
If $a_1>1$, minus all $k$ numbers by 1: 
$$(a_1-1)+(a_2-1)⋯+(a_k-1)=n-k$$
The number of solutions of this is $S(n-k, k)$.
So $S(n, k)=S(n-1, k-1)+S(n-k, k)$
