That's a very elegant formula (I think technically you're missing a division by two in it, but that's a minor detail). Here's a rough proof I wrote up of why that works.

Observation 1: The actual numbers you are arranging do not matter as long as they are distinct — just how many there are. This is because for any strictly increasing sequence {a1, ..., an}, you can map ai to i for i = 1 to n without changing any of the relative orderings.

Observation 2: For n > 1, call a decreasing-end extremal permutation an extremal permutation {p(1), ..., p(n)} such that p(n) < p(n-1), and an increasing-end extremal permutation an extremal permutation {p(1), ..., p(n)} such that p(n) > p(n-1). Then for any n, the number of increasing-end and decreasing-end permutations of size n are the same. Consider any increasing-end permutation {p(1), ..., p(n)} of the sequence {1, ..., n}. Then for all i from 1 to n, let p'(i) equal n + 1 — p(i). Therefore, if p(n) > p(n-1), p'(n) < p(n-1), and p' is still an extremal permutation of size n (since all relative orderings are flipped, all relative minima in p and relative maxima in p' and vice verse). So p' is a decreasing-end permutation, and for every increasing-end permutation there exists a unique decreasing-end permutation. So if there are a increasing-end permutations and b decreasing-end permutations, a <= b. Similar logic shows that every decreasing-end permutation can be mapped to a unique increasing-end permutation, so b <= a. For both of these to be true, a = b. Therefore, if f(n) is the number of extremal permutations of size n, there are f(n)/2 increasing-end extremal permutations and f(n)/2 decreasing-end extremal permutations. For n = 1, the permutation {1} will be considered both increasing-end and decreasing-end, and for n = 0 the permutation {} will be considered both increasing-end and decreasing-end.

Now, we will try each possible placement of the number n+1 in our extremal permutation of size n+1. For each position k+1, there are k elements before n+1 and n — k elements after it. In order for the permutation to be extremal, the arrangement of the first k elements must be a decreasing-end extremal permutation of size k (there are f(k)/2 ways to do this — we will say that f(0) = 2 and f(1) = 2 for the purposes of calculation and add them as special cases later), and the arrangement of the last n — k elements must be an extremal permutation of size n — k such that p(1) < p(2) — this can be thought of as a decreasing-end permutation in reverse order, so the number of such permutations is f(n-k). Also, because of observation 1, we can arbitrarily choose which elements come before n + 1 in choose(n, k) ways. Therefore, f(n+1) = sum{k = 0 to n} f(k)/2 * f(n-k)/2 * choose(n, k), with base cases of f(0) = 2 and f(1) = 2. Then, add in special cases for 0 and 1 since we know that the actual answer is 1 for both of them.

Sgu