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
Funding
\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.
| Funders | Funder number |
|---|---|
| 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 |
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