Counting Number of Possibilities using Inclusion-Exclusion

Question

I have been tasked with answering the following combinatorics problem for a homework assignment:

Consider the set of all six digit numbers that don’t begin with 0. How many of these have at least one 0, at least one 1, and at least one 2?

The professor hinted that we use inclusion-exclusion to solve it, but I am not really seeing to accomplish this. I have tried writing down some patterns and then finding rearrangements of them within the rules, but I am not arriving at the correct answer of 59790 (I wrote a program to count the size of the set). Given that this is homework I would prefer some guidance and not a full solution.

Thanks!

Answer 1

Outline: There are two cases, (i) first digit is $1$ or $2$; (ii) first digit is $3$ to $9$.

We count (i) and (ii) and add.

We outline how to count (ii), because (i) is easier.

There are $7$ choices for first digit. We count the number that have first digit $3$, and multiply the answer by $7$.

So we want to count the strings of $5$ digits that have at least one $0$, at least one $1$, and at least one $2$. There are $10^5$ strings of length $5$. We count the bad ones, the ones missing at least one of $0$, $1$, $2$.

There are $9^5$ missing $0$, the same number missing $1$, and the same number missing $2$. Add. We get $3\cdot 9^5$. But we have double-counted the ones missing $2$ of our target numbers. So we add back $3\cdot 8^5$. But we have added back too much. It's almost over.

Answer 2

Denote the set of numbers that do not contain a $0$ by $A$

Denote the set of numbers that do not contain a $1$ by $B$

Denote the set of numbers that do not contain a $2$ by $C$

Now start hunting for $|A\cup B\cup C|$ with inclusion/exclusion:

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$ These cardinalities are not quite difficult to find. E.g. in the case of $|B\cap C|$ you have $7$ choices for the first digit ($0$, $1$ and $2$ are excluded) and $8$ for the others ($1$ and $2$ are excluded) leading to $7.8^5$ possibilities.

You are looking for: $|X|-|A\cup B\cup C|$ where $X$ denotes the set of all numbers.