On avoidance of patterns of the form σ-τ by words over a finite alphabet
Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2140/pdf |
| _version_ | 1827323844839342080 |
|---|---|
| author | Toufik Mansour Mark Shattuck |
| author_facet | Toufik Mansour Mark Shattuck |
| author_sort | Toufik Mansour |
| collection | DOAJ |
| description | Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the equivalences witnessed for such patterns of length four. When combined with previous results, numerical evidence, and some arguments in specific cases, we obtain the complete Wilf-classification for all vincular patterns of length four containing a single dash. In some cases, our proof shows further that the equivalence holds for multiset permutations since it is seen to respect the number of occurrences of each letter within a word. Some related enumerative results are provided for patterns $τ$ of length four, among them generating function formulas for the number of members of [$k$]<sup>$n$</sup> avoiding any $τ$ of the form 11$a-b$. |
| first_indexed | 2024-04-25T01:59:04Z |
| format | Article |
| id | doaj.art-f51dfca405094cfb93877a2314a771ed |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:04Z |
| publishDate | 2015-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f51dfca405094cfb93877a2314a771ed2024-03-07T15:28:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-09-01Vol. 17 no.2Combinatorics10.46298/dmtcs.21402140On avoidance of patterns of the form σ-τ by words over a finite alphabetToufik Mansour0https://orcid.org/0000-0001-8028-2391Mark Shattuck1Department of Mathematics [Haïfa]Department of Mathematics [Tennessee]Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the equivalences witnessed for such patterns of length four. When combined with previous results, numerical evidence, and some arguments in specific cases, we obtain the complete Wilf-classification for all vincular patterns of length four containing a single dash. In some cases, our proof shows further that the equivalence holds for multiset permutations since it is seen to respect the number of occurrences of each letter within a word. Some related enumerative results are provided for patterns $τ$ of length four, among them generating function formulas for the number of members of [$k$]<sup>$n$</sup> avoiding any $τ$ of the form 11$a-b$.https://dmtcs.episciences.org/2140/pdfpattern avoidancevincular patterns$k$-ary words[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Toufik Mansour Mark Shattuck On avoidance of patterns of the form σ-τ by words over a finite alphabet Discrete Mathematics & Theoretical Computer Science pattern avoidance vincular patterns $k$-ary words [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On avoidance of patterns of the form σ-τ by words over a finite alphabet |
| title_full | On avoidance of patterns of the form σ-τ by words over a finite alphabet |
| title_fullStr | On avoidance of patterns of the form σ-τ by words over a finite alphabet |
| title_full_unstemmed | On avoidance of patterns of the form σ-τ by words over a finite alphabet |
| title_short | On avoidance of patterns of the form σ-τ by words over a finite alphabet |
| title_sort | on avoidance of patterns of the form σ τ by words over a finite alphabet |
| topic | pattern avoidance vincular patterns $k$-ary words [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2140/pdf |
| work_keys_str_mv | AT toufikmansour onavoidanceofpatternsoftheformstbywordsoverafinitealphabet AT markshattuck onavoidanceofpatternsoftheformstbywordsoverafinitealphabet |