Number of partitions of n into at least two distinct parts

Revision en4, by SPyofgame, 2020-08-30 16:48:18

The problem is to calculate the number of such subsequence ${a_1, a_2, \dots a_n}$ that ($a_1 + a_2 + \dots + a_k = n$) where ($k \geq 2$) and ($a_i \in {1, 2, \dots, n}$)

It is the sequence OEIS A111133

### My approach for small n

Lets $magic(left, last)$ is the number of valid subsequences whose sum equal $left$ which next selected element is such $next$ in range $(last, left]$ ($next$ is strictly greater then last selected number $last$ and not greater than current sum $left$). The recursive stop when $left = 0$ then we found one valid subsequence

Recursive dp - O(n^3) - small n

### My approach for bigger n

Lets $magic(sum, cur)$ is the number of valid subsequences whose selected sum is $sum$ and current selecting element is $cur$

• $cur$ is init as $1$ (smallest element) and recursive stop when it greater than $n$ (largest element)

• $sum$ is in range $[0, n]$ when it equal $n$ then we found 1 valid subsequence so we return $1$, else if it greater than $n$ we stop the recursive

The complexity is still $O(n^3)$ which $O(n^2)$ calculation and $O(n)$ for bignum implementation

Recursive dp - O(n^3) - bignum result
Iterative dp - O(n^3) - bignum result

### My question

• Can I solve the problem in $O(n^2)$ or in $O(n^2 \times polylog(n))$

• Can I find the n_th element faster than $O(n^3)$

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 SPyofgame 2020-08-30 16:48:18 13
en3 SPyofgame 2020-08-30 16:18:25 7 Tiny change: 'roblem in Linear $O(n^2)$ ' -> 'roblem in $O(n^2)$ '
en2 SPyofgame 2020-08-30 12:55:06 64 Tiny change: 'he **n_th* element ' -> 'he **n_th** element '
en1 SPyofgame 2020-08-30 12:52:29 5147 Initial revision (published)