Number of $9-$digit numbers, all digits are different and nonzero and having no consecutive digits in consecutive positions

The first step of any problem in enumerative combinatorics is to compute the first few cases, then look the sequence up on OEIS. If we do that here, we find A002464:

Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

There is no particularly nice formula for $A_n$, which dashes our hopes of finding a particularly nice solution.

Your approach of finding $A_n$ in terms of $A_{n-1}$ and $B_{n-1}$ seems like it might possibly lead to the recurrence $$A_n = (n+1)A_{n-1} - (n-2)A_{n-2} - (n-5)A_{n-3} + (n-3) A_{n-4}$$ after a lot more work. But the original source for this recurrence finds it algebraically, so it's not clear if a combinatorial interpretation is even known.

Taking an inclusion-exclusion type approach to this problem is slightly more straightforward. For this, we want to compute the number of $n$-digit numbers that at least contain some $r$ pairs of adjacent consecutive digits, in $c$ "clumps". For example, in $843256917$, there are $r=3$ adjacent pairs total: $(4,3)$, $(3,2)$, and $(5,6)$, in two clumps: $432$ and $56$.

We can:

• permute the $c$ clumps and $n-r-c$ elements outside the clumps ($n-r$ objects total) in $(n-r)!$ ways,
• orient the clumps in $2^c$ ways,
• choose the sizes of the $c$ clumps (each with size at least $2$, total size $r+c$), in $\binom{r-1}{c-1}$ ways, and
• choose the sizes of the $n-c+1$ gaps between the largest element of one clump and smallest element of the next, plus the start and end (each gap at least $0$, total size of gaps $n-r-c$) in $\binom{n-r}{c}$ ways.

This gives us the formula $$A_n = n! + \sum_{r=1}^{n-1} (-1)^r (n-r)! \sum_{c=1}^r 2^c \binom{r-1}{c-1} \binom{n-r}{c}.$$

(See the Art of Problem Solving thread for more discussion of this formula.)

Finally, we can approximate $A_n$ fairly closely by an asymptotic formula: there are $n-1$ pairs of consecutive elements, which can be adjacent in a random permutation with probability $\frac{2}{n-1}$. Assuming independence (falsely), there is a a $(1 - \frac{2}{n-1})^{n-1} \approx e^{-2}$ chance that no pair of consecutive elements is adjacent, which implies that $A_n \approx e^{-2} n!$.