How many ways to write 4 as the sum of 5 non-negative integers?

[fleazo]

the problem:
In how many ways can we write the number 4 as the sum of 5 non-negative integers?I realize this is a generalized combinations problem. I can plug it in using a formula, but I want to understand the logic behind why the generalizaed combination formula works. More specifically, my book gives a description of the problem and I don't understand why it works at all. I have taken a screen cap of the solution that my book provides. Here it is

http://imgur.com/8BhxXPq

So I understand the concept of how they're explaining this - for example - one possible selection is I chose "box 1" 2 times, "box 2" 1 time, "box 3" 0 times, "box 4" 2 times, and "box 5" 0 times, this corresponds to : 2 + 1 + 2 = 5.

The confusion for me is, it seems like this approach would have a lot of repeats. For example - the selection of "box 1" 0 times, "box 2" 0 times, "box 3" 2 times, "box 4" 1 time, and "box 5" 2 times, would also produce : 2 + 1 + 2 = 5.I realize I'm missing something in the logic, but I'm not sure what.

Homework Equations

C(r + n -1, r) (generalized combinations with repetitions allowed formula)

The Attempt at a Solution

see the above section, this thread is about trying to understand a solution attempt in a textbook

 

[Borek]

So I understand the concept of how they're explaining this - for example - one possible selection is I chose "box 1" 2 times, "box 2" 1 time, "box 3" 0 times, "box 4" 2 times, and "box 5" 0 times, this corresponds to : 2 + 1 + 2 = 5.

You have "overselected" - you can't select 5 boxes, as you have only 4 balls (and each ball is used to select a box).

I am not stating I understand the solution, but your initial approach is already wrong.

 

[fleazo]

Oops, yes it seems in the examples I gave I was using 5 rather than 4. That was just a dumb mistake on my part. But if I redo the examples using 4 balls, I still have the same problem right?

(example - "box 1" 2 times, "box 2" 2 times and all the rest 0 equates to 2 + 2, "box 3" 2 times, "box 4" 2 times and all the rest 0 also equates to 2 + 2.)

The reason I'm asking specifically about this approach is because I googled around and found this exact approach the box uses to solve this problem many times. I just can't wrap my head around it because I'm wondering where all these repeats go :(

 

[PeroK]

The confusion for me is, it seems like this approach would have a lot of repeats. For example - the selection of "box 1" 0 times, "box 2" 0 times, "box 3" 2 times, "box 4" 1 time, and "box 5" 2 times, would also produce : 2 + 1 + 2 = 5.

I realize I'm missing something in the logic, but I'm not sure what.

You're right about the repeats, but it says in the solution that the order does not matter in the box analogy. So, these repeats get bundled up in the calculation.

If the order did matter, then you'd have $5^4$ choices.

So, order does matter in the original setting of the problem, but does not matter when you use the box mapping.

 

[fleazo]

Hi PeroK, perhaps you could elaborate a little bit, because this is where my disconnect is happening.


I understand that in a "combinations" problem (as opposed to a permutation problem), the order doesn't matter, and so repeats come out in the calculation. My confusion is seeing how their visual analogy works, because I think it winds up giving an additional set of repeats which don't get filtered out. Let me rephrase their approach to a similar problem where it makes sense. This should highlight why I don't think the analogy works on their problem.

I believe the setup their using would work for this problem: "How many ways can you select 4 cans of soda, from a cooler stocked full of Coke, Pepsi, 7UP, Dr. Pepper, and Diet Coke?" I'm going to use their visual approach, only with bit strings instead of boxes, since I can't draw boxes here. So if I were to set up this problem I'd first recognize two things: (1) order doesn't matter (2) repeats are allowed. I could envision the problem this way: I have a bit string of 4 0's and 4 1's, where 0's represent "column partitions", (a column for each type of soda), and the 1's in between these column partitions correspond to how many selections of that column's soda I've made. Here's an example of such a bit string:


10101001

Now suppose my columns are like this:

---------------------------------------------------
Coke | Pepsi | 7UP | Dr. Pepper | Diet Coke
---------------------------------------------------

Then the bit string above translates to: 1 Coke, 1 Pepsi, 1 7up column, then I skip Dr. Pepper column, and there's 1 for Diet Coke. So this corresponds to selecting 1 Coke, 1 Pepsi, 1 7UP, and 1 Diet Coke. I can visualize it like this:

-------------------------------------------
Coke | Pepsi | 7UP | Dr. Pepper | Diet Coke
--------------------------------------------
1----0-1----0-1---0-----------0-1----------

Similarly:

01001110 would correspond to 3 Dr. Peppers and a Pepsi.

--------------------------------------------
Coke | Pepsi | 7UP | Dr. Pepper | Diet Coke
--------------------------------------------
-----0-1----0-----0-111-------0------------

Using this setup, I can now think of the problem as "how do I rearrange 4 1's, in a bit string of length 8, where order doesn't matter? This is C(8,4) = 70 choices. in fact, this is the answer they arrive at in the book for their problem.


Now here's why I don't see the connection between this problem and the one they've given.

In my problem, suppose I have bit strings:

10001110 and 1110100

This first bitstring is 1 Coke and 3 Dr. Peppers, and the second one is 3 Cokes and a Pepsi. These are distinct answers.

Now in THEIR problem, 10001110 and 1110100 both correspond to 1 + 3, which are NOT distinct answers.

So see my confusion is, it seems like in the "soda approach", each bit string arrangement is a *unique* answer, whereas in this "integer problem", there are bit string arrangements which are repeats of each other. Now, the fact that the "soda problem" reduces to a combinations problem (arranging bit strings), is what allows repeats to be filtered (i.e., 1's are indistinguishable, so this is why it's not a permutation problem). But what I'm getting at is they don't seem to be the same repeats I'm concerned about. When this approach is used on the "integer problem" there seem to be an additional set of repeats going on, and I don't see how they're filtered out.

 

[PeroK]

Their analogy works like this:

If you have 5 integers that add to 4, where the order does matter. These are all strings of 0, 1, 2, 3 and 4. E.g. 0-2-1-0-1 or 0-0-0-4-0.

Each of these corresponds to a combination (where the order does not matter) of placing 4 balls in 5 boxes.

0-2-1-0-1 corresponds to 2 balls in the 2nd box, 1 in the 3rd box and 1 in the 5th box

0-0-0-4-0 corresponds to 4 balls in the 4th box.

You need to convince yourself that there is a 1-1 correspondence here.

The second problem, the one with the boxes, has an already known solution in terms of binomials.

I'd forget the soda analogy. I don't think that helps.

 

[fleazo]

Their analogy works like this:

If you have 5 integers that add to 4, where the order does matter. These are all strings of 0, 1, 2, 3 and 4. E.g. 0-2-1-0-1 or 0-0-0-4-0.

Each of these corresponds to a combination (where the order does not matter) of placing 4 balls in 5 boxes.

0-2-1-0-1 corresponds to 2 balls in the 2nd box, 1 in the 3rd box and 1 in the 5th box

0-0-0-4-0 corresponds to 4 balls in the 4th box.

You need to convince yourself that there is a 1-1 correspondence here.

The second problem, the one with the boxes, has an already known solution in terms of binomials.

I'd forget the soda analogy. I don't think that helps.

You need to convince yourself that there is a 1-1 correspondence here.

This is where I'm struggling. Based on my understanding, 0-2-1-1-0 is equivalent to the "answer" 2 + 1 + 1. But how would the answers 0-2-1-1-0 and 2-1-0-1-0 be different from each other? This is where I'm failing to see the 1 - 1 correspondence, as both are valid combinations that would come out using the "box method", but here, 0-2-1-1-0 is equivalent to 2 + 1 + 1 and so is 2-1-0-1-0.

 

[PeroK]

You've misunderstood the original problem. You're looking for 5 numbers that add to 4 where:

0-0-0-0-4 and 0-0-0-4-0 are different possibilities.

This is what is meant by "the order matters".

If the order (in the original problem) did not matter, you would only have 5 possibilities:

4
1+3
2+2
1+1+2
1+1+1+1

To get 70 possibilities, you need to add in the 0's and allow any order.

 

[fleazo]

So you're saying the problem is, assume x_1, x_2, x_3, x_4, and x_5 are 5 numbers such that when you add them together, they equal 4, and the problem in the book is asking: how many different ways can we select sets of 4 of these variables, where repeats are allowed? (so in their analogy, each "box" is equivalent to one of the variables, where the number of balls in that box is saying how many times we're picking that specific variable).


Yes, I thought the original question was literally asking "how solutions are there to the problem x_1 + x_2 + x_3 + x_4 + x_5 = 4, where x_1, x_2, x_3, x_4, and x_5 are all non-negative integers.

 

[PeroK]

So you're saying the problem is, assume x_1, x_2, x_3, x_4, and x_5 are 5 numbers such that when you add them together, they equal 4, and the problem in the book is asking: how many different ways can we select sets of 4 of these variables, where repeats are allowed? (so in their analogy, each "box" is equivalent to one of the variables, where the number of balls in that box is saying how many times we're picking that specific variable).

No, the problem is how many ways to add x_1 ... x_5 to equal 4. That's the problem. The equivalent problem is how many ways can 4 balls be put in 5 boxes, where the number of balls in box b_1 = the value of the variable x_1.

Yes, I thought the original question was literally asking "how solutions are there to the problem x_1 + x_2 + x_3 + x_4 + x_5 = 4, where x_1, x_2, x_3, x_4, and x_5 are all non-negative integers.

It is!

 

[fleazo]

I have to be honest, I feel like a bit of a dunce here because I don't seem to understand what the problem is even asking :( I'm sorry to be beating a dead horse.If this is what it is asking ("how many solutions are there to the problem x_1 + x_2 + x_3 + x_4 + x_5 = 4, where x_1, x_2, x_3, x_4, and x_5 are all non-negative integers?) then how is it possible that order doesn't matter, when answering this question? It seems like there are only 5 possibilities: 4, 1 + 1 + 1 + 1, 1 + 2 + 1, 1 + 3, 2 + 2. I get that you're saying these 5 answers are only when order matters. But I just can't wrap my head around order NOT mattering - how can 2 + 2 (coming from the "box solution" of 0-0-2-2-0) be distinct from 2 + 2 (coming from the "box solution" of 2-0-2-0-0)?

 

[PeroK]

Well, suppose each number was picked by a different person? Let's call them x_1 to x_5. Then x_1 picking 4 and the rest picking 0 is different from x_2 picking 4 and the rest picking 0.

 

[fleazo]

ok, this does make sense when you put it this way! Thank you very much :)Two follow up questions -

(1) If you were to see the original problem statement (how many ways to write 4 as the sum of 5 non-negative integers?), which version would you jump to, the one where order matters (where you get 5 as the answer), or the one where order doesn't matter? (as in the book, where you get 70 as an answer). The reason I ask is because, the way that problem is asked, I would immediately jump to wanting to get 5 as the answer, and so I'm worried there's something off in the way I'm interpreting the question. I seem to misinterpreting a lot of word problems when it comes to combinations/permutations.

(2) Just out of curiosity, is there a permutation/combination formula I could use to answer the problem I thought it was asking - the one where order DOES matter and you get 5 as the answer? Because that to me seems like the more "practical" problem. As in, I could see myself really wanting to know the answer to such a question, but I'm not sure how I'd compute it other than brute force.

 

[PeroK]

(1) I thought initially as you did, but soon realized what was intended. The question, as stated, is ambiguous.

(2) I don't know. You could try working it out for a few examples and see if you can spot a pattern that could be proved inductively.

 

[fleazo]

Thanks PeroK, as long as I know the problem statement is a little ambiguous, I feel better. As for (2), I'll play around with it, I just wasn't sure if there was just a super common formula that I just didn't know which is why I had asked.

Thanks for all the help, especially since it took me so many replies to understand what you were getting at!