Auto comment: topic has been updated by 3905 (previous revision, new revision, compare).

The first obvious solution is dp: f[mask_of_used_elements][last_element], everything you need to recalc this dp is to find some not used element and try to add it in such way, that all conditions will be met. Sth like f[mask_of_used_elements | new_element][new_element] += f[mask_of_used_elements][last_element]

The answer is sum of f[2^n — 1][i] for all i.

In general case, if the numbers are distinct, you don't care about the numbers, being able to normalize them. In this case, you can use a dynamic programming solution where dp[i][j] = number of permutations ending in j of i elements that respect the first i — 1 relations(through relation I mean a[1] < a[2] > a[3] ...). You can find reccurence in O(N) getting N ^ 3 time complexity, and also, using same partial sumes you can get O(N ^ 2) total time with O(1) the reccurence for an element. To be noted that this solution is a generalization which works for any given order of signs. This, being a particular case, most probably can be solved in O(N) or O(1) or something like that observing some sort of formula(using the previous dynamic) that could be inductively prove, but for getting this formula you should run the program for small values and observe certain things, I guess. One more time, this solution only works if the numbers are distinct. Otherwise, I don't think that there exist any solution with polynomial time complexity.