Given an integer, how many ways can you divide into unequal portions

Question

I have been thinking about this problem for a while but have been unable to formalize a complete answer.

Given an integer $n \geq 3$, how many different sets can you sum the integer elements in the set to equal n ?

Constraints:

1) Each set must contain at least 2 elements.

2) All elements in a set must sum to $n$ (all elements must be greater than 0).

3) Normal set rules apply: No elements in a set can be repeated, and Order doesn't matter

Examples:

when n = 3 the only possible set is {1, 2} so the answer would be 1.

when n = 4 the only possible set is {1, 3} so the answer would be 1.

when n = 5 there are two sets {1, 4}, {2, 3} so the answer would be 2.

This is meant to be a programming question. I think the answer could be computed as a math equation, or at least a dynamic programming approach. My goal is for the run time to not exceed O(n), however O(1) would be great. If you want to provide code python like syntax would be fine.

Answer 1

This is one less than OEIS A000009, which begins $1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718, 6378$. The one less comes because you prohibit the partition of $n$ into $\{n\}$ which the OEIS sequence allows. No simple formula is given, but one of the asymptotic ones is $$a(n) \approx \exp(\pi\sqrt{n/3})/(4\cdot 3^{1/4}\cdot n^{3/4}) \cdot (1 + (\pi/(48\sqrt3) - (3\sqrt3)/(8\pi))/\sqrt n + (\pi^2/13824 - 5/128 - 45/(128\pi^2))/n)$$

Answer 2

Let $N_i(n)$ give the number sets of size $i$. You want $\sum_{i=2}^\infty N_i(n)$.

Clearly $N_2(n) = \lfloor\frac{n-1}{2}\rfloor$.

To compute $N_3(n)$, we're going to try to find the three-member set from least to greatest. If the least member is a $1$, then the other members are all at least $2$; we can subtract $1$ from the other $2$ members, and we need two unequal numbers adding to $n-3$; there are $N_2(n-3)$ such possibilities. Similarly, if the least member is $2$, there are $N_2(n-6)$ possibilities; etc. So $N_3(n) = \sum_{i=1}^{\lfloor\frac{n}{3}\rfloor} N_2(n-3i)$.

Similarly, $N_4(n) = \sum_{i=1}^{\lfloor\frac{n}{4}\rfloor} N_3(n-4i)$

You can try to devise some computation method based on these relations; however, I'm not sure it will be so computationally efficient.