Combinatoric problem

假設答案是R(n, k) - 假設可以重覆。（1 + 2 , 2 + 1 當不同combinations）

第一個數字一定要是1,2,3, .. [n - (k - 1)], 因為後面最少也是1, 所以有 k - 1 咁多個 1。

所以

R(n, n) = 1 只可以全部都是1
R(n, 1) = 1 只可以一個 n
R(n, k) = Sum(i = 1.. [n - k + 1]) R(n - i. k - 1)) [ when 0 < k < n ]，第一個是i, 其它用Recursive的方式表示。

For example, R(3, 2)
= sum(i = 1 .. [3 - 2 + 1]) R(3 - i, 2 - 1)
= sum(i = 1 .. 2) R(3 - i, 1)
= R(2, 1) + R(1, 1)
= 2 , in this case 1 + 2 and 2 + 1

For another example R(4, 3)
= sum(i = 1 .. [4 - 3 + 1]) R(4 - i, 3 - 1)
= sum(i = 1 .. 2) R(4 - i, 2)
= R(3, 2) + R(2, 2)　留意，R(3, 2) 已經算過，不用再expand
= 2 + 1
= 3, in this case (1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1)

從表現答案的角度來說，這個答案可能比上一個答案長，數學上感覺不太簡潔。但從計算的角度來說，這個表現方式可以用動態規劃(Dynamic Programming)計算出來，所需要計算時間比計算nCr和factorial 快多了。這是典型的電腦上算法的買賣，用空間換取時間。

如果不可以有重覆，上述的方法也可以做得到，而用括孤的人兄就做不到了。Basic idea 是做一個三維的動態規劃。最後一個維度，是最少可以填進的數字。

S(n, k, p) = 1 (when n = kp，這時候，只可能使用 k 個 p 去表示 n)
S(n, 1, x) = 1 只可以一個 n　表示 n, x 是甚麼都沒關係。
S(n, k, p) = Sum(i = p .. floor(n/k)) S(n - i, k - 1, i)

最後一式需要一點點解釋，因為n - i 如果少於 (k - 1) i，那S(n - i, k - 1, i)就是0, 所以summation中的i必須保持 n - i <= (k - 1)i，換句話說 n/k <= i，而i 亦必須是整數，所以用了floor function, 就是truncate（拿掉小數點後的東西，不是四捨五入), floor(5/3) = 1, 雖然5/3 = 1.6666....

真正的答案將會是S(n, k, 1)

例題目的S(5, 3, 1)

S(5, 3, 1)
= Sum(i = 1 .. floor(5/3)) S(5 - i, 3 - 1, i)
= Sum(i = 1 .. 1) S(5 - i, 2, i)
= S(4,2,1)
= Sum(i = 1 .. floor(4/2)) S(4 - i, 2 - 1, i)
= Sum(i = 1 .. 2) S(4 - i, 1, i)
= S(3, 1, 1) + S(2, 1, 2)
= 1 + 1
= 2

當然如此的計算有法是為了表示的方便，如果是真正要計算比較大的n跟k時，還是用列表的方式比較合理。

i had thought this problem before and discuss with my classmates,hope that you know wt i mean, in fact, i am not solving yuor problem, our problem is similar to yours, hope that it can brainstorm you!

======================================
我同同學investigate的question係咁o既

a+b+c=10 有幾多組solutions?

sol:
imagine the following graph in your brain.


1 1 1 1 1 1 1 1 1 1=10

上面係有10個1,中間有空隙,d空隙係用來放d "+"號,我e家random放2個"+"號,i.e.

1 1 1 1 1+1 1+1 1 1=10

咁樣,我當頭5個1係我地o既a,中間2個1係b,最尾3個1係c,

i.e

a + b + c =10
(1 1 1 1 1)+(1 1)+(1 1 1)=10
5 + 2 + 3 =10

咁樣,the question will transform into,係9個空隙中放2個"+"號有幾多combination
the answer is obvious 9C2=9!/(7!)(2!)
===========================
但你個question係1+2+2=2+1+2,就唔可以好似我地咁做,雖然我無answer you,但希望你有d idea.

do you understand?