• Support PF! Buy your school textbooks, materials and every day products Here!

How many ways to count to 20

  • Thread starter srfriggen
  • Start date
  • #1
288
3

Homework Statement


a) Given x1+x2+x3=20, for all positive integers, how many solutions are there?
b) For x > 3?

Homework Equations


Multichooose

The Attempt at a Solution


At first I computed "20 multi-choose 3" and got 231, but I believe that is counting zeros as part of the solutions.

So for the positive integers I computed "19 Multichoose 3" and go 210.

For x > 3 I computed "17 Multichoose 3" and got 171.

We looked at the method of counting say 5 multichoose 2 would be thought of as xlxxlxx, which is how many ways can you arrange two l's in 7 slots, or 7C2. So I have a decent understand how the multichoose function works but not so confident in my answers. I feel the x > 0 is correct.
 

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992

Homework Statement


a) Given x1+x2+x3=20, for all positive integers, how many solutions are there?
b) For x > 3?

Homework Equations


Multichooose

The Attempt at a Solution


At first I computed "20 multi-choose 3" and got 231, but I believe that is counting zeros as part of the solutions.

So for the positive integers I computed "19 Multichoose 3" and go 210.

For x > 3 I computed "17 Multichoose 3" and got 171.

We looked at the method of counting say 5 multichoose 2 would be thought of as xlxxlxx, which is how many ways can you arrange two l's in 7 slots, or 7C2. So I have a decent understand how the multichoose function works but not so confident in my answers. I feel the x > 0 is correct.
I'm not sure using binomials is a good way. First, I'd think about ##x_1##. How many values can it take?

Hint: Try a smaller number. Total of 5, say, then you can easily count all the ways and check your multichoose formula.
 
  • #3
33,646
5,315
To expand on PeroK's comment, if ##x_1## is known, there are only a relatively few number pairs of the other two numbers that will add up to 20. Do this kind of analysis for each possible value of ##x_1##, and add up all the different possible combinations.
 
Last edited:
  • #4
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
Further hint: do it for a total of 4, then 5, then 6 and try to spot the pattern.
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement


a) Given x1+x2+x3=20, for all positive integers, how many solutions are there?
b) For x > 3?

Homework Equations


Multichooose

The Attempt at a Solution


At first I computed "20 multi-choose 3" and got 231, but I believe that is counting zeros as part of the solutions.

So for the positive integers I computed "19 Multichoose 3" and go 210.

For x > 3 I computed "17 Multichoose 3" and got 171.

We looked at the method of counting say 5 multichoose 2 would be thought of as xlxxlxx, which is how many ways can you arrange two l's in 7 slots, or 7C2. So I have a decent understand how the multichoose function works but not so confident in my answers. I feel the x > 0 is correct.
If you really do mean positive integers, it is probably easiest to set ##x_1 = 1 + x'_1, x_2 = 1+ x'_2## and ##x_3 = 1 + x'_3##, with ##x'_1, x'_2, x'_3 \geq 0##, so you need ##x'_1 + x'_2 + x'_3 = 17##. Now, what are the possible values of ##x'_3?##. For each choice of ##x'_3## you know the value of ##x'_1 + x'_2 = n##. For fixed ##n##, how many possible values are there for ##x'_1?##. Now put it all together.

For ##x_1 > 3##, set ##x_1 = 4 + x'_1## with ##x'_1 \geq 0##. Now you need ##x'_1 + x'_2 + x'_3 = ??## Take if from there.

For both versions I get answers different from yours.
 
  • #6
288
3
If you really do mean positive integers, it is probably easiest to set ##x_1 = 1 + x'_1, x_2 = 1+ x'_2## and ##x_3 = 1 + x'_3##, with ##x'_1, x'_2, x'_3 \geq 0##, so you need ##x'_1 + x'_2 + x'_3 = 17##. Now, what are the possible values of ##x'_3?##. For each choice of ##x'_3## you know the value of ##x'_1 + x'_2 = n##. For fixed ##n##, how many possible values are there for ##x'_1?##. Now put it all together.

For ##x_1 > 3##, set ##x_1 = 4 + x'_1## with ##x'_1 \geq 0##. Now you need ##x'_1 + x'_2 + x'_3 = ??## Take if from there.

For both versions I get answers different from yours.
I see the mistake I made. For positive integers I should have done "3 multichoose 17" which I computed as 171.

For x > 3 I see that each x has to be fixed at 4, or I thought of it as "bins" with at least 4 objects in them. So that is 3 multichoose 20 - 4(3) = 3 multichoose 8, which I computed as 45.

For me it was easier to view the problem as the "stars and bars" method which is why I mentioned "bins."

Now I understand how to put a bottom limit on the x values, but what about an upper limit? What if I wanted x1 + x2 + x3 = 10 but 2 < x < 10. So 3 + 3 + 4 is a solution. Is there a ways using the stars and bars / multichoose intuition to put an upper limit? I've been working this out on paper for quite some time and haven't made any progress.
 
  • #7
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
I see the mistake I made. For positive integers I should have done "3 multichoose 17" which I computed as 171.

For x > 3 I see that each x has to be fixed at 4, or I thought of it as "bins" with at least 4 objects in them. So that is 3 multichoose 20 - 4(3) = 3 multichoose 8, which I computed as 45.

For me it was easier to view the problem as the "stars and bars" method which is why I mentioned "bins."

Now I understand how to put a bottom limit on the x values, but what about an upper limit? What if I wanted x1 + x2 + x3 = 10 but 2 < x < 10. So 3 + 3 + 4 is a solution. Is there a ways using the stars and bars / multichoose intuition to put an upper limit? I've been working this out on paper for quite some time and haven't made any progress.
Question (b) is ambiguous; I interpreted it as a misprint that meant to say that one of the x_i is > 3 (for example, x1 > 3) but the other two are unrestricted. You interpreted it as applying to all three of the xi. Whoever wrote the question should have made it clear.
 
  • #8
33,646
5,315
Question (b) is ambiguous; I interpreted it as a misprint that meant to say that one of the x_i is > 3 (for example, x1 > 3) but the other two are unrestricted.
It's certainly ambiguous. I would interpret x > 3 to mean that all three (##x_1, x_2, x_3##) are > 3.

Whoever wrote the question should have made it clear.
Absolutely.
 
  • #9
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
I see the mistake I made. For positive integers I should have done "3 multichoose 17" which I computed as 171.

For x > 3 I see that each x has to be fixed at 4, or I thought of it as "bins" with at least 4 objects in them. So that is 3 multichoose 20 - 4(3) = 3 multichoose 8, which I computed as 45.

For me it was easier to view the problem as the "stars and bars" method which is why I mentioned "bins."

Now I understand how to put a bottom limit on the x values, but what about an upper limit? What if I wanted x1 + x2 + x3 = 10 but 2 < x < 10. So 3 + 3 + 4 is a solution. Is there a ways using the stars and bars / multichoose intuition to put an upper limit? I've been working this out on paper for quite some time and haven't made any progress.
In my opinion, you are still missing the trick of using a smaller number to get your counting method verified. For example, if three numbers have to add up to 4, then we have:

1+1+2; 1+2+1; 2+1+1; giving a total of 3 ways

And for 5 we have:

1+1+3; 1+2+2; 1+3+1; 2+1+2; 2+2+1; 3+1+1 giving a total of 6 ways

If you are going to use the "stars and bars" approach, you are going to have to think it through. In particular, you can't have the two bars together. For the example of adding to 4, we have:

xlxlxx; xlxxlx; xxlxlx

It's easy to see that you must always start and end with an x and that you cannot have the two l's next to each other. Apart from that we are good. So, you need to count that.
 
  • #10
288
3
In my opinion, you are still missing the trick of using a smaller number to get your counting method verified. For example, if three numbers have to add up to 4, then we have:

1+1+2; 1+2+1; 2+1+1; giving a total of 3 ways

And for 5 we have:

1+1+3; 1+2+2; 1+3+1; 2+1+2; 2+2+1; 3+1+1 giving a total of 6 ways

If you are going to use the "stars and bars" approach, you are going to have to think it through. In particular, you can't have the two bars together. For the example of adding to 4, we have:

xlxlxx; xlxxlx; xxlxlx

It's easy to see that you must always start and end with an x and that you cannot have the two l's next to each other. Apart from that we are good. So, you need to count that.
The only reason I'm focused on the multichoose method (which I "see" as stars and bars) is because in this course we are leading up to a problem about "how many ways to roll an 18 on five dice." Now I've figured out the answer by listing the combinations , e.g. 6+6+2+2+1+1 then performing the method of, in this case, 5! / 2!2!2! on each of the 20 combinations. I got help from the PF community because I originally only listed 13 combinations. But knowing what I know now I would have been at least able to show there should be 20 right off the bat.

But my prof is going to want an answer in the form of multi chooses and combinations, which some inclusion/exclusion (that's what he said in class).

So I hope that clears up why I'm so focused on understanding one method vs. the others suggested. Also apologies for the ambiguous question. I suppose when I wrote it down in my book, in the context of the class that day, to me it made more sense.
 
  • #11
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
The only reason I'm focused on the multichoose method (which I "see" as stars and bars) is because in this course we are leading up to a problem about "how many ways to roll an 18 on five dice." Now I've figured out the answer by listing the combinations , e.g. 6+6+2+2+1+1 then performing the method of, in this case, 5! / 2!2!2! on each of the 20 combinations. I got help from the PF community because I originally only listed 13 combinations. But knowing what I know now I would have been at least able to show there should be 20 right off the bat.

But my prof is going to want an answer in the form of multi chooses and combinations, which some inclusion/exclusion (that's what he said in class).

So I hope that clears up why I'm so focused on understanding one method vs. the others suggested. Also apologies for the ambiguous question. I suppose when I wrote it down in my book, in the context of the class that day, to me it made more sense.
Okay, but how are you going to count these things?
 
  • #12
288
3
Okay, but how are you going to count these things?
Not totally sure I understand the question lol.

My method for the dice is going to be to find all the ways that 5 x's can add to twenty, then I suppose subtract all the ways that numbers greater than 6 can add to twenty, since a die has a max of 6. That's my problem-solving technique that I'm going to explore.

The course is called "Problem Solving" and it can be frustrating because I don't have the same math background as some students in the course. I feel like we're all trying to build a house and they showed up with nail guns and I got the loaner hammer. I'm putting in probably way too many hours with this course but find it fascinating.

So if that strategy doesn't work I'll tinker with something else, but its frustrating when you have a strategy but not the tools to implement it.

Like we had this locker riddle problem. In class I came up with a strategy that wound up being the correct one. No one else did. They were all arguing with me but I got the right strategy but I wasn't able to push through the math before the other students.
 
  • #13
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
Not totally sure I understand the question lol.

My method for the dice is going to be to find all the ways that 5 x's can add to twenty, then I suppose subtract all the ways that numbers greater than 6 can add to twenty, since a die has a max of 6. That's my problem-solving technique that I'm going to explore.

The course is called "Problem Solving" and it can be frustrating because I don't have the same math background as some students in the course. I feel like we're all trying to build a house and they showed up with nail guns and I got the loaner hammer. I'm putting in probably way too many hours with this course but find it fascinating.

So if that strategy doesn't work I'll tinker with something else, but its frustrating when you have a strategy but not the tools to implement it.

Like we had this locker riddle problem. In class I came up with a strategy that wound up being the correct one. No one else did. They were all arguing with me but I got the right strategy but I wasn't able to push through the math before the other students.
Okay, but I'd be looking for some answers! I feel like I gave you a massive hint in post #9, but you don't seem to have noticed!
 
  • #14
288
3
Okay, but I'd be looking for some answers! I feel like I gave you a massive hint in post #9, but you don't seem to have noticed!
I think I am starting to see. If I calculate the total number of ways to add to 18, but then subtract off the cases that can't happen on a die, like having zeros (or two bars next to each other) as well as having the bars too far apart, I think that should get me closer. Now to think about how to represent that...
 
  • #15
288
3
hmm, what if I consider two bars next to each other as one object?
 
  • #16
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
I think I am starting to see. If I calculate the total number of ways to add to 18, but then subtract off the cases that can't happen on a die, like having zeros (or two bars next to each other) as well as having the bars too far apart, I think that should get me closer. Now to think about how to represent that...
I don't know where this problem with the dice has come from. I would like to see you understand:

a) why there are 3 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 4.
b) why there are 6 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 5.

Use that to extrapolate to any number.

Your dice problem looks very different to me:

1) The dice have a limit of 6.
2) Your answer suggests the dice are indistiguishable (whereas, in the other problem you have definite numbers (##x_1, x_2, x_3##).

Is the reason you struggle on this course because you never stick to one question long enough to solve it?
 
  • #17
288
3
I don't know where this problem with the dice has come from. I would like to see you understand:

a) why there are 3 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 4.
b) why there are 6 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 5.

Use that to extrapolate to any number.

Your dice problem looks very different to me:

1) The dice have a limit of 6.
2) Your answer suggests the dice are indistiguishable (whereas, in the other problem you have definite numbers (##x_1, x_2, x_3##).

Is the reason you struggle on this course because you never stick to one question long enough to solve it?
That honestly may be the reason! I have glimpses of eureka moments with all the other open problems and don't want to not get it down. I'll take your advice and work this out first.
 
  • #18
288
3
That honestly may be the reason! I have glimpses of eureka moments with all the other open problems and don't want to not get it down. I'll take your advice and work this out first.
I don't know where this problem with the dice has come from. I would like to see you understand:

a) why there are 3 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 4.
b) why there are 6 ways to add three postive numbers (##x_1, x_2, x_3##) to get a total of 5.

Use that to extrapolate to any number.

Your dice problem looks very different to me:

1) The dice have a limit of 6.
2) Your answer suggests the dice are indistiguishable (whereas, in the other problem you have definite numbers (##x_1, x_2, x_3##).

Is the reason you struggle on this course because you never stick to one question long enough to solve it?
For a) It's 3C2, since you have x _ x _ x _ x which is saying 3 spaces to put 2 bars.

For b) It's 4C2, since you have x _ x _ x _ x _ x which is saying 4 spaces to put 2 bars.
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,506
5,992
For a) It's 3C2, since you have x _ x _ x _ x which is saying 3 spaces to put 2 bars.

For b) It's 4C2, since you have x _ x _ x _ x _ x which is saying 4 spaces to put 2 bars.
Yes, but why is it ##\binom42##?

It's not four spaces to put two bars. It's 5 spaces to put two bars in, but no two bars can be together.
 
  • #20
288
3
Yes, but why is it ##\binom42##?

It's not four spaces to put two bars. It's 5 spaces to put two bars in, but no two bars can be together.
Yes, because if the two bars are together that indicates a zero, which we can't have.

4C2 comes from 3 multichoose 2. Originally we have 3 objects (the x's) and we are distributing 5 numbers to them from the set {1, 2, 3, 4, 5} and repetition is allowed, so we can pull out x1 = 2, x2 = 2, and x3 = 1. We can also not give x1 or x2 anything, and have just x3 = 5. That is 3 multichoose 5.

But since they have to be positive then each x has to start with at least 1. So after we distribute 1 to each x, it's changing the problem to "how many ways can you add {1, and 2} to 2?" So now we have 2 objects to distribute to 3 x's, which is 3 multichoose 2 = 4C2 = 6.
 
  • Like
Likes PeroK
  • #21
288
3
Yes, because if the two bars are together that indicates a zero, which we can't have.

4C2 comes from 3 multichoose 2. Originally we have 3 objects (the x's) and we are distributing 5 numbers to them from the set {1, 2, 3, 4, 5} and repetition is allowed, so we can pull out x1 = 2, x2 = 2, and x3 = 1. We can also not give x1 or x2 anything, and have just x3 = 5. That is 3 multichoose 5.

But since they have to be positive then each x has to start with at least 1. So after we distribute 1 to each x, it's changing the problem to "how many ways can you add {1, and 2} to 2?" So now we have 2 objects to distribute to 3 x's, which is 3 multichoose 2 = 4C2 = 6.
You can also view it as the two bars being distributed among 5 spaces. So that is also 2 multichoose 5 which equals 6. I think there is more intuition in that method.
 
  • #22
tnich
Homework Helper
1,048
336
I am interested in your problem of combinations of 5 dice that sum to 18. If you want to start another thread on that, we can discuss it.
 

Related Threads on How many ways to count to 20

  • Last Post
Replies
4
Views
983
Replies
5
Views
1K
Replies
3
Views
378
Replies
4
Views
998
  • Last Post
Replies
17
Views
669
Replies
2
Views
728
  • Last Post
Replies
18
Views
740
  • Last Post
Replies
3
Views
372
Top