The numbers 
are arranged in a list so that each number is either greater than all the numbers that come before it or is less than all the numbers that come before it. For example, 
is one such list: notice that (for instance) the 6 is greater than all the numbers that come before it, and the 2 is less than all the numbers that come before it.
How many such lists of the numbers are possible?
+893 The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example and some of those to the left will be bigger, and some smaller.) Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on. There will only one choice left for the first digit, so 2 to the eight or 256 possibles
+118609 I have no idea where to start.
Some of the permutations are obvious but how you would count them I have no idea 
+33615 I conjecture that the answer is 256 (= 29-1) based on extrapolating results for sets {1,2}, {1,2,3} and {1,2,3,4}. However, I have yet to find an elegant proof!
Partial reasoning:
If we have a number of arrangements for the set A = {1,...,n-1} then we can immediately get that many again for the set B = {1, ...,n} by simply putting n after all the arrangements for A. Any extra arrangements for B must end in 1, because if they end in anything other than 1 or n, the end value will be bigger than 1 and smaller than n, violating the criteria. It seems that there are just as many arrangements ending in 1 as there are ending in n, hence, since there are just 2 arrangements, for the set {1.2} each extra digit doubles the number of arrangements. There must be a simple proof of the fact that there are just as many arrangements ending in 1 as there are ending in n (if it's true!), but I'm having a mental block trying to see it!
.
+893 The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example and some of those to the left will be bigger, and some smaller.) Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on. There will only one choice left for the first digit, so 2 to the eight or 256 possibles
