I'm sure this exists somewhere online, but finding it will take some work. How about this idea?
Let f(n,k) be the number of solutions of sums of k integers that add to n.
f(13,2) = 12, since the sums are
1+11, 2+10, 3+9 ... 11+1
It should be easy to show that f(n,2) = n-1
Now, if you have k=3, there are 3C2=3 ways to pick the first two variables.
If you let the 3rd variable range from 1 to 12,
f(14,3) = 3C2 (f(13,2) + f(12,2) + f(11,2) + ... f(2,2))
= 3C2 * ((13-1)+(12-1) ... + (2-1))
= 3C2 * (13+12+...+2) - 12)
= 3C2 * 13*14/2 - 13
= 3 * 78
= 224
Now construct a similar step for f(15,4), knowing what f(14,3) is
How many nonnegative integer solutions does the equation x+y+z+t = 15 have?
1 answer