Geodesic
The insertion encoding of permutations
The electronic journal of combinatorics, Tome 12 (2005)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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.
DOI : 10.37236/1944
Classification : 05A05, 05A15, 68Q45
Mots-clés : enumeration, pattern classes, Wilf equivalence 
Michael H. Albert; Steve Linton; Nik Ruškuc. The insertion encoding of permutations. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1944
@article{10_37236_1944,
     author = {Michael H. Albert and Steve Linton and Nik Ru\v{s}kuc},
     title = {The insertion encoding of permutations},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1944},
     zbl = {1081.05001},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1944/}
}
TY  - JOUR
AU  - Michael H. Albert
AU  - Steve Linton
AU  - Nik Ruškuc
TI  - The insertion encoding of permutations
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1944/
DO  - 10.37236/1944
ID  - 10_37236_1944
ER  - 
%0 Journal Article
%A Michael H. Albert
%A Steve Linton
%A Nik Ruškuc
%T The insertion encoding of permutations
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1944/
%R 10.37236/1944
%F 10_37236_1944

Cité par Sources :