combinations with repetitions allowed, order does not matter, n less than k

Question

A machine produces a $9$-digit code from the numbers $\{1,2,3,4,5,6\}$. So, $k=9$ and $n=6$. Repetition is allowed, so the machine could produce $111111112$. However, the order does not matter. So, the machine would consider $111111112$ the same as $211111111$ or $111121111$.

Thus, the number of possible combinations would not simply be $6^9$ as that would be double (or even more) counting certain sequences. How many combinations are there?

Answer 1

What you are looking for is the Stars and Bars method. This method is used to count things where order does not matter and repetition is allowed.

We are choosing $9$ digits from $\{1,2,3,4,5,6\}$

Let me explain how we can get to the answer.

For example, let's say we want to pick the combination $123456123$. This can be "arranged" as such:

$$••|••|••|•|•|•$$

We picked $2$ ones, $2$ twos, $2$ threes, and $1$ of the rest.

Let's look at another possibility: $111222456$ $$•••|•••| |•|•|•$$

We have three ones, three twos, and one $4$, $5$, and $6$.

Look at what these pictures are showing: we have $14$ symbols and we are choosing $5$ of them to be a bar. Or we could look at it as choosing $9$ of them to be a dot (star)

So the answer to our original question is $$\binom{14}{9} = \binom{14}{5} = 2002$$

Answer 2

Further to the stars and bars advice, you can justify that approach by considering a process for producing a sorted code (and since order doesn't matter, we can assume the code numbers are sorted).

Imagine that the machine has a status flag to say which digit to generate, from $1$ to $6$. At each step it can either generate a digit (unless $9$ have been generated) or move the status flag on to the next digit (unless it is already at $6$).

Starting with the status flag at $1$ and zero digits generated, we have $9+5$ actions to complete to end at $9$ digits generated and the status flag at $6$.

To generate $112222466$ for example, we would need the action sequence $gg{\uparrow}gggg{\uparrow}{\uparrow}g{\uparrow}{\uparrow}gg$, where $g$ generates a digit and ${\uparrow}$ increments the status flag. Then these $14$ actions will produce a different code - and any valid sorted code can be produced - by choosing when the status flag updates happen in the sequence of events. This produces the required $\binom{14}{5} = 2002$ options.