Understanding combinations with repetitions

[Alvin Seville]

Hello everyone! I started learning probability theory from this article. And I haven't understood combinations with repetitions. Why not simply calculate it as n^k/k!, where n - entire count of objects and k - is chosen objects? I want to divide permutations with repetitions number by k factorial. Where and why I've mistaken because the result of this calculation seems to be wrong.

 

[Dr.Peterson]

Hello everyone! I started learning probability theory from this article. And I haven't understood combinations with repetitions. Why not simply calculate it as n^k/k!, where n - entire count of objects and k - is chosen objects? I want to divide permutations with repetitions number by k factorial. Where and why I've mistaken because the result of this calculation seems to be wrong.

Please explain WHY you think [MATH]\frac{n^k}{k!}[/MATH] should be correct. Perhaps work through a small example to show why you would do that division, and you may discover why it doesn't do what you think.

The method they are using is commonly called "stars and bars", due to another way to explain it. You can search for that term to see additional explanations. But the reason the technique is needed is precisely that this problem is difficult to envision otherwise. I can only tell you why your approach doesn't work when I know how you are looking at it.

 

[JeffM]

In line with Dr. Peterson's post, let's suppose that there are two available flavors of ice cream, vanilla and chocolate, and we want to know how many different kinds of double scoop ice cream cones are available without regard to order.

We could have three combinations: vv, vc or cv, or cc, which is three. Does your formula work?

[MATH]n = 2 = k \implies \dfrac{n^k}{k!} = \dfrac{2^2}{2} = 2 \ne 3.[/MATH]
Let's try three flavors and two scoops by adding strawberry to the selection.

cs or sc, cv or vc, vs or sv, cc, vv, ss: 6 possibilities.

What does your formula say when n = 3 and k = 2.

[MATH]\dfrac{3^2}{2!} = \dfrac{9}{2} = 4.5 \ne 6.[/MATH]
Thus, your formula is wrong.

 

[pka]

Hello everyone! I started learning probability theory from this article. And I haven't understood combinations with repetitions. Why not simply calculate it as n^k/k!, where n - entire count of objects and k - is chosen objects? I want to divide permutations with repetitions number by k factorial. Where and why I've mistaken because the result of this calculation seems to be wrong.

Dear fellow, one can not just jump into a subject that has a three hundred year history of having been studied.
That area is called counting theory. Simple question: how many ways can the letters of the word SOUTHERN be arranged?
The answer is as you seem to understand $8!=40320$ ways. There are eight distinct letters in that word.
What is different here: how many ways can the letters of the word MISSISSIPPI be arranged?
Well in addition to the fact that there are eleven letters, there are multiple repeated letters.
There are four $S$'s; four $I$'s; and two $P$'s which cannot be told apart.
However putting subscripts on repeated letters, $\bf{MI_1S_1S_2I_2S_3S_4I_3P_1P_2I_4}$ , solves the problem of having identical letters.
So there are $11!=39916800$ ways to rearrange that subscripted string.
Now the string $\bf{S_1S_2S_3S_4}$ can be rearranged in $4!=24$ ways.
So if we drop the subscripts from the $S's$ we need to remove 24 of each of the $11!=39916800$.
Thus repeating the above argument the number of ways to rearrange the letters of MISSISSIPI is $\dfrac{11!}{4!\cdot4!\cdot2!\cdot}$
Now can you answer this: How many ways to rearrange the letters of TENNESSEE?

 

[Dr.Peterson]

@Alvin Seville: Of course, pka's example is a different kind of problem than yours (permutations, not combinations, and of all the letters, not just some). But I'm guessing that you applied similar thinking to your problem, with a wrong assumption that the two problems are more alike than they are.

Let's take JeffM's example of 2 scoops from 3 flavors, V, C, S.

Your numerator, 3^2 = 9 counts the number of ways to select 2 scoops, where order counts: VV, VC, VS, CV, CC, CS, SV, SC, SS.

You divided by 2!, which is the number of ways to arrange two different items, hoping to eliminate the order in the cases VC=CV, VS=SV, and CS=SC.

But the cases where the two selections are the same, there is only one arrangement: VV, CC, SS. So you can't divide that part of the count by 2.

Is that more or less what your thinking was?