Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many solutions does the following equation have?

$$k+l+m+n=30,$$

where $k,l,m,n\in\mathbb{Z},0\leq k,l,m,n\leq 10.$

Edit: this is an exercise in the inclusion-exclusion principle.

share|improve this question
3  
Executing Count[Total /@ Tuples[Range[0, 10], 4], 30] in Mathematica gives 286, but I'd like to see a slicker solution. –  J. M. Oct 24 '10 at 12:21
1  
Perhaps we can close this as a dupe of math.stackexchange.com/questions/4632/… or maybe math.stackexchange.com/questions/4643/… –  Aryabhata Oct 24 '10 at 13:01
add comment

2 Answers

up vote 7 down vote accepted

This is the coefficient of $x^{30}$ in $(1 + x + ... + x^{10})^4$. (To see this, think about what happens when you choose a term from each factor.) But this is $\frac{(1 - x^{11})^4}{(1 - x)^4}$. Now,

$$\frac{1}{(1 - x)^4} = \sum_{n \ge 0} {n+3 \choose 3} x^n$$

(which you'll recognize as the generating function giving the answer to the problem without the range restriction.) On the other hand, $(1 - x^{11})^4 = 1 - {4 \choose 1} x^{11} + {4 \choose 2} x^{22} - {4 \choose 3} x^{33} + x^{44}$. Of these terms only the first three contribute to the coefficient of $x^{30}$, making the final answer

$${33 \choose 3} - {4 \choose 1} {22 \choose 3} + {4 \choose 2} {11 \choose 3} = 286.$$

This is equivalent to the following inclusion-exclusion argument: start with the set of all solutions with no restriction. Remove all the solutions where one of the four numbers is greater than $10$. Add back in all the solutions where two of the four numbers are greater than $10$.

share|improve this answer
1  
@MFV: when we start with the set of all solutions, we've overcounted the solutions where at least one of the four numbers is greater than 10. When we subtract the solutions where k is greater than 10, then l is greater than 10, etc. we overcount the solutions where two of the four numbers are greater than 10. When we subtract those solutions we are done because three of them cannot be greater than 10. –  Qiaochu Yuan Oct 24 '10 at 14:31
add comment

A geometric way of seeing the answer is this: this is the number lattice points in the cube $[0,10]^4$ that intersects the plane $k+l+m+n = 30$. Note that the corners $(0,10,10,10)$ are points on this plane. Since the weights on $k,l,m,n$ are equal, the solutions are in bijection (it would be clear once you draw a picture) with the lattice points in the $k,l,m$ plane that is inside the tetrahedron formed by the vertices $(0,10,10)$, $(10,0,10)$, $(10,10,0)$ and $(0,0,0)$, the total number of which would be the 11th tetrahedral number which is 286.

share|improve this answer
    
That's beautiful! Qiaochu's method is how I would have done it, but I find this very compelling. –  Brian Hopkins May 20 '11 at 4:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.