$1 \cdot 13$ Let the positive integer $M$ in its $n$-ary representation have all distinct digits, and each digit, except the leftmost one, differs from some digit to its left by $\pm 1$. Find the number of all such positive integers $M$. (The answer should be given as an explicit function of $n$ in its simplest form)


[Solution] First, we allow 0 as the leftmost digit and use $F(n)$ to denote the number of $M$ that meet the requirements. Thus,
$$
\begin{aligned}
F(1)= & 1 \text { (the only number is } 0) ; \\
F(2)= & 4(0,01,1,10) ; \\
F(3)= & 11(0,01,012,1,10,102,12,120,2,21,210) ; \\
F(4)= & 26(0,01,012,0123,1,10,102,1023,12,120,1203,123, \\
& \quad 1230,2,21,210,2103,213,2130,23,231,2310,3,32, \\
& 321,3210) .
\end{aligned}
$$

From the table above, we can see that the rightmost digit is either the largest or the smallest among all digits. Let's prove this.
Consider a number $M$ that meets the requirements, represented in $n$-ary notation as
$$
M=\overline{k_{1} k_{2} \cdots k_{m}}, \quad 1<m \leqslant n,
$$

Let $k_{i}=\min \left\{k_{1}, k_{2}, \cdots, k_{m}\right\}$ and $k_{j}=\max \left\{k_{1}, k_{2}, \cdots, k_{m}\right\}$, and assume $i, j<m$. Without loss of generality, assume $i<j$. Since each digit differs from the digit to its left by $\pm 1$, for any positive integer $h, k_{i}<h<k_{j}$, there must exist $l<j$ such that $k_{l}=h$. In particular, for $h=k_{m}$, we have $k_{l}=k_{m}, l \neq m$, which is a contradiction.

Therefore, the $F(n+1)$ numbers that meet the requirements in $(n+1)$-ary notation can be divided into 3 categories:
(1) $n+1$ one-digit numbers: $0,1,2, \cdots, n$;
(2) $F(n)$ numbers that meet the requirements in $n$-ary notation, with an additional digit appended to the right, which is 1 greater than the largest digit already used in the number;
(3) $F(n)$ numbers in $n$-ary notation, where each digit is incremented by 1, and then the smallest digit of the original number is appended to the right.
This gives us the recurrence relation:
$$
\begin{array}{c}
F(n+1)=n+1+2 F(n), \\
F(n+1)+(n+3)=2\{F(n)+(n+2)\} .
\end{array}
$$

From this recurrence, we get:
$$
\begin{aligned}
F(n+1)+(n+3) & =2^{n}\{F(1)+(1+2)\}=2^{n+2}, \\
F(n) & =2^{n+1}-n-2 .
\end{aligned}
$$

Finally, in the count of $F(n)$, we exclude the numbers starting with 0: $0,01,012, \cdots, 012 \cdots(n-1)$, which are $n$ numbers in total, to get the total number of positive integers $M$ that meet the requirements as $2^{n+1}-2 n-2$.