Carleton University
Technical Report TR-62
October 1984
On Zigzag Permutations and Comparisons of Adjacent Elements
M.D. Atkinson
Abstract
Each permutation (a1 ,a2, … , an) of 1,2, … , n determines a sequence of ‘<‘ and ‘>’ relations determined by the relations holding between adjacent values (ai,ai+1). A new and elementary algorithm is given which, for every such pattern of ‘<‘, ‘>’ relations, computes the number of permutations with that pattern. The algorithm enables one to calculate (in bits) the amount of information gained by comparing all adjacent pairs of elements in a list. It also has a simple extension to circular patterns of relations.