A sequence of at least two distinct integers ${ \left\{x_1, x_2, x_3, x_4, \ldots, x_n | n \geq 2, x_i \ne x_j \forall i \ne j \right\} }$ that satisfies either the property:
$$
x_1 < x_2 > x_3 < x_4 \cdots <> x_n
$$
or:
$$
x_1 > x_2 < x_3 > x_4 \cdots <> x_n
$$
Is there a name for such a sequence?
Given any sequence of distinct integers, it is possible to arrange (or, "sort") it to satisfy the above property.
Positive integers can be arranged like http://oeis.org/A065190 or http://oeis.org/A103889.
The "sorted" arrangements of $\{ 1, 2 \}$ is: $1 > 2$ and $2 > 1$.
The "sorted" arrangements of $\{ 1, 2, 3 \}$ is: $1 < 3 > 2$ and $3 > 1 < 2$, and their mirrors: $2 < 3 > 1$ and $2 > 1 < 3$.
How many such (mirrored and non-mirrored) arrangements are possible?
Are there any other properties of such sequences?
Best Answer
It doesn’t really matter what $x_1,\dots,x_n$ are, as long as they are distinct, so let’s take them to be $1,\dots,n$. These permutations are called zigzag permutations. A permutation of your first kind is an up-down permutation or an alternating permutation; one of your second kind is a down-up permutation.
It’s not hard to see that there are exactly as many up-down permutations as there are down-up permutations. If $\pi$ be a zigzag permutation of $1,\dots,n$, let $\hat\pi$ be the permutation obtained by changing each term $x$ into $n+1-x$. For example, if $n=5$ and $\pi=32514$, $\hat\pi=34152$. If $\pi$ is up-down, $\hat\pi$ is down-up, and if $\pi$ is down-up, $\hat\pi$ is up-down, so this bijectively pairs up the two kinds of zigzag permutations.
The number of up-down permutations of $1,\dots,n$ is often denoted by $A_n$ and have been called the Euler zigzag numbers and the up-down numbers. To get the total number of zigzag permutations of $1,\dots,n$, just double $A_n$. As you’ve discovered, $A_2=1$ and $A_3=2$. The next few values are $A_4=5$, $A_5=16$, and $A_6=61$. These numbers are sequence A000111 in the On-Line Encyclopedia of Integer Sequences. To the best of my knowledge thay have no nice closed form; a rather ugly formula for $A_n$ is derived here.
You can read more about them in Wikipedia.