# Is there a name for a neither-increasing-nor-decreasing-but-alternating sequence like below?

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?

• That would just be an alternating sequence. At least, if you substract the mean, it literally is an alternating sequence. – Raskolnikov Apr 9 '12 at 3:53
• When $x_1,\dots,x_n$ are a permutation of the numbers $1,\dots,n$, they are sometimes called up-down and down-up permutations, respectively. – Brian M. Scott Apr 9 '12 at 3:54
• @Raskolnikov: I would normally understand alternating sequence to be one whose terms alternated in sign. – Brian M. Scott Apr 9 '12 at 3:54
• @Raskolnikov: I can't see $1325476$ as the sum of a constant sequence and a sequence whose terms alternate in sign. – user856 Apr 9 '12 at 4:32
• @Rahul: You're right, I didn't think that through. Thanks for correcting me. – Raskolnikov Apr 9 '12 at 8:18

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.