Number of cycles in the graph of $312$-avoiding permutations
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 lette...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2014-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2378/pdf |
| _version_ | 1797270258026807296 |
|---|---|
| author | Richard Ehrenborg Sergey Kitaev Einar Steingrımsson |
| author_facet | Richard Ehrenborg Sergey Kitaev Einar Steingrımsson |
| author_sort | Richard Ehrenborg |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:24Z |
| format | Article |
| id | doaj.art-12e2c3fad9da4ffd88ae2791776090af |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:24Z |
| publishDate | 2014-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-12e2c3fad9da4ffd88ae2791776090af2024-03-07T14:53:19ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502014-01-01DMTCS Proceedings vol. AT,...Proceedings10.46298/dmtcs.23782378Number of cycles in the graph of $312$-avoiding permutationsRichard Ehrenborg0https://orcid.org/0000-0001-5854-3890Sergey Kitaev1https://orcid.org/0000-0003-3324-1647Einar SteingrımssonDepartment of MathematicsDepartment of Computer and Information Sciences [Univ Strathclyde]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.https://dmtcs.episciences.org/2378/pdfpermutation patterngraph of overlapping permutationsnumber of cyclesaffine permutations[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Richard Ehrenborg Sergey Kitaev Einar Steingrımsson Number of cycles in the graph of $312$-avoiding permutations Discrete Mathematics & Theoretical Computer Science permutation pattern graph of overlapping permutations number of cycles affine permutations [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | Number of cycles in the graph of $312$-avoiding permutations |
| title_full | Number of cycles in the graph of $312$-avoiding permutations |
| title_fullStr | Number of cycles in the graph of $312$-avoiding permutations |
| title_full_unstemmed | Number of cycles in the graph of $312$-avoiding permutations |
| title_short | Number of cycles in the graph of $312$-avoiding permutations |
| title_sort | number of cycles in the graph of 312 avoiding permutations |
| topic | permutation pattern graph of overlapping permutations number of cycles affine permutations [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/2378/pdf |
| work_keys_str_mv | AT richardehrenborg numberofcyclesinthegraphof312avoidingpermutations AT sergeykitaev numberofcyclesinthegraphof312avoidingpermutations AT einarsteingrımsson numberofcyclesinthegraphof312avoidingpermutations |