论坛 › 算法交流 › 将整数N拆分为k个正整数之和的总方案数

aimisiyou 发表于 2021-3-15 09:58:21

将整数N拆分为k个正整数之和的总方案数

求将一正整数N拆分为k（k<=N）个正整数之和`x_1+x_2+...+x_k`的解数D(N,k).
比如 5=1+1+3=1+3+1=3+1+1=1+2+2=2+1+2=2+2+1，故D(5,3)=6.

aimisiyou 发表于 2021-3-15 13:59:53

\

aimisiyou 发表于 2021-3-15 14:41:23

6=1+1+4
=1+4+1
=4+1+1
=1+2+3
=1+3+2
=2+3+1
=2+1+3
=3+1+2
=3+2+1
=2+2+2

D(6,3)=C(1,0)+C(2,1)+C(3,2)+C(4,3)=10

zeroieme 发表于 2021-3-15 18:10:59

n个1，之间可以选+号或者,号。选+号的合并成一个数，选,号的是前面合并和的间隔。
于是n-1个位置，有k-1个,号。

查看完整版本: 将整数N拆分为k个正整数之和的总方案数