Number of partitions of n into at least two distinct parts

Правка en2, от SPyofgame, 2020-08-30 12:55:06

About the problem

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 Linear $$$O(n^2)$$$ or in $$$O(n^2 \times polylog(n))$$$

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

Теги combinatorics, math, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)