Permutations of the form a_1<a_2>a_3< >a_n

[joeblow]

I've been thinking about this one for over a week now. Does anyone have any smart way of counting the permutations of {1,2,3,...,n} that are of the form a_1< a_2 > a_3 < ... > a_n?

You notice that there are (n-1) ways to choose the first elt. since the first choice cannot be n. And the complicated thing is that for an odd choice, if you choose the lowest possible elt., then the next choice cannot be the lowest poss elt. For even choices, if you choose the highest poss. elt., you cannot choose the highest elt. for the next choice. So, clearly thinking about this in terms of how many ways to choose individual elts. is probably not optimal. Can someone suggest another way of thinking about it? Thanks.

 

[mXSCNT]

Apparently it is a tricky problem
http://en.wikipedia.org/wiki/Alternating_permutation
(I found that page by googling 1, 1, 2, 5, 16, 61, 272, 1385, 7936)