Asked by picklepeter
How many nonnegative integer solutions does the equation x+y+z+t = 15 have?
Answers
Answered by
oobleck
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
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
There are no AI answers yet. The ability to request AI answers is coming soon!