0

How many $5$-digit numbers can be formed from digits $0 ,1,....9$ such that no $2$ same digits are sit next to each other?

I tried to solve the problem but complement as following

There are
$$9 \cdot 10 \cdot 10 \cdot 10 \cdot 10$$
$5$-digit numbers.

Now I find ways to form $5$-digit number with $2$ same digits. $$9 \cdot 5C2 \cdot 9C3 \cdot 4!$$ "First choose $2$ places out of $5$, then fill them by $9$ ways and fill the other $3$ places by $9C3$ and finally permute them all."

Then the answer $= 9 \cdot 10 \cdot 10 \cdot 10 \cdot 10 - 9 \cdot 5C2 \cdot 9C3 \cdot 4!$

Is my work true? Is there a simpler way ?

Thank you for your help.

N. F. Taussig
  • 76,571
user373141
  • 2,503
  • 1
    @celtschk has come up with a simple solution. While it is possible to exclude those numbers with at least two consecutive digits that are equal, you have to account for those numbers with three, four, or five consecutive digits. You can do so using the [inclusion-Exclusion Principle], but it requires considerably more work, particularly since only the leading digit cannot equal zero. – N. F. Taussig Apr 14 '17 at 12:30

1 Answers1

5

The first digit cannot be a $0$, so you've got $9$ digits to choose from ($1$ to $9$). The second digit cannot be the same as the first, so again you've got $9$ digits to choose from (all but the one you chose for the first digit). The third digit cannot be the same as the second, so again there are $9$ choices. And so on. So you've got $9^5$ numbers fulfilling the condition.

celtschk
  • 43,384
  • But wouldn't it amount to inclusion of cases like 99999? – The Dead Legend Apr 14 '17 at 12:09
  • 2
    @UddeshyaSingh: No. After you've chosen the digit $9$ as first digit, I explicitly excluded that choice for the second digit (that's why you only have $9$ digits to choose from as second digit, not $10$). – celtschk Apr 14 '17 at 12:10