A permutation p_{1} p_{2} ··· p_{n}
is an up-down permutation if p_{1} < p_{2} > p_{3}
< p_{4} > ···.
In other words,
*p _{i}* <

Other names that authors have used for these permutations are
*zig-zag permutations* and *alternating permutations*.
The later name is unfortunate since it is the standard term for
the group of permutations of even parity.

The number of *n* up-down permutations for
*n* = 1,2,...,15, is
1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765,
22368256, 199360981, 1903757312.
This is sequence
**A000111**(M1492) in
Neil J. Sloane's
database
of integer sequences.
These numbers are known as the **Euler** numbers and have
exponential generating function sec(*x*) + tan(*x*).
The Euler numbers are sometimes called the "up/down" numbers.

Define E(*n*,*k*) to be the number of up-down permutations for
which p_{1} = *k*.
Then E(1,1) = 1, E(*n*,*k*) = 0 if *k* >= *n*
or *k* < 1, and otherwise

E(*n*,*k*) = E(*n*,*k*+1)
+ E(*n*-1,*n*-*k*)

The program used is from the paper: Bauslaugh and Ruskey
*Generating Alternating Permutations Lexicographically*,
BIT, 30 (1990) 17-26.

(Please note that the suffix XXXX must be removed from the preceeding email address.)

It was last updated Wednesday, 10-May-2006 10:32:14 PDT.

There have been 4902 visitors to this page since May 16, 2000 .

©Frank Ruskey, 1995-2003.