2
$\begingroup$

How many solutions are there to the equation $x + y + z + w = 17$ for non-negative integers $w, x, y, z$ ?

I don't know if I'm doing this right, but I guessed that the solution would be $\binom{20}{3}$, which equals $1140$. Am I doing this right?

  • 1
    See http://math.stackexchange.com/questions/86820/finding-the-number-of-solutions-to-an-equation and the questions referenced there.2011-12-15

2 Answers 2

4

Your result is correct. You are looking for the number of monomials of total degree $17$ in $4$ variables. There are $\binom{17+4-1}{17}=\binom{20}{17}=\frac{20\cdot 19\cdot 18}{3\cdot 2} = 20\cdot19\cdot3 = 1140$ of these.

A proof would be the following. We associate to any solution $(x,y,z,w)$ a weakly increasing sequence of length $17$, where $0$ appears $x$ times, $1$ appears $y$ times, and so on. For instance, the solution $(4,3,2,8)$ would correspond to $(0,0,0,0,1,1,1,2,2,3,3,3,3,3,3,3,3)$ By adding $i$ to the $i$-th component of that sequence, it becomes strictly increasing. This way, we can see that the solutions correspond to subsets of $\{1,\ldots,17+4-1\}$ of cardinality $17$. Of course, you can replace $17$ and $4$ by $n$ and $d$ to obtain a more general statement.

13

Line up $20$ skittles in a row:

+ + + + + + + + + + + + + + + + + + + + 

Knock any three of them over:

+ + + x + + + + + + x x + + + + + + + + 

Now let $x,y,z,$ and $w$ be the number of skittles left standing between the knocked-over skittles. In this case $x=3, y=6, z=0,$ and $w=8$.

So your answer is correct.

  • 1
    I was a bridge programmer a long time ago. In bridge, C + D + H + S = 13.2011-12-15