There can only be one

Here is the intended solution using a recurrence relation:

Begin with the case of $1$ element. Obviously the only permutation is $\{1\}$ , so there is $1$ total in this case.

Now I seek to prove that the number of unimodal permutations with $n$ elements is $2^{n-1}$ ; we already have the base case of $n=1$ .

Assume we have proven this for $n=k$ ; then, for $n=k+1$ , increase every element in $n=k$ by $1$ and add $1$ to either the beginning or the end of the new permutation. This establishes a correspondence, so that the number with $n=k+1$ is precisely the number with $n=k$ times $2$ .

So by induction, the value for $n$ elements is $2^{n-1}$ , so the answer is $2^{9-1}=\boxed{256}$ .

The number of unimodal permutations on $n$ elements is $2^{n-1}$ . Proof: let $U_n$ be the set of unimodal permutations on $\{ 1, \ldots, n \}$ . (Identify an element of $U_n$ with the list $\sigma_1, \ldots, \sigma_n$ of its images.) Then the map $U_{n+1} \rightarrow U_n$ given by removing the largest element is surjective and two-to-one: Clearly removing the largest element preserves unimodality, and every element of $U_n$ is the image of exactly two elements of $U_{n+1}$ , because if we try to add $n+1$ to an element of $U_n$ to get an element of $U_{n+1}$ , there are exactly two choices that will work: immediately before or after $n$ .

So $|U_{n+1}| = 2|U_n|$ . The result follows by an easy induction. When $n = 9$ we get $2^{9-1} = \fbox{256}$ .

Consider a constructive counting approach. In any unimodal permutation of our set, the $9$ must be the local maximum, since it is the largest number in the set. Say that the $9$ is at position $i,$ where $1 \le i \le 9.$ Then there are $i-1$ elements to the left of the $9,$ and $9-i$ elements to the right of the $9.$ We choose the elements on the left in $\dbinom{8}{i-1}$ ways, and then the elements on the right are determined. The crucial step is to note that for every choice of the elements on the left, there is exactly one way to order them (in increasing order), and similarly there is one way to order the elements on the right (in decreasing order), so when $9$ is at position $i,$ there are exactly $\dbinom{8}{i-1}$ unimodal permutations.

Thus, the total number of unimodal permutations is given by $\displaystyle\sum_{i=1}^9 \dbinom{8}{i-1},$ or, shifting indices, $\displaystyle\sum_{i=0}^8 \dbinom{8}{i} = 2^8 = \boxed{256}.$