Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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

2 Answers 2

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];
share|improve this answer
    
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.

share|improve this answer
    
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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