[其他] 排列組合
主要是找非負整數解的所有組合 題目如下
X1 + X2 + ... + Xn = k, 0<= Xi <= m
找出 k=0,1,2,....,nm 的所有組合 把它定義成 S(n,k) 好了
我的算法如下
k=0到m 其實就是一般的問題(高中或大學離散都有教)
S(n,k)=H(n,k)=C(n+k-1,k) for k=0,1,...,m
k 從 m+1 到 2(m+1)-1 必須考慮到可能多算了某個 Xi>=m+1 故
S(n,k)=H(n,k)-C(n,1)*H(n,k-(m+1)) for k=m+1,...,2(m+1)-1
k 從 2(m+1) 到 3(m+1)-1 必須扣掉某兩個Xi,Xj>=m+1 或某個Xi>=2(m+1)
S(n,k)=H(n,k)-C(n,2)H(n,k-2(m+1))-C(n,1)H(n,k-2(m+1))
不知道這一步有沒有錯誤
若沒有...很容易類推 k 從 r(m+1) 到 (r+1)(m+1)-1
S(n,k)=H(n,k)-H(n,k-r(m+1))*[C(n,1)+C(n,2)+...+C(n,r)]
for k=r(m+1),...,(r+1)(m+1)-1 , r=1,2,...,n-1
覺得似乎有哪裡怪怪的...但說不上來
另外若給定一個 0<a<1 則
nm
Sigma S(n,k)*a^(k)
k=0
有無類似二項式定理的說明或解釋?
(1+a)^n = C(n,0) + C(n,1)a + ... + C(n,n)a^n
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.105.30
→
05/03 20:47, , 1F
05/03 20:47, 1F
討論串 (同標題文章)
