Counting occurrences of patterns in permutations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917603316858880 |
|---|---|
| author | Conway, Andrew R Guttmann, Anthony J |
| author_facet | Conway, Andrew R Guttmann, Anthony J |
| contents | We develop a new, powerful method for counting elements in a multiset. As a first application, we use this algorithm to study the number of occurrences of patterns in a permutation. For patterns of length 3 there are two Wilf classes, and the general behaviour of these is reasonably well-known. We slightly extend some of the known results in that case, and exhaustively study the case of patterns of length 4, about which there is little previous knowledge. For such patterns, there are seven Wilf classes, and based on extensive enumerations and careful series analysis, we have conjectured the asymptotic behaviour for all classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_12682 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Counting occurrences of patterns in permutations Conway, Andrew R Guttmann, Anthony J Combinatorics Data Structures and Algorithms 05A15 (Primary) 05A05, 06-04 (Secondary) We develop a new, powerful method for counting elements in a multiset. As a first application, we use this algorithm to study the number of occurrences of patterns in a permutation. For patterns of length 3 there are two Wilf classes, and the general behaviour of these is reasonably well-known. We slightly extend some of the known results in that case, and exhaustively study the case of patterns of length 4, about which there is little previous knowledge. For such patterns, there are seven Wilf classes, and based on extensive enumerations and careful series analysis, we have conjectured the asymptotic behaviour for all classes. |
| title | Counting occurrences of patterns in permutations |
| topic | Combinatorics Data Structures and Algorithms 05A15 (Primary) 05A05, 06-04 (Secondary) |
| url | https://arxiv.org/abs/2306.12682 |