Order does not matter, repetition allowed

Given we have an unlimited supply of $3$ types of fruit:

• A: apples
• O: oranges
• P: peaches

How many ways are there to select $4$ pieces of fruit, if the order of selection does not matter, only the type of fruit / not the individual piece matters?

We could consider a box which can store 4 pieces of fruit, the box can have 3 compartments, each can store one of 3 types of fruit. Compartments are divided by 2 movable dividers that can be shifted depending on how many types of each fruit we want to store. For example:

• 2 apples, 1 orange, 1 peach: $\boxed{AA|O|P}$
• 4 oranges: $\boxed{|OOOO|}$
• 1 apple, 3 peaches: $\boxed{A||PPP}$
• 4 apples: $\boxed{AAAA||}$

So if we have to choose $k$ objects from a set of $n$ objects, with repetition allowed, we need a box with $k$ places for the chosen object and $n-1$ places for the dividers dividing the box into $n$ compartments.

Given any random box: $\boxed{\ast \ast |\ast \ast \ast |\ast ||}$, we have $k+n-1$ places.

The number of ways we can choose our $k$ objects is the number of ways we can distribute the dividers in the box. Out of the $k+n-1$ places, we hace to choose $n-1$ for the dividers. The number of ways of doing this is:

$$\boxed{\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)}=\left(\begin{array}{c}k+n-1\\ k\end{array}\right)$$

This formula should be remembered!

Going back to the example, we find that:

$$\begin{array}{rl}\left(\begin{array}{c}4+3-1\\ 3-1\end{array}\right)& =\left(\begin{array}{c}6\\ 2\end{array}\right)\\ & =\frac{6!}{4!\cdot 2!}\\ & =\frac{6\times 5}{1\times 2}\\ & =15\text{ ways}\end{array}$$