# Combinatorics with repetition

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.

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

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.
• 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$ – ER H Oct 22 '16 at 12:50
• @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$.) – Brian M. Scott Oct 22 '16 at 12:54