1
$\begingroup$

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?

  • 1
    That would just be an alternating sequence. At least, if you substract the mean, it literally is an alternating sequence.2012-04-09
  • 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.2012-04-09
  • 0
    @Raskolnikov: I would normally understand *alternating sequence* to be one whose terms alternated in sign.2012-04-09
  • 0
    @Brian: Yes, but you could see it as the sum of a constant sequence and an alternating sequence.2012-04-09
  • 0
    As with @Brian, I've heard them called "up-down permutations". Wikipedia seems to give priority to the term "alternating permutation": http://en.wikipedia.org/wiki/Alternating_permutation . As mentioned there, $\sec\theta+\tan\theta$ is the exponential generating function of the associated "Euler up-down (or zig-zag) numbers". (Not mentioned there, though, is that the connection between combinatorics and analytics is actually ... um ... geometrics. See my note "Zig-Zag Involutes, Up-Down Permutations, and Secant and Tangent": http://dlnds.com/math/pdfs/sectan.pdf )2012-04-09
  • 1
    @Raskolnikov: I can't see $1325476$ as the sum of a constant sequence and a sequence whose terms alternate in sign.2012-04-09
  • 1
    @Rahul: You're right, I didn't think that through. Thanks for correcting me.2012-04-09

1 Answers 1

1

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.

  • 0
    Thanks @Brian! From the Wikipedia link, I found the additional terms "fence" and "zigzag poset".2012-04-09