1
$\begingroup$

How many solution does $x+y+z=11$ have where $x, y, z$ are non-negative integers. In light of the restrictions, its clear that $x,y,z \in \{0,1,2,..11\}$. So, at face value I would assign a value for $x$ and determine the different combinations that $y$ and $z$ can hold. For example,

For $x=0$, we have $y+z=11$. With writing them out I found that there are $12$ different assigned combinations for $y$ and $z$ that satisfy the equation. For $x=1$, I got $11$. Consequently, the pattern becomes clear whereby each one takes a value less by one. Hence, the number of solutions is $1+2+3+4+5+6+7..+12=78$. I was wondering if there is an easier method perhaps with combinations equation $C(a,b)$..?

$\endgroup$
  • $\begingroup$ We have had too many questions of this type. $\endgroup$ – evil999man May 3 '14 at 12:13
  • $\begingroup$ See my answer here:math.stackexchange.com/questions/689975/… $\endgroup$ – evil999man May 3 '14 at 12:15
  • $\begingroup$ Guys, stop upvoting duplicate homework questions, seriously! $\endgroup$ – Alec Teal May 3 '14 at 12:18
  • $\begingroup$ @Alec Lighten up. The OP shows plenty of effort, and arrives at the correct answer in doing so. It deserves an upvote. John likely didn't know that this is a classic sort of problem, and probably hasn't encountered it before. Nor that many similar questions can be answered by the same method. And if you believe it is a duplicate and should be slammed shut because of it, then why'd you answer it? Besides, stop playing the homework police on questions showing commendable levels of effort! $\endgroup$ – amWhy May 3 '14 at 12:24
  • $\begingroup$ @amWhy Not thinking something deserves an upvote isn't the same as saying it deserves to be closed. When I upvote something, what I personally mean is "this is the kind of content I come to the site for". My preferred policy would for routine problems to be dealt with quickly and without fanfare (positive or negative), and to save upvotes (and therefore time on the front page) for the more original, thought-provoking questions. $\endgroup$ – Jack M May 3 '14 at 12:28
9
$\begingroup$

This is a version of the classic stars-and-bars problem in combinatorics.

For any pair of natural numbers $n$ and $k$, the number of distinct $n$-tuples of non-negative integers whose sum is $k$ is given by the binomial coefficient $$\binom{n + k - 1}{k}$$

Here, $n = 3$, and $k = 11$, giving you $$\binom{3 + 11 - 1}{11} = \binom{13}{11} = \dfrac{13\cdot 12}{2} = 6\cdot 13 = 78$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The link takes you to Wikipedia's Stars and Bars entry, where you'll find a nice explanation of why this works, using an example that's fleshed out nicely. $\endgroup$ – amWhy May 3 '14 at 12:17
  • $\begingroup$ Using the formula makes things easy, but I don't see what the connection is. Even with using the stars and bars method, it seems rather inappropriate, due to the dependency of the variables. In other terms, if x takes a value it creates a dependency on the other variables. I would appreciate it if you could make the connection clearer. $\endgroup$ – John May 3 '14 at 13:41
  • $\begingroup$ Did you read the Wikipedia entry? It elaborates on the "why's" of this formula. $\endgroup$ – amWhy May 3 '14 at 13:45
  • $\begingroup$ I read it and I understood everything but when I went to this question, math.stackexchange.com/questions/322369/…, with the additional restrictions I started to doubt everything. None of the answers that used combinations were clear. $\endgroup$ – John May 3 '14 at 13:49
  • 1
    $\begingroup$ Yes. I see you used $x, y, z$, so if only $x$ needs to be greater than or equal to 2, then the solution (with k=11 - 2 = 9) is $\binom{3 + 9 - 1}{9}$. $\endgroup$ – amWhy May 3 '14 at 15:17
0
$\begingroup$

imagine 11 balls in a row and two blocks which you will place somewhere. you insert the blocks before, after or between the balls and then you assign values to $x,y,z$ in the following way: $x$ is the number of balls from the beginning of the row up to the first block, $y$ the number of balls between the two blocks and $z$ number of balls from the second block up until the end of the row. you will easily see that the number of ways in which you can place the blocks is equal to the number of different triplets $x,y,z$. Do you know how to compute the number of possible distributions of blocks?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ call it stars and bars if you don't like blocks and balls, but this is the usual way to approach such problems $\endgroup$ – Alessandro Codenotti May 3 '14 at 12:15
  • $\begingroup$ it's an answer explained in a tangible way. actually it's pretty much the same thing you gave as an answer although it's explained with words rather than a picture. $\endgroup$ – mm-aops May 3 '14 at 12:15
  • $\begingroup$ Oh right! You could have laid it out nicer, I thought you did some weird thing that'd result in a 3! somewhere $\endgroup$ – Alec Teal May 3 '14 at 12:16
  • $\begingroup$ Could you edit the answer so I may at least remove my DV? $\endgroup$ – Alec Teal May 3 '14 at 12:17
0
$\begingroup$

Okay let us write a solution to $a+b+c+d+e=10$ a different question, just incase it is homework.

Each solution will have the form:

||||-|---||||| <-> 4As 1B 0Cs, 0Ds, 5Es 

How many different ways can we arrange 10 |s and 4 (4=5-1) -s? Each arrangement of these |s and -s is a valid solution.

$$\frac{(10+4)!}{4!10!}=\frac{14!}{10!4!}$$

| cite | improve this answer | |
$\endgroup$

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