線性方程正整數解個數?

01-27

$Sigma x_{i} =N$
給定一組解，求它是第幾組解
假設0,0...,0,N是第一組，依次N,0,0...,0是最後一組

動態規劃會嗎？

用 $f(n,k)$ 表示把n拆成k個非負整數的方案數。

顯然 $f(*,1) = 1$ 。

然後可由遞推式 $f(n,k) = sum_{i=0}^{n}f(n-i,k-1)$ 求出所有的 $f(n,k)$ 。求和式中的i代表拆出來的第一個數是幾。

有了這些 $f(n,k)$ ，就可以求任一組解的序號了。

先舉個例子：假設要把20拆成4個數，求5,3,9,3的序號。

顯然由0,1,2,3,4開頭的解都會排在它前面，這些解有 $f(20,3) + f(19,3) + f(18,3) + f(17,3) + f(16,3)$ 組。

然後以(5,0), (5,1), (5,2)開頭的解也都會排在它前面，這些解有 $f(15,2) + f(14,2) + f(13,2)$ 組。

然後只需考慮以(5,3)開頭的了。因為只剩下兩個數，所以(9,3)是第10組解。

把上面這些數加起來，就是5,3,9,3的序號。

推廣一下，如果給定的分拆方式是 $a_1, ldots, a_k$ ，且記 $s_i = sum_{j=i}^{k} a_i$ ，則這種分拆的序號是：

$left[ sum_{i=1}^{k-2} sum_{j = s_{i+1}+1}^{s_i} f(j,k-i) ight] + a_{k-1} + 1$ 。

注意到 $f(n,k) = sum_{i=0}^n f(i,k-1)$ ，

所以內層求和 $sum_{j=s_{i+1}+1}^{s_i} f(j,k-i) = f(s_i, k-i+1) - f(s_{i+1}, k-i+1)$ ，

序號就可以化簡為 $left{ sum_{i=1}^{k-2} left[ f(s_i, k-i+1) - f(s_{i+1}, k-i+1) ight] ight} + a_{k-1} + 1$ 。

======================================

寫完後發現，由隔板原理， $f(n,k)$ 其實就是組合數 $left( egin{array}{c} n+k-1 \ k-1 end{array} ight)$ ，

所以序號就是 $sum_{i=1}^{k-2} left[ left( egin{array}{c} s_i + k - i \ k - i end{array} ight) - left( egin{array}{c} s_{i+1} + k - i \ k - i end{array} ight) ight] + a_{k-1} + 1$ 。