Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg; Sergey Kitaev; Einar Steingrímsson

Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg
, Sergey Kitaev
, Einar Steingrímsson

Mathematics

Producción científica: Conference article › revisión exhaustiva

Resumen

The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations.

Idioma original	English
Páginas (desde-hasta)	37-48
Número de páginas	12
Publicación	Discrete Mathematics and Theoretical Computer Science
Estado	Published - 2014
Evento	26th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2014 - Chicago, United States Duración: jun 29 2014 → jul 3 2014

Nota bibliográfica

Publisher Copyright:
© 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Financiación

\u2217Email: [email protected]. Partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280. \u2020Email: [email protected]. \u2021Email: [email protected]. Supported by grant no. 090038013 from the Icelandic Research Fund.

Financiadores	Número del financiador
Icelandic Centre for Research
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	DMS 0902063
National Security Agency	090038013, H98230-13-1-0280

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Discrete Mathematics and Combinatorics

Otros archivos y enlaces

Citar esto

@article{55c605df38184380ba6f43a64f05e4d8,

title = "Number of cycles in the graph of 312-avoiding permutations",

abstract = "The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations.",

keywords = "Affine permutations, Graph of overlapping permutations, Number of cycles, Permutation pattern",

author = "Richard Ehrenborg and Sergey Kitaev and Einar Steingr{\'i}msson",

note = "Publisher Copyright: {\textcopyright} 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France; 26th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2014 ; Conference date: 29-06-2014 Through 03-07-2014",

year = "2014",

language = "English",

pages = "37--48",

}

TY - JOUR

T1 - Number of cycles in the graph of 312-avoiding permutations

AU - Ehrenborg, Richard

AU - Kitaev, Sergey

AU - Steingrímsson, Einar

PY - 2014

Y1 - 2014

N2 - The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations.

AB - The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations.

KW - Affine permutations

KW - Graph of overlapping permutations

KW - Number of cycles

KW - Permutation pattern

UR - https://www.scopus.com/pages/publications/85082938427

UR - https://www.scopus.com/pages/publications/85082938427#tab=citedBy

M3 - Conference article

AN - SCOPUS:85082938427

SN - 1462-7264

SP - 37

EP - 48

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

T2 - 26th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2014

Y2 - 29 June 2014 through 3 July 2014

ER -

Number of cycles in the graph of 312-avoiding permutations

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Otros archivos y enlaces

Huella

Citar esto