How many $5$-digit numbers are there, so that $0,1$ and $2$ are NOT included, $3,4$ and $5$ have to be included

I have the following question. How many $5$-digit numbers are there, so that the following conditions are satisfied:

• $0,1$ and $2$ are NOT included
• $3,4$ and $5$ have to be included

The list of possible numbers to choose from is $(3,4,5,6,7,8,9)$. As we know, $3,4$ and $5$ have to be included in every number, for example $33475$, $54339$ etc.

I tried to do this as follows:

For the $1.$ digit, I can choose $3,4$ or $5$. So, I basically have ${3 \choose 1}$ choices. For the $2.$ digit, I have $2$ numbers to choose from, for example $4$ or $5$ if $3$ is the 1. digit, $3$ or $5$ if $4$ is the 1. digit etc. So, that's ${2 \choose 1}$. For the $3.$ digit there is $1$ number to choose as per reasoning for choosing the $2.$ number. That's basically ${1 \choose 1}$. For the $4.$ and $5.$ digit, there are ${7 \choose 1}$ possibilities respectively, because any number from the list can be chosen.

At the end I get ${3 \choose 1} \cdot {2 \choose 1} \cdot {1 \choose 1} \cdot {7 \choose 1} \cdot {7 \choose 1} = 3 \cdot 2 \cdot 1 \cdot 7 \cdot 7 = 294$ possible numbers. Now, you can permute those choices between the digit places. There are $5$ digits, so it would be $5! = 120$ possible permutations. In the end I got $294 \cdot 120 = 35280$ numbers. However, the problem is that there are not 120 such permutations, because for some cases one number is counted multiple times.

I know from my class that the answer is $1830$. And I also got the hint from my professor to use the inclusion-exclusion principle. But with that I have problems to start.

So, could somebody help me either how to calculate this with the inclusion-exclusion principle OR with the way I tried to do this, i.e. how to NOT multiple count those numbers.

Solution 1:

The easiest is to apply Principle of Inclusion Exclusion:

Count of five digit numbers with digits $3$ - $9$ where at least one of $3, 4, 5$ are missing is

$3 \cdot 6^5 - 3 \cdot 5^5 + 4^5$

Now subtracting it from $7^5$ should give us the count of numbers where all three digits $(3, 4, 5)$ appear at least once. So the answer is,

$7^5 - (3 \cdot 6^5 - 3 \cdot 5^5 + 4^5) = 1830$

If you are working cases by case, there are $3$ cases.

$(i)$ three of five spaces are taken by $3, 4, 5$
$(ii)$ four of five spaces are taken by $3, 4, 5$
$(iii)$ all five spaces are taken by $3, 4, 5$

$(i)$ We choose three spaces and place $3, 4, 5$. Rest two spaces are taken by $6, 7, 8, 9$

So count of numbers $ ~ = \displaystyle {5 \choose 3} \cdot 3! \cdot 4^2$

$(ii)$ We choose four spaces and choose one from $3, 4, 5$ that appears twice. Remaining space is taken by $6, 7, 8, 9$

So count of numbers $ ~ = \displaystyle {5 \choose 4} \cdot 3 \cdot \frac{4!}{2!} \cdot 4$

$(iii)$ consists of one of $3, 4, 5$ appearing three times or two of them appearing two times.

So that leads to,

$ \displaystyle 3 \cdot \left[\frac{5!}{3!} + \frac{5!}{2! \cdot 2!}\right]$

Adding $(i), (ii), (iii)$ should give the same answer as we got using Principle of Inclusion Exclusion.