# Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n > 0$ and $0 < 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?

-
The number of solutions is called the number of partitions of $n$ into $k$ parts. There is no known closed form. – André Nicolas Mar 20 '12 at 14:23

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<=m; ++i)
for (int j=i; j<=m; ++j)
c[j] += c[j-i];
int count = c[m];

-
What changes if $a_k \color{red}{<} a_{k+1}$? – draks ... Apr 7 '12 at 12:29
@draks: Then $a_i\geq i$ for all $i$, so one sets $a'_i=a_i-i$ instead, leading to the same reduced problem, but with $m=n-\binom{k+1}2$ instead of $m=n-k$ (assuming of course this number is non-negative, for otherwise there are no solutions). – Marc van Leeuwen Apr 8 '12 at 7:38

Let $b_1=a_1$, $b_2=a_2-a_1$, $b_3=a_3-a_2$, etc., $b_k=a_k-a_{k-1}$, $b_{k+1}=n-a_k$, reducing it to a problem you've already solved.

EDIT: It appears this is quite wrong. See comments and other solution. Sorry.

-
You also have to be a little careful about shifting from strict inequality to weak inequality. Up to probable calculation error on my part, the reduction should be $b_1 = a_1, b_2 = a_2 - a_1 + 1, b_3 = a_3 - a_2 + 1, \dots, b_k = a_k - a_{k-1} + 1, b_{k+1} = (n - k + 2) - a_k$, reducing to the equation $b_1 + \cdots b_{k+1} = n + 1$, with $b_i > 0$. – Michael Joyce Mar 20 '12 at 13:53
Both Gerry Myerson and Michael Joyce are mistaken. For Gerry the problem is (apart from the fact that it supposes $0\leq a_1$ rather than $0<a_1$, to lead to all $b_i\geq0$) that it does not represent the relation $a_1+\cdots+a_k=n$ at all; picking the $b_i\geq0$ adding to $n$ and putting $a_k=b_1+\cdots+b_k$ for $k\leq n$, $\sum_ia_i$ could be anything. For Michael it's similar: one does get $b_i>0$ but $a_k=b_1+\cdots+b_k-(k-1)$ for $k\leq n$ does not give $\sum_ia_i=n$ at all. André Nicholas' comment has it right. – Marc van Leeuwen Mar 20 '12 at 15:39