Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On avoidance of patt ...
Article

On avoidance of patterns of the form σ-τ by words over a finite alphabet

Toufik Mansour ORCID (1), Mark Shattuck (2)
(1) Department of Mathematics [Haïfa]
(2) Department of Mathematics [Tennessee]
Download article
Open on HAL
Imported on
February 23, 2014
Published on
September 15, 2015
Last modified on
March 31, 2025
Volume 17
vol. 17:2
Combinatorics
DOI
10.46298/dmtcs.2140
License
https://about.hal.science/hal-authorisation-v1
Indicators
1067
Views
764
Downloads

On avoidance of patterns of the form σ-τ by words over a finite alphabet

Toufik Mansour ORCID (1), Mark Shattuck (2)
(1) Department of Mathematics [Haïfa]
(2) Department of Mathematics [Tennessee]
Abstract
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$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • pattern avoidance
  • vincular patterns
  • $k$-ary words
Preview
Loading PDF preview...