## Information on Up-down Permutations

A permutation p1 p2 ··· pn is an up-down permutation if p1 < p2 > p3 < p4 > ···. In other words, pi < pi+1 if i is odd, and pi > pi+1 if i is even.

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 Anum=A000111"> A000111(M1492) in 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 p1 = 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.

It was last updated .