How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times?

Question

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times? The solution is supposed to be derived using Inclusion-Exclusion.

Here is my attempt at a solution:

Let $A_0$= sequences where there are two $0$'s that appear in the sequence.

...

$A_{9}$=sequences where there are two $9$'s that appear in the sequence.

I want the intersection of $A_0^{'}A_1^{'}...A_9^{'}$= $N-S_1+S_2$ because you can only have at most two digits who are used exactly two times each in a $5$ digit sequence.

$N=10^5$, $S_1=10\cdot \binom{5}{2}\cdot[9+9\cdot 8 \cdot 7]$, and $S_2=10 \cdot 9 \cdot \binom{5}{4} \cdot8$.

The $S_1$ term comes from selecting which of the ten digits to use twice, selecting which two places those two digits take, and then either having the same digit used three times for the other three places, or having different digits used for the other three digits.

The $S_2$ term comes from selecting which two digits are used twice, selecting where those four digits go, and then having eight choices for the remaining spot.

So my answer becomes $10^5 -10 \cdot \binom{5}{2} \cdot [9+9 \cdot 8 \cdot 7]+10 \cdot 9 \cdot \binom{5}{4} \cdot 8$.

Am I doing this correctly?

Answer 1

The structure of the analysis is the same as yours. We count the bad strings, where some digit appears exactly twice.

We first count the strings where say the digit $0$ appears exactly twice. Where the $0$'s are can be chosen in $\binom{5}{2}$ ways. For each of these ways, the remaining $3$ places can be filled in $9^3$ ways.

So our first estimate of the number of bad strings is $(10)\binom{5}{2}(9^3)$.

But we have double-counted, for example, the strings where $0$ and $1$ appear exactly twice. There are $\binom{5}{2}$ ways to choose where the $0$'s go, and for each there are $\binom{3}{2}$ ways to choose where the $1$'s go. The remaining spot can be filled in $8$ ways. Multiply by $\binom{10}{2}$ for the number of ways to choose the two digits that appear twice.

Putting things together, we find that the number of bad strings is $$(10)\binom{5}{2}(9^3)-\binom{10}{2}\binom{5}{2}\binom{3}{2}(8).\tag{1}$$

Finally, subtract (1) from $10^5$.

Answer 2

The partitions of $5$ showing the admissible multiplicities of occurring digits are $(1,1,1,1,1)$, $(3,1,1)$, $(4,1)$, and $(5)$.

There are $10\cdot9\cdot 8\cdot 7\cdot 6=30\,240$ numbers with five different digits.

There are $10\cdot{9\choose 2}=360$ ways to choose three digits whereby the first chosen digit will be used three times. You can arrange these digits in ${5!\over3!}=20$ ways, so that we get $7200$ numbers with multiplicities $(3,1,1)$.

There are $10\cdot9=90$ ways to choose two digits whereby the first chosen digit will be used four times. The second chosen digit can be placed in five different slots, so that we get $450$ numbers with multiplicities $(4,1)$.

There are $10$ ways to choose a single digit to be used five times.

In all there are $37\,900$ admissible numbers.

Answer 3

Suppose we ask about $N$ digit numbers including leading zeros where no digit appears two times.

The species of set partitions with no two-elements sets is $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ne 2, \ge 1}(\mathcal{Z})).$$

This yields the generating function

$${n\brace k}_{\ne 2} = \frac{(\exp(z)-z^2/2-1)^k}{k!}.$$

We get as the answer for the problem

$$\sum_{q=1}^N {10\choose q} {N\brace q}_{\ne 2} q!$$

which simplifies in terms of ordinary Stirling numbers of the second kind to

$$N! [z^N] \sum_{q=1}^N {10\choose q} (\exp(z)-z^2/2-1)^q \\ = N! [z^N] \sum_{q=1}^N {10\choose q} \sum_{p=0}^q {q\choose p} (\exp(z)-1)^{q-p} (-1)^p \frac{z^{2p}}{2^p} \\ = N! \sum_{q=1}^N {10\choose q} \sum_{p=0}^{\min(q,\lfloor N/2\rfloor)} {q\choose p} [z^{N-2p}] (\exp(z)-1)^{q-p} \frac{(-1)^p}{2^p} \\ = N! \sum_{q=1}^N {10\choose q} \sum_{p=0}^{\min(q,\lfloor N/2\rfloor)} {q\choose p} \frac{(-1)^p}{2^p} \frac{(q-p)!}{(N-2p)!} {N-2p\brace q-p}.$$

This yields the sequence

$$10, 90, 730, 5410, 37900, 264250, 1908910, 14322520, \\ 110305720, 875799550, 7203731050, 60866700940, 527138423380, \\ 4696469283970, 42797376850150, \ldots$$

Remark. Starting from the alternate species

$$\mathfrak{S}_{=10}(\mathfrak{P}_{\ne 2}(\mathcal{Z}))$$

we obtain the closed form

$$N! [z^N] (\exp(z)-z^2/2)^{10}.$$