5
$\begingroup$

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?

  • 3
    The number of solutions is called the number of partitions of $n$ into $k$ parts. There is no known closed form.2012-03-20
  • 0
    Related: http://math.stackexchange.com/questions/1867469/number-of-integer-triplets-a-b-c-such-that-abc-and-abc-n?noredirect=1&lq=1.2016-12-23

1 Answers 1