Choose 6 pieces of candy from three flavors

[RChristenk]

Homework Statement

You walk into a candy store and have enough money for 6 pieces of candy. The store has chocolate (C), gummies (G), and Haribo sugar-free gummi-bears, which are horrible (H). How many different selections can you make?

Relevant Equations

Elementary combinatorics

I saw this question from here: https://www.cs.sfu.ca/~ggbaker/zju/math/perm-comb-more.html (under Combinations with Repetitions).

I thought the answer would be obvious: $3\cdot3\cdot3\cdot3\cdot3\cdot3=729$

But the course notes give the answer as $28$, and it says this is obvious because we just have to decide where to put the dividers. As you can tell, I have absolutely no idea what it is talking about and don't feel my answer is wrong. What's going on here?

 

[anuttarasammyak]

Your idea of 6 differnt cases
GCCCCC
CGCCCC
CCGCCC
CCCGCC
CCCCGC
CCCCCG
are counted one and let us name it C5G1H0.

You can count the cases :
C6G0H0
C5G1H0
C5G0H1
C4G2H0
C4G1H1
C4G0H2
C3G3H0 and so on.

 

[FactChecker]

You can count the cases :
C6G0H0
C5G1H0
C5G0H1
C4G2H0
C4G1H1
C4G0H2
C3G3H0 and so on.

Good. And to relate that to the section dividers mentioned in the link answer:
C6G0H0 is CCCCCC | |
C5G1H0 is CCCCC|G|
C5G0H1 is CCCCC||H
C4G2H0 is CCCC|GG|
C4G1H1 is CCCC|G|H
C4G0H2 is CCCC||HH
C3G3H0 is CCC|GGG| and so on.
So that is why the answer can be determined by counting the number of positions to place the section dividers, giving C(8,2).

 

[Hill]

Homework Statement: You walk into a candy store and have enough money for 6 pieces of candy. The store has chocolate (C), gummies (G), and Haribo sugar-free gummi-bears, which are horrible (H). How many different selections can you make?
Relevant Equations: Elementary combinatorics

I saw this question from here: https://www.cs.sfu.ca/~ggbaker/zju/math/perm-comb-more.html (under Combinations with Repetitions).

I thought the answer would be obvious: $3\cdot3\cdot3\cdot3\cdot3\cdot3=729$

But the course notes give the answer as $28$, and it says this is obvious because we just have to decide where to put the dividers. As you can tell, I have absolutely no idea what it is talking about and don't feel my answer is wrong. What's going on here?

You need to choose three numbers, each between 0 and 6, so that their sum equals 6. IOW, you need to choose two numbers between 0 and 6 so that their sum is not greater than 6. Surely you don't have 729 ways to do this.

However, it is not clear to me from the Statement that you have to buy 6 pieces of candy rather than up to 6, although their answer, 28, indicates so.

 

[FactChecker]

However, it is not clear to me from the Statement that you have to buy 6 pieces of candy rather than up to 6, although their answer, 28, indicates so.

The problem statement in the link is a little careless. There are a few things that are not clear about the problem statement and are only indicated by the answer given in the link.

 

[WWGD]

As others have said. I guess they're just assuming the individual pieces of candy of the same type are indistinguishable. So, if say, the triplet H1, H2, H3 is considered the same as any permutation of the triplet. Same for any pair, or singleton, i.e H1, H2 is the same as H2,H1, etc.
Like Fact Checker wrote, Stars and Bars formular is
(n+k-1)C(k-1) (" n+k-1 Choose k-1"), giving you 8C2.
Edit: May have been a good idea for author of book to specify that candies are undistinguishable, even if it's somewhat obvious.

 

[PeroK]

As others have said. I guess they're just assuming the individual pieces of candy of the same type are indistinguishable. So, if say, the triplet H1, H2, H3 is considered the same as any permutation of the triplet. Same for any pair, or singleton, i.e H1, H2 is the same as H2,H1, etc.
Like Fact Checker wrote, Stars and Bars formular is
(n+k-1)C(k-1) (" n+k-1 Choose k-1"), giving you 8C2.
Edit: May have been a good idea for author of book to specify that candies are undistinguishable, even if it's somewhat obvious.

How would you know how many different items there are of each type? There might be 500 individual chocolate candies. Although some people might not want one with a crinkled wrapper.

 

[RChristenk]

I don't get it, the question says you can purchase 6 pieces of candy. But how come using dividers to separate the three types of candy ends up as counting 8 slots, or essentially 8 pieces of candy? This makes absolutely no intuitive sense to me. Also how is this equation $C(n+r-1,r)$ derived? I don't understand it as it is. Thanks.

 

[PeroK]

I don't get it, the question says you can purchase 6 pieces of candy. But how come using dividers to separate the three types of candy ends up as counting 8 slots, or essentially 8 pieces of candy? This makes absolutely no intuitive sense to me.

It's actually a technique to transform the problem to a different from in order to make it easier to solve. For this to work, you need to check that the two solutions sets can be put into a one-to-one correspondence.

 

[WWGD]

How would you know how many different items there are of each type? There might be 500 individual chocolate candies. Although some people might not want one with a crinkled wrapper.

That's exactly my point.
You're finding the number of non-negative solutions to
$x_1+x_2+ x_3=6$
Where $x_i$ is the number of pieces of candy of type i=1,2,3 . Gummy bears, etc.

Which, I guess is assumed, there are at least 6 of each type , to allow for triplets where $x_i=6; x_j=0, j\neq i$.

 

[WWGD]

I don't get it, the question says you can purchase 6 pieces of candy. But how come using dividers to separate the three types of candy ends up as counting 8 slots, or essentially 8 pieces of candy? This makes absolutely no intuitive sense to me. Also how is this equation $C(n+r-1,r)$ derived? I don't understand it as it is. Thanks.

Edit:Please check the Wiki entry on Stars and Bars. Get back to us.
Basically, each arrangement with dividers corresponds to a solution . Let $D_j$be the ith divider; $i=1,2$same for $C_i; i=1,2,..6$ being the 3 types of candy.
Sorry, need to head out now, will return ASAP. Meantime, try to see why/how each arrangement of candies and dividers represents a solution.
Just consider,
D1D2C1C2C3C4C5C6
Represents the arrangement were all candies are of type 3

 

[FactChecker]

I don't get it, the question says you can purchase 6 pieces of candy. But how come using dividers to separate the three types of candy ends up as counting 8 slots, or essentially 8 pieces of candy? This makes absolutely no intuitive sense to me. Also how is this equation $C(n+r-1,r)$ derived? I don't understand it as it is. Thanks.

Did you see my post #3? I tried to relate @anuttarasammyak 's post #2 to the dividers. Since order doesn't count, you can reorder them so that all the Cs are first, the Ns are next, and the Hs are last. Then the numbers of each type are determined simply by the position of the two dividers, call them C_to_N and N_to_H. Counting the ends of the 6, that gives 8 places to put those two dividers. Thus, C(8,2).

P.S. There are some subtleties about why the order of the dividers does not count if I label them C_to_N and N_to_H and insist that C_to_N is always first. That fact that I am only counting the cases where C_to_N is first avoids the double counting that would occur if I allowed N_to_H to be first.

 

[haruspex]

I thought the answer would be obvious: $3\cdot3\cdot3\cdot3\cdot3\cdot3=729$

That's wrong because the order in which you make your selections doesn't matter. Selecting three C then two G then another C just means you ended up with four C and two G. You have counted many ways of achieving the same end.

Wrt the divider trick, suppose you were to make your selection according to this procedure:

• lay out eight coins in a row, heads up
• choose two coins to flip over
• for each head before the first tail, choose a C; for each head before the next tail choose a G; for the remaining heads choose an H.

Clearly each choice of two coins leads to one, and only one, valid selection. You can reverse the process, starting with a selection and expressing it as a line of coins with two showing tails. Again, each selection leads to only one such line.
Therefore the number of coin arrangements equals the number of selections.