Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
1  
@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
1  
@Rahul: You're right, I didn't think that through. Thanks for correcting me. –  Raskolnikov Apr 9 '12 at 8:18
show 2 more comments

1 Answer

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|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
add comment

Your Answer

 
discard

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.