On zigzag permutations and comparisons of adjacent elements

DOI10.1016/0020-0190(85)90057-2MaRDI QIDQ1063028zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90057-2

zbMATH Keywords

algorithmcomparisonpermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Review text

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.

Recommendations

• Generating permutations with given ups and downs
• Generating alternating permutations lexicographically
• scientific article; zbMATH DE number 4010574
• Ranking and unranking permutations in linear time
• Some considerations on permutation trees

Cites work

• Enumeration of permutations with prescribed up-down and inversion sequences
• Permutations and sequences
• Permutations with prescribed pattern

Cited in

(1)

• On the frequencies of patterns of rises and falls

This page was built for publication: On zigzag permutations and comparisons of adjacent elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1063028)