4
$\begingroup$

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.

  • 3
    Executing `Count[Total /@ Tuples[Range[0, 10], 4], 30]` in *Mathematica* gives 286, but I'd like to see a slicker solution.2010-10-24
  • 1
    Perhaps we can close this as a dupe of http://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-to/ or maybe http://math.stackexchange.com/questions/4643/an-efficient-method-for-computing-the-number-of-submultisets-of-size-n-of-a-give/2010-10-24

2 Answers 2

8

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$.

  • 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.2010-10-24
6

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.

  • 0
    That's beautiful! Qiaochu's method is how I would have done it, but I find this very compelling.2011-05-20