kuing

理论上用多项式展开也可以，只是我不清楚其时间和空间复杂度有多大，主要我没学过算法……

其原理倒是非常好理解，设
\[F=\left( \sum_{k=0}^{1000}x^k \right)\left( \sum_{k=0}^{\lfloor1000/2\rfloor}x^{2k} \right)\left( \sum_{k=0}^{\lfloor1000/3\rfloor}x^{3k} \right)\cdots\left( \sum_{k=0}^{\lfloor1000/999\rfloor}x^{999k} \right),\]
那么 `F` 展开式的 `x^{1000}` 的系数就是所求。
理由就是：展开时，第 `m` 个括号所取的项就代表拆分中含有 `m` 的个数。
如果你理解了前两天这帖 http://kuing.orzweb.net/redirect ... =5872&pid=29759 （11#）的解析，这个你应该也能明白。

用 Mathematica 来试一下：

1. f[sum_,max_] := Coefficient[Product[Sum[x^(m k), {k, 0, Floor[sum/m]}], {m, 1, max}], x^sum]

复制代码

那么楼主要求的就是 f[1000,999]，这个太大了，来算小一点的：
和为 10，无最大数限制的（即 10=10 也算一种），那就是 f[10, 10]，结果是 42，如果 10=10 不算那就是 41。
我手工拆了一次来验证此结果：

1. 10 = 10
   
2. 10 = 9+1
   
3. 10 = 8+2
   
4. 10 = 8+1+1
   
5. 10 = 7+3
   
6. 10 = 7+2+1
   
7. 10 = 7+1+1+1
   
8. 10 = 6+4
   
9. 10 = 6+3+1
   
10. 10 = 6+2+2
    
11. 10 = 6+2+1+1
    
12. 10 = 6+1+1+1+1
    
13. 10 = 5+5
    
14. 10 = 5+4+1
    
15. 10 = 5+3+2
    
16. 10 = 5+3+1+1
    
17. 10 = 5+2+2+1
    
18. 10 = 5+2+1+1+1
    
19. 10 = 5+1+1+1+1+1
    
20. 10 = 4+4+2
    
21. 10 = 4+4+1+1
    
22. 10 = 4+3+3
    
23. 10 = 4+3+2+1
    
24. 10 = 4+3+1+1+1
    
25. 10 = 4+2+2+2
    
26. 10 = 4+2+2+1+1
    
27. 10 = 4+2+1+1+1+1
    
28. 10 = 4+1+1+1+1+1+1
    
29. 10 = 3+3+3+1
    
30. 10 = 3+3+2+2
    
31. 10 = 3+3+2+1+1
    
32. 10 = 3+3+1+1+1+1
    
33. 10 = 3+2+2+2+1
    
34. 10 = 3+2+2+1+1+1
    
35. 10 = 3+2+1+1+1+1+1
    
36. 10 = 3+1+1+1+1+1+1+1
    
37. 10 = 2+2+2+2+2
    
38. 10 = 2+2+2+2+1+1
    
39. 10 = 2+2+2+1+1+1+1
    
40. 10 = 2+2+1+1+1+1+1+1
    
41. 10 = 2+1+1+1+1+1+1+1+1
    
42. 10 = 1+1+1+1+1+1+1+1+1+1

复制代码

和为 50 的，f[50, 50]，运行一分多钟得出 204226。
试了下 100，等好久都不出来，看来复杂度挺大，算了……

kuing

两个帖子都明白了，下次碰到能不能用起来？

@realnumber 为啥不能用？这些又不是新东西……

PS、修改了下标题。

kuing

再丢个链接：http://oeis.org/A000041

kuing

唉！我早就应该想到，这么经典的问题，Mathematica 应该已经自带相应命令，一查果然如此！！！
它们是 PartitionsP 和 IntegerPartitions，前者就是拆分方法数（同样包含 10=10 这种），后者则是列出具体的拆分。
参考：
https://reference.wolfram.com/language/ref/PartitionsP.html
https://reference.wolfram.com/language/ref/IntegerPartitions.html
比如，PartitionsP[10] 得出 42，而 IntegerPartitions[10] 得出：
{{10},{9,1},{8,2},{8,1,1},{7,3},{7,2,1},{7,1,1,1},{6,4},{6,3,1},{6,2,2},{6,2,1,1},{6,1,1,1,1},{5,5},{5,4,1},{5,3,2},{5,3,1,1},{5,2,2,1},{5,2,1,1,1},{5,1,1,1,1,1},{4,4,2},{4,4,1,1},{4,3,3},{4,3,2,1},{4,3,1,1,1},{4,2,2,2},{4,2,2,1,1},{4,2,1,1,1,1},{4,1,1,1,1,1,1},{3,3,3,1},{3,3,2,2},{3,3,2,1,1},{3,3,1,1,1,1},{3,2,2,2,1},{3,2,2,1,1,1},{3,2,1,1,1,1,1},{3,1,1,1,1,1,1,1},{2,2,2,2,2},{2,2,2,2,1,1},{2,2,2,1,1,1,1},{2,2,1,1,1,1,1,1},{2,1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1,1,1}}
排列的方式正和我上面手工列的一模一样，都是由大到小。

PartitionsP[50] 的结果是 204226，也和我们得到的一样。

但是 PartitionsP[1000] 得出的是 24061467864032622473692149727991（楼主想求的就是这个数减 1）那就和 9# 的不一样了。