Information on Up-down Permutations

A permutation p₁ p₂ ··· p_n is an up-down permutation if p₁ < p₂ > p₃ < p₄ > ···. In other words, p_i < p_i+1 if i is odd, and p_i > p_i+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 p₁ = 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.

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.
There have been 5636 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.