Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 $$


$$ 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 or

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?

share|cite|improve this question
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. – Rahul 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
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thanks @Brian! From the Wikipedia link, I found the additional terms "fence" and "zigzag poset". – vapace Apr 9 '12 at 4:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.