21.2.3 ** The permutations of integers $1,2, \cdots, n$ satisfy: each number is either greater than all the numbers before it, or less than all the numbers before it. How many such permutations are there?
Let the number of permutations we are looking for be $a_{n}$.
When $n=1$, there is only the number 1, so obviously $a_{1}=1$.
For $n>2$, consider the permutations where $n$ is in the $i$-th position. At this time, the positions of the $n-i$ numbers after $n$ are uniquely determined, and can only be $n-i, n-i-1, \cdots, 2,1$. The $i-1$ numbers before it have $a_{i-1}$ ways of being arranged. Since $i=1,2, \cdots, n$, it must be that $a_{n}=1+a_{1}+\cdots+a_{n-1}$. Therefore, $a_{n-1}=1+a_{1}+\cdots+a_{n-2}$. Subtracting the two equations gives $a_{n}-a_{n-1}=a_{n-1}$, which means $a_{n}=2 a_{n-1}(n \geqslant 2)$. Thus, $a_{n}=a_{1} \cdot 2^{n-1}=2^{n-1}$, so the number of permutations we are looking for is $2^{n-1}$.