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.
|Number of pages||12|
|Journal||Discrete Mathematics and Theoretical Computer Science|
|State||Published - 2014|
|Event||26th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2014 - Chicago, United States|
Duration: Jun 29 2014 → Jul 3 2014
Bibliographical noteFunding Information:
∗Email: email@example.com. Partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280. †Email: firstname.lastname@example.org. ‡Email: email@example.com. Supported by grant no. 090038013 from the Icelandic Research Fund.
Partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280. Supported by grant no. 090038013 from the Icelandic Research Fund.
© 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
- Affine permutations
- Graph of overlapping permutations
- Number of cycles
- Permutation pattern
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)
- Discrete Mathematics and Combinatorics