Count of $N$ digit numbers with no repeating neighbors

Question

How many $N$ digit numbers are there such that neighboring digits are distinct and first and last digits are distinct too.

For $2$ digits there are $9\cdot 9$ obviously.

For $3$ digits it's $9\cdot 8\cdot 8+9\cdot 1\cdot 9$.

Same logic I can apply for $4$ and $5$ digits but the number of terms grows and it becomes hard to keep track. So how to proceed?

Answer 1

First let's not exclude that the first digit takes value $0$.

(Excluding afterwards that the first digit takes value $0$ means that the outcome must be mupltiplied with $0.9$)

Let $A=\{0,1,2,3,4,5,6,7,8,9\}^N$

For $i=1,\dots,N-1$ let $A_i=\{d\in A\mid d_i=d_{i+1}\}$

Let $A_N=\{d\in A\mid d_N=d_1\}$.

To be found is then $|A-A_1\cup\dots\cup A_N|=10^N-|A_1\cup\dots\cup A_N|$

Here $|A_1\cup\cdots\cup A_N|$ can be found by inclusion/exclusion applying that $|A_{i_1}\cap\cdots\cap A_{i_k}|=10^{N-k}$ whenever $1\leq i_1<i_2<\cdots<i_k\leq N$ and $k<N$ together with $|A_1\cap\dots\cap A_N|=10$.

This leads to:$$\sum_{i=0}^{N-1}\binom{N}i(-1)^i10^{N-i}+(-1)^N10=\sum_{i=0}^{N}\binom{N}i(-1)^i10^{N-i}-(-1)^N+(-1)^N10=$$$$9^N+9(-1)^N$$

So the final outcome ($0$ excluded as first digid) is:$$\frac9{10}\left(9^N+9(-1)^N\right)$$

Answer 2

A start for you:

There are $9$ digits you can place in the "first" position. To the right you can place just $8$ (the ones that are different from the first position). Next to the right you can place just $8$ (the ones that are different from the second position). And so on. At position $n-2$ either you have the SAME digit as the first position (in which case you have $8$ possibilities for position $n-1$, or instead you have a DIFFERENT digit as the first position (in which case you have just $7$ possibilities for position $n-1$.

Answer 3

Since a leading zero apparently isn't allowed (except perhaps for a one-digit number), let's see. The initial exhaustively-counted results are:

$$ 10, 81, 648, 5913, 53136, 478305, 4304664, 38742057… $$

According to prime factorization and a bit of pattern finding, this corresponds to the following:

$$ \begin{align} 10 &= 9 + 1 \\ 81 &= 9 \times 9 \\ 648 &= 8 \times 9 \times 9 \\ 5913 &= (8 \times 9 + 1) \times 9 \times 9 \\ 53136 &= (9 \times 9 + 1) \times 8 \times 9 \times 9 \\ 478305 &= ((9 \times 9 + 1) \times 8 \times 9 + 1) \times 9 \times 9 \\ 4304664 &= ((9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 \times 9 \\ 38742057 &= (((9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 + 1) \times 9 \times 9 \end{align} $$

My guesses for the next values:

$$ (((9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 \times 9 \\ ((((9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 + 1) \times 9 \times 9 \\ ((((9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 \times 9 \\ (((((9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 9 \times 9 + 1) \times 8 \times 9 + 1) \times 9 \times 9 \\ \vdots $$

Note the two-stage pattern, repeating with yet another $ (9 \times 9 + 1) $ nested at the beginning:

1. $ (\cdots((9 \times 9 + 1) \times 9 \times 9 + 1) \cdots \times 8 \times 9 + 1) \times 9 \times 9 $
2. $ (\cdots((9 \times 9 + 1) \times 9 \times 9 + 1) \cdots \times 9 \times 9 + 1) \times 8 \times 9 \times 9 $