How many numbers of $10$ digits that have at least $5$ different digits are there?

Question

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero.

The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are $4^{10}$. The numbers that can use any $4$ digits are ${10\choose 4}\cdot 4^{10}$

I'm saying "they can use," which does not mean that use; however this is very advantageous for this problem, for those who "can use" includes four digits using $4$ digits, which use $3$ to $2$ and using those who only use one.

So answering the question of the problem, the answer is:

"All ten-digit numbers except those who can only use four digits" \begin{align} &= 10^{10} - {10\choose 4} \cdot 4^{10}\\ &= 10^{10} - 210 \cdot 4^{10} \end{align} There is no reason to believe that the figures have some asymmetric distribution, so it is obvious that for all these numbers, the tenth start with zero. Since starting with zero are not exactly ten-digit numbers, we discard it.

The solution is: \begin{align} \tfrac 9{10} (10^{10} - 210 \cdot 4^{10})&= 9(10^9 - 21 \cdot 4^{10})\\ &= 8,801,819,136 \end{align} But I'm not sure this reasoning is correct.

Answer 1

This answer is a slightly different variation of the theme which affirms the result of @MarkoRiedel.

Here we use exponential generating functions to count the number of configurations of labelled objects and apply the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series.

If we are looking for the number of strings of length $10$ consisting of $4$ different objects, whereby

• each object may occur zero or more times, we calculate \begin{align*} 10![x^{10}]e^{4x} \end{align*}

• each object occurs at least once, we remove $x^0$ from the generating function $e^x$ and calculate \begin{align*} 10^4 \end{align*}

• each object occurs at most three times, we take the initial four summands from the series representation of $e^x$ and calculate \begin{align*} 10![x^{10}]\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^4 \end{align*}

We calculate the wanted number of $10$-digit numbers containing at least $5$ different digits by calculating the complement. We start with calculating the number of all $10$-digit numbers. From this number we subtract the $10$-digit numbers which contain exactly $j$ different digits, $j=1,\ldots,4$.

The number of all $10$-digit numbers are those starting with $1,\ldots,9$ followed by $9$ digits from $\{0,\ldots,9\}$. We obtain \begin{align*} 9\cdot 10^9 \end{align*} different numbers. Now we calculate the $10$-digit numbers which contain exactly four different digits. If we consider four different digits, the number is \begin{align*} 10^4 \end{align*} Since we have to choose four digits out of $\{0,\ldots,9\}$, there are $\binom{10}{4}$ different possibilities giving a total of \begin{align*} \binom{10}{4}10^4 \end{align*} From this number we have to subtract the number of strings which start with $0$. We can describe these strings as those which start with $0$ followed by zero or more occurrences of $0$ and one or more occurrences of the other three digits. Precisely nine digits have to follow the leading zero. We obtain so \begin{align*} 9![x^9]e^x(e^x-1)^3 \end{align*} Note the factor $e^x$ reflects the fact that $0$ may occur zero or more times after the leading $0$ while the other three digits have to occur at least once. Since there are $\binom{9}{3}$ different possibilities for choosing the three digits different from $0$ we conclude the number containing precisely four different digits are \begin{align*} \binom{10}{4}10^4-\binom{9}{3}9![x^9]e^x(e^x-1)^3 \end{align*}

$$ $$

Since we have to subtract from $9\cdot 10^{9}$ all numbers containing precisely four, three, two and one different digits, we finally obtain

\begin{align*} &9\cdot10^9-\binom{10}{4}10^4+\binom{9}{3}9![x^9]e^x(e^x-1)^3\\ &\quad\qquad-\binom{10}{3}10^3+\binom{9}{2}9![x^9]e^x(e^x-1)^2\\ &\quad\qquad-\binom{10}{2}10^2+\binom{9}{1}9![x^9]e^x(e^x-1)^1\\ &\quad\qquad-\binom{10}{1}10^1+\binom{9}{0}9![x^9]e^x\\ &=9\cdot10^9-210\cdot818520+84\cdot204630\\ &\qquad\qquad-120\cdot55980+36\cdot18660\\ &\qquad\qquad-45\cdot1022+9\cdot511\\ &\qquad\qquad-10\cdot1+1\cdot1\\ &=8839212480 \end{align*}

Answer 2

With these kinds of problems it can be useful to employ Stirling numbers of the second kind which encapsulate inclusion-exclusion. The count then becomes quite simple.

Suppose we first count $n$-digit numbers with one, two, three and four different digits where we include those that start with one or more zeroes. This is given by

$$\sum_{q=1}^4 {10\choose q} {n\brace q} \times q!$$

Now subtract out those numbers that start with zero where zero does not occur a second time having at most four different digits. This is

$$\sum_{q=1}^4 {9\choose q-1} {n-1\brace q-1} \times (q-1)!$$

Finally subtract out those starting with zero where zero occurs a second time or more which yields

$$\sum_{q=1}^4 {9\choose q-1} {n-1\brace q} \times q!$$

The final answer then becomes

$$9\times 10^{n-1} - \left(\sum_{q=1}^4 {10\choose q} {n\brace q} \times q! - \sum_{q=1}^4 {9\choose q-1} {n-1\brace q-1} \times (q-1)! \\ - \sum_{q=1}^4 {9\choose q-1} {n-1\brace q} \times q! \right).$$

This formula is implemented in the following Maple code:

with(combinat);

Q :=
proc(n)
    local res;

    res :=
    add(binomial(10,q)*stirling2(n, q)*q!, q=1..4)
    - add(binomial(9,q-1)*stirling2(n-1, q-1)*(q-1)!, q=1..4)
    - add(binomial(9,q-1)*stirling2(n-1, q)*q!, q=1..4);

    9*10^(n-1) - res;
end;

This yields the sequence (starting at $n=5$) $$27216, 544320, 7212240, 81648000, 862774416, 8839212480, \\ 89320326480, 897169996800, 8988342579216, 89952351128640, \\ 899806333018320, \ldots$$

In particular the answer for $n=10$ is

$$8839212480.$$

The first few values may be verified by the following Perl script which does total enumeration.

#! /usr/bin/perl -w
#


MAIN: {
    my $mx = shift || 5;


    for(my $n=5; $n <= $mx; $n++){
        my $res = 0;

        for(my $ind = 10 ** ($n-1); $ind < 10 ** $n; $ind++){
            my $val = $ind, %d = ();

            while($val > 0){
                $d{$val % 10}++;
                $val = ($val - ($val % 10))/10;
            }

            $res++ if scalar(keys(%d)) >= 5;
        }

        printf "%02d $res\n", $n, $res;
    }
}

Remark. It would appear that nothing is gained by working with the complement of the problem. We can use the same method as above and enumerate numbers with five, six, seven etc. up to ten different digits. The following Maple routine does this.

with(combinat);
Q2 :=
proc(n)
    add(binomial(10,q)*stirling2(n, q)*q!, q=5..10)
    - add(binomial(9,q-1)*stirling2(n-1, q-1)*(q-1)!, q=5..10)
    - add(binomial(9,q-1)*stirling2(n-1, q)*q!, q=5..10);
end;

Closed form. We can find a closed form for this sum.

Recall the species for set partitions which is $$\mathfrak{P}(\mathcal{U} \mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which gives the generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$

This yields $${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$

We thus obtain for the first sum term (observe that we have $n\ge 5$ in the entire calculation)

$$\sum_{q=5}^{10} {10\choose q} {n\brace q} \times q! = n! [z^n] \sum_{q=5}^{10} {10\choose q} (\exp(z)-1)^q \\ = n! [z^n] \sum_{q=5}^{10} {10\choose q} \sum_{p=0}^q {q\choose p} (-1)^{q-p} \exp(pz) \\ = n! [z^n] \sum_{p=0}^{10} \exp(pz) \sum_{q=\max(5,p)}^{10} {10\choose q} {q\choose p} (-1)^{q-p} \\ = \sum_{p=0}^{10} p^n \sum_{q=\max(5,p)}^{10} {10\choose q} {q\choose p} (-1)^{q-p}.$$

This yields $$10^n - 210\times 4^n + 720 \times 3^n - 945 \times 2^n + 560.$$

Using the same procedure we get for the second term

$$\sum_{p=0}^{9} p^{n-1} \sum_{q=\max(4,p)}^{9} {9\choose q} {q\choose p} (-1)^{q-p}.$$

This yields

$$9^{n-1} - 84\times 3^{n-1} + 216\times 2^{n-1} - 189.$$

We finally have for the third piece

$$\sum_{p=0}^{10} p^{n-1} \sum_{q=\max(5,p)}^{10} {9\choose q-1} {q\choose p} (-1)^{q-p}.$$

This yields

$$10^{n-1} - 9^{n-1} - 84\times 4^{n-1} + 300\times 3^{n-1} - 405\times 2^{n-1} + 245.$$

Collecting everything we finally have the closed form

$$9\times 10^{n-1} - 189\times 4^n + 648\times 3^n - 1701\times 2^{n-1} + 504.$$