---

1.回憶高中排列組合教過 a[1] + a[2] + ... a[m] = K 非負整數解數量的求法：

    數量就是：C (k+加號個數) 取 加號個數 (或常聽到的"C (k+m) 取 k(或m)")

 

    可以想像成：這些加號要擺在這 K 個東西之間總共有幾種可能(加號一樣、K個東西也一樣)

 

2.再來想：a[1] + a[2] + ... + a[m] <= k 的 非負整數解數量 求法 為 :

 

    ※法-1 設一個 u = k - (a[1] + a[2] + ... + a[m]) (右邊跟左邊差的量)

 

    這樣一來，在左邊補個"+u"，就可以把式子重新改寫成以下：

 

        a[1] + a[2] + ... + a[m] + u = k ("小於等於"變成"等於")

 

    便變成與上面 1. 一樣的形狀，於是可以使用上面的公式求解

 

    u 的直觀作用就是把前面 a[1]加到a[m] 後，還不足 k 的量吸掉，所以小弟個人喜歡稱他叫"垃圾桶"。

 

 

    ※法-2 "<= k" ，意思就是 " = 0(因為每一項都 >= 0，所以相加一定 >=0，於是從0開始) 、 1 、 2 、... 直到k" 所有數量的相加

 

        把每一個"等於"對應的數量寫下來，再用 帕斯卡原理 加起來。

 

-------------------------------------------------------------------------------------------分隔線-------------------------------------------------------------------------------------

 

 

現在可以這樣拆解問題：

 

原題目: x + 2y + 2z = n 的非負整數解數量

 

    (1) 把 x 移過去 → 2(y + z) = n - x

        又因為 x >= 0 ，所以原題目等價於" 2(y + z) <= n 的非負整數解數量"

        (舉例: x = 0時對應到"= n"，x=1對應到"= n-1"，以此類推)

 

    (2) 將2除過去，得到 y + z <= n/2 (n 如果是奇數則 n/2 不是整數，但等一下這個問題會解決)，一個與上方 2. 一樣形狀的式子，所以知道他應該能使用 2. 的解法

 

    (3) 回到原式，將 y 跟 z 先括在一起:

            x + 2(y + z) = n

 

        正好發現已經有 x 這個現成的"垃圾桶"。而因為它 係數=1 的特性，在(2)當中 n 為奇數導致 n/2 不為整數的問題則可以被解決，只要先把 1 個 "1" 丟進 x 裡就行了

 

    (4) 最後套用上方 2. 的公式，得到原題目的解為：

            C (n+2) 取 2

            = (n+2)*(n+1) / 2

 

結語：

    雖然這一題應該是要練習演算法的使用，不過卻被小弟我用"人腦"先代勞去了...。就當是複習排列組合吧！