$1 \cdot 49$ integers $1,2, \cdots, n$ are arranged in a permutation such that 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?
［Solution］ 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 \geqslant 2$, if the number $n$ is placed in the $i$-th position, then the $n-i$ numbers after it are completely determined, i.e., they can only be $n-i, n-i-1, \cdots, 1$. The $i-1$ numbers before it have $a_{i-1}$ ways to be arranged. Considering the different positions of $n$, we must have
$$a_{n}=1+a_{1}+a_{2}+\cdots+a_{n-1} .$$

From $a_{1}=1$, we get $a_{2}=1+a_{1}=2$
$$\begin{array}{l}
a_{3}=1+a_{1}+a_{2}=2^{2} \\
a_{4}=1+a_{1}+a_{2}+a_{3}=8=2^{3}
\end{array}$$

This leads us to conjecture that $a_{n}=2^{n-1}$. It is not difficult to prove our conjecture using the second principle of mathematical induction.