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

aimisiyou

求将一正整数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

\[D(N,k)=\sum_{i=0}^{N-k} C_{N-2-i}^{N-k-i}\]

aimisiyou

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

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