3
$\begingroup$

I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Here's a solution for given $n$.

# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
    for j in i, ..., n:
        ways[j] = ways[j] + ways[j-i]

print ways[n]

This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?

$\endgroup$
2
$\begingroup$

Let us denote the array ways after $t$ iterations of the outer loop by $w_t$. The recurrence implemented by the code is $$ w_0(n) = \begin{cases} 1 & \text{if } n = 0, \\ 0 & \text{if } n > 0. \end{cases} \\ w_t(n) = \begin{cases} w_{t-1}(n) & \text{if } n < t, \\ w_{t-1}(n) + w_t(n-t) & \text{if } n \geq t. \end{cases} $$ You can prove by induction that $w_t(n)$ is the number of representations of $n$ as a sum of natural numbers between $1$ and $t$ (without regard to order). (This is also the number of representations of $n$ as a sum of at most $t$ natural numbers.)

The code returns $w_{n-1}(n)$, which is the number of representations of $n$ as an arbitrary sum of natural numbers, other than the representation $n$.

As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $\tilde O(\sqrt{n})$, much faster than your $\Theta(n^2)$ algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "This is also the number of representations of $n$ as a sum of at most $t$ natural numbers" Is this intuitively equivalent to the number of partitions of $n$ to numbers at most $t$ (the statement to prove with induction)? I don't quite see the relation between both statements. $\endgroup$ – narek Bojikian Dec 26 '19 at 2:51
  • 1
    $\begingroup$ Conjugation moves you from one to the other. Look it up. $\endgroup$ – Yuval Filmus Dec 26 '19 at 7:44
  • $\begingroup$ I was able to prove the statement by proving that the number representations of $n$ as a sum of exactly $t$ numbers is equal to the number of representations of $n-t$ as a sum of at most $t$ numbers. $\endgroup$ – narek Bojikian Dec 26 '19 at 15:53
  • 1
    $\begingroup$ See here: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus Dec 26 '19 at 15:56
  • $\begingroup$ However, I couldn't find resources about the conjugation you mentioned above (there were many different "kinds" of conjugation in wikipedia and I didn't know which one did you mean) $\endgroup$ – narek Bojikian Dec 26 '19 at 15:56

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.