16.2.39 ** Find the number of positive integers such that in base $n$ their digits are all different, and except for the leftmost digit, each digit differs from some digit to its left by $\pm 1$.

 untranslated text remains unchanged.
If 0 is allowed to be the leftmost digit, $F(n)$ is the number of $n$-ary numbers that satisfy the condition, then
$$
F(1)=1 \text { (there is only one number } 0 \text { ). }
$$
$F(n+1)$ numbers can be divided into the following three categories:
(1) $n+1$ numbers $0,1,2, \cdots, n$;
(2) $F(n)$ numbers in the $n$-ary system, with an additional digit appended to the right, which is 1 more than the largest digit already used in the number.
(3) $F(n)$ numbers in the $n$-ary system, where each digit is increased by 1, and then the smallest digit of the original number is appended to the right.

Clearly, these 3 categories have no overlap. On the other hand, any number $A$ among the $F(n+1)$ numbers, if the rightmost digit $h$ is not the largest digit $m$, then $m-1$ must be to the left of $m$, $m-2$ to the left of $m-1$, $\cdots$, i.e., $m > m-1 > \cdots > k$, where $k$ is the leftmost digit. Among the digits other than $m, m-1, m-2, \cdots, k$, the leftmost is $k-1$, the next leftmost is $k-2, \cdots$, i.e., $k-1 > k-2 > \cdots > h$, thus $h$ is the smallest digit of $A$. Therefore, all $F(n+1)$ numbers fall into the above 3 categories, with no omissions.
Thus, the recurrence relation is
$$
F(n+1)=n+1+2 F(n),
$$

Therefore,
$$
F(n+1)+(n+3)=2(F(n)+n+2),
$$
$$
\begin{array}{c}
F(n+1)+n+3=2^{n}(F(1)+1+2)=2^{n+2}, \\
F(n)=2^{n+1}-n-2 .
\end{array}
$$

Excluding numbers with 0 as the leftmost digit, there are $n$ such numbers (i.e., $0,01,012, \cdots, \overline{012 \cdots(n-1)}$), the answer is $2^{n+1}-2 n-2$.