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

Question

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 \times 9 \times 8) \times (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 \times 9 \times 8) \times (9) \times (10) = 64800$ is probably too great. Any suggestions? Thank you

Answer 1

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).

Answer 2

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

Answer 3

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.

Answer 4

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$

Answer 5

For a spreadsheet-style solution:

Let us define $S(n,d)$ as the number of different strings of $n$ characters containing $d$ 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}

Answer 6

For a shortcut approach , try to use exponential generating functions.. It is wanted that we have a string of lenght $5$ and only contain $3$ distinct digits such as $xxyxz$ or $xyyzy$ . We can choose these $3$ distinct digits form the set of $\{0,1,2,...,8,9\}$ by $C(10,3)=120$ ways.Now , it is times to arrange these $3$ distinct digits in the string , realize that each digit must appear at least once. Then ,the exponential generating function for each digits is $(e^x -1)=x+ \frac{x^2}{2!}+\frac{x^3}{3!}+..$

We know that because of each digits must appear at least once , then each digits can appear at most thrice.Hence , find the coefficient of $x^5$ in the expansion of $$\bigg(x+ \frac{x^2}{2!}+\frac{x^3}{3!}\bigg)^3$$

and multiply it by $5!$ or just find the coefficient of $\frac{x^5}{5!}$ in given expansion.

We see that , it is $5! \times \frac{5}{4}=150$

Then , the answer is $$120 \times 150 = 18,000$$