How many strings of five decimal digits contain exactly three distinct digits?

Here is my thought process so far:

There are 10 options for the first number, 9 for the second, and 8 for the third. According to this current structure, the fourth and fifth digits would have to be one or two of the three already selected digits in some order. If the first three digits were 1, 2, 3, then the possible permutations for the fourth and fifth spots are: 11, 22, 33, 12, 21, 13, 31, 23, and 32.

So the answer so far would be (10 x 9 x 8) x (9)

Therefore: Per three distinct digits, there are already 9 options for a string. Additionally, the fourth and fifth spots which contain 1 or more of the distinct digits for the first repeated occurrence don't have to be at the end. I thought that I should multiply the present answer by (5 choose 3) = 10 to account for this additional variation in order, but I can tell that there must be some number of strings which are counted twice by this method, so

(10 x 9 x 8) x (9) x (10) = 64800 is probably too great. Any suggestions? Thank you

• Hint: break it into two cases. The case where you have a number that has digits $\{a,b,c,c,c\}$ and the case where the digits are $\{a,b,b,c,c\}$ – Joe May 2 '18 at 22:59

Instead of thinking about the number of ways to place the digits (which gets quite complicated), think about it as a three step procedure:

1. How many ways are there to write a 5 digit number with 3 distinct characters?

2. How many ways can one choose three distinct characters to be placed into the forms from above.

3. Watch out for any duplication or overcounting.

There are two options (using Joe's suggestion in the comments):

• $\{a,b,c,c,c\}$. We can choose $3$ of the $5$ positions for the $c$'s, then there are two options for the $a$ and $b$ ($a$ first and then $b$ or the other way around). This gives $$2\binom{5}{3}=20$$ ways to write $a$, $b$, and $c$.

• $\{a,b,b,c,c\}$. We can choose $1$ of the $5$ positions for the $a$, and then $2$ of the remaining $4$ positions for the $b$'s. This gives $$5\binom{4}{2}=30$$ ways to write $a$, $b$, and $c$.

Now, there are $10\cdot 9\cdot 8=720$ ways to choose three digits for the positions $a$, $b$, and $c$. So, one might expect $$720\cdot (20+30)=36000$$ arrangements. The problem with this is that there is some overcounting since $abbcc$ and $accbb$ result in the same arrangement when the numbers in $b$ and $c$ are also flipped. This occurs for $a\leftrightarrow b$ in the first option and $b\leftrightarrow c$ in the second form. Therefore, we've overcounted by a factor of $2$ and there are $18000$ total arrangements. (Note that $720\cdot 30/2=10800$ matching @Green's approach).

• I believe the answer to 2. is 10 x 9 x 8 = 720 ways to choose the 3 distinct digits. But number 1. perplexes me... – mike May 2 '18 at 23:08
• @whatafeynman Yes, the answer to 2 is 720 (but we must be careful about double counting by "double switching") See the edits above. – Michael Burr May 2 '18 at 23:14
• Thank you very much! Between your answer, that of Joe, and that of Green, I think I have a much better understanding of the question. – mike May 2 '18 at 23:17

I think you're on the right track, but I wouldn't recommend fixing the first 3 spots to be distinct numbers as you do. For example, the number $11231$ satisfies the condition of being a 5-digit number with exactly $3$ different digits, but doesn't have the first $3$ digits distinct.

I noticed that you have $10 * 9 * 8 = 720$ ways to pick your first $3$ digits to use in order. Instead, I would suggest that you just find the total number of combinations of $3$ digits you could use in making your string, which is $10$ choose $3$, or $120$. Given this, the next step would be to split the problem into cases. As you seem to have noticed, you can either have $2$ of the digits be used twice, or $1$ of the digits be used thrice.

Let's consider case $1$, which is that you have $2$ digits used twice. There's $3$ ways to choose which of the $3$ digits to use twice, and then a total of $\frac{5!}{2! * 2!} = 30$ ways to arrange the digits afterwards, giving us a total of $120 * 3 * 30 = 10800$ possible arrangements.

Now, try to calculate the other case by yourself and see if you're able to arrive at the answer.

That's an obscene amount of double counting.

First you got three digits (in you example $123$) and you figured there were $9*8*7$ ways to get these. Those coming up with $123$ and $312$ etc. are different results. Then you multiplied by $9$ for the last to digits. But then you allowed for scrambling them all up again. So that $12312$ and $12321$ each can scramble to the same results. As can $31212$ and $31221$. The we I see it you counted the number $31212$ $12$ times!

Better: There are ${10 \choose 3}$ choices of the three distinct $3$ digits. Of those distinct $3$ digits there are two ways to have repeats: You may have $1$ digit repeated three times (and there are ${3 \choose 1}=3$ way of picking it); or you may have $2$ digits each repeated twice. And there are $({3\choose 2}=3$ ways of picking those.

If you have one digit repeated three times you have $5*4$ spots to place the two distinct digits. If you have two digits repeated twice. You have $5$ options to place the distinct digit and $4\choose 2$ options to place the first pair of repeated digits.

So there are ${10\choose 3}({3 \choose 1}5*4 + {3\choose 2}5*{4\choose 2})=$

$\frac {10!}{7!3!}(60 + 90) = \frac {10*9*8}6(150)= 10*9*8*25=18,000$

Let us define $S(n,d)$ as the number of different strings of $n$ characters containing $k$ distinct characters (from a pool of $u$ possible characters). Then in general there are two ways to form a string in $S(n,d)$:

• add an already-used character to a string in $S(n{-}1,d)$ - with $d$ options
• add a novel character to a string in $S(n{-}1,d{-}1)$ - with $u-(d{-}1)$ options

This gives us that $S(n,d) = d\cdot S(n{-}1,d) + (u-(d{-}1))\cdot S(n{-}1,d{-}1)$ which here with $u=10$ is $S(n,d) = d\cdot S(n{-}1,d) + (11-d)\cdot S(n{-}1,d{-}1)$

Then we just need to frame this with $S(0,0)=1$ and otherwise $S(n,0)=S(0,d)=0$, and we can calculate a table of results:

\begin{array}{l|rr} d \ \backslash \ n\! & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 10 & 10 & 10 & 10 & 10 \\ 2 & 0 & 0 & 90 & 270 & 630 & 1350 \\ 3 & 0 & 0 & 0 & 720 & 4320 & \color{red}{18000} \\ 4 & 0 & 0 & 0 & 0 & 5040 & 50400 \\ 5 & 0 & 0 & 0 & 0 & 0 & 30240 \\ \end{array}

If you just want the answer, there's nothing wrong with computing it:

\$ python
>>> import itertools
>>> sum(len(set(x))==3 for x in itertools.product(range(10),repeat=5))
18000

• If this is, in fact, the correct answer, then I can use it to be certain that all my attempts so far are incorrect! So, thank you! Unfortunately, I am hoping to develop an understanding of how to find this value by hand. – mike May 2 '18 at 23:03