[Information Index] [Generation Index] [COS homepage]

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

[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(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.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.