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

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$]$n$ avoiding any $τ$ of the form 11$a-b$.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.181-202
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01349055
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:14:54
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44

Fichier

2559-9778-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349055, version 1

Collections

Citation

Toufik Mansour, Mark Shattuck. On avoidance of patterns of the form σ-τ by words over a finite alphabet. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.181-202. 〈hal-01349055〉

Partager

Métriques

Consultations de la notice

62

Téléchargements de fichiers

172