2
$\begingroup$

I'm having a hard time with combinatorics with repetition.

Say we have the set $A = \{1,2,3,4,5,6\}$ and we are going to choose $3$ items from the set $A$ with $6$ items in.

So my intuitive understanding of this is that you can divide the set $A$ into $3$ different bins and to do so we need to have $2$ "walls" to create $3$ bins: like $xx\mid xxx\mid x$, so we could add $2$ extra items in the set so we have $6 + 2$ items to choose from and we always want to use $2$ of those as "walls"

So now the question is about in how many places we could place those two walls and we get $\binom{6 + 2}{2} = \binom82$.

But the theorem says that :

The number of unordered selections, with repetition, of $r$ objects from a set of $n$ objects is $\binom{n + r - 1}{r}$

In this case that would give us $n=6, r=3 \implies \binom{6 +3-1}{3} = \binom83$ which is not the same as $\binom82$.

My intuitive reasoning is obviously wrong but I can’t understand exactly where my mistake is.

$\endgroup$
  • $\begingroup$ You have to use \{ and \} to get the curly braces to show up.. $\endgroup$ – Brian M. Scott Oct 22 '16 at 12:05
3
$\begingroup$

You’re not dividing $A$ into $3$ different bins. You should instead think of the elements of $A$ as the bins, and you’re going to put $3$ tokens into those $6$ bins. Putting all $3$ tokens into Bin $1$ means selecting $3$ $1$s for your multiset of $3$ things. Putting $2$ tokens into Bin $3$ and $1$ into Bin $5$ means selecting $2$ $3$s and $1$ $5$ for your multiset of $3$ things. Thus, you have $5$ walls, not $2$, and $3$ tokens, so you have $5+3=8$ objects to arrange, and there are $\binom83=\binom85$ possible arrangements. In this example, as you say, $n=6$ and $r=3$, and sure enough,

$$\binom{n+r-1}r=\binom{6+3-1}3=\binom83\;.$$

You should thing of the upper number as $(n-1)+r$: there are $n-1$ walls and $r$ objects being placed between them.

$\endgroup$
  • $\begingroup$ Hey Brian! thanks for your fast answer. So I got it completely wrong. It's the set A that are the bins and to create those we need 5 walls as you say! and how many things we are choosing is how many tokens we should put in each bin. Okej so this is starting to make a bit more sense now. $\endgroup$ – ER H Oct 22 '16 at 12:44
  • $\begingroup$ So a shorter example: $A = \{1,2,3\}$ and we should choose $2$, first we need $2$ dividers to create $3$ bins and now we are going to put two tokens into those bins : bin 1: xx , x , x, 0 bin 2: 0 , x , 0, 0 bin 3: 0 , 0 , x, 0 And we have $4$ unique ways to put the tokens and that is from $n=2, r = 3 \implies \binom{2 + 3 - 1}{3} = \binom{4}{3} = 4$ $\endgroup$ – ER H Oct 22 '16 at 12:50
  • $\begingroup$ @ERH: You’re welcome! Yours is a very common mistake when people first encounter this kind of problem; the right way of looking at it somehow feels ‘backwards’ at first glance, because it’s natural to think of the elements of $A$ as the objects being distributed. That’s why I like to introduce the tokens when I explain it, so that we can distribute the right things. \\ I’m not following your notation in the second comment. You should have $\binom{3+2-1}2=\binom42=6$ outcomes: there are $2$ dividers and $2$ tokens. (You get the outcomes $11,12,13,22,23$, and $33$.) $\endgroup$ – Brian M. Scott Oct 22 '16 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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