On zigzag permutations and comparisons of adjacent elements (Q1063028)

Each permutation \((a_ 1,a_ 2,...,a_ n)\) of 1,2,...,n determines a sequence of \(''<''\) and \(''>''\) relations determined by the relations holding between adjacent values \((a_ i,a_{i+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.