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.
| Original language | English |
|---|---|
| Pages (from-to) | 37-48 |
| 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 note
Publisher Copyright:© 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
Keywords
- Affine permutations
- Graph of overlapping permutations
- Number of cycles
- Permutation pattern
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics