The insertion encoding of permutations

M H Albert, S Linton, N Ruskuc

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

We introduce the insertion encoding, an encoding of finite permutations. Classes of permutations whose insertion encodings form a regular language are characterized. Some necessary conditions are provided for a class of permutations to have insertion encodings that form a context free language. Applications of the insertion encoding to the evaluation of generating functions for classes of permutations, construction of polynomial time algorithms for enumerating such classes, and the illustration of bijective equivalence between classes are demonstrated.

Original languageEnglish
Article numberR47
Pages (from-to)-
Number of pages31
JournalElectronic Journal of Combinatorics
Volume12
Issue number1
Publication statusPublished - 19 Sept 2005

Fingerprint

Dive into the research topics of 'The insertion encoding of permutations'. Together they form a unique fingerprint.

Cite this