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?

$\endgroup$
4
$\begingroup$

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];
$\endgroup$
  • $\begingroup$ What changes if $a_k \color{red}{<} a_{k+1}$? $\endgroup$ – draks ... Apr 7 '12 at 12:29
  • $\begingroup$ @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). $\endgroup$ – Marc van Leeuwen Apr 8 '12 at 7:38
  • $\begingroup$ @draks: For additional information on counting partitions with all distinct parts, see this previous Question and Answer. $\endgroup$ – hardmath May 31 '16 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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