Popularity of patterns over d-equivalence classes of words and permutations
Affiliation auteurs | !!!! Error affiliation !!!! |
Titre | Popularity of patterns over d-equivalence classes of words and permutations |
Type de publication | Journal Article |
Year of Publication | 2020 |
Auteurs | Baril J-L, Vajnovszki V |
Journal | THEORETICAL COMPUTER SCIENCE |
Volume | 814 |
Pagination | 249-258 |
Date Published | APR 24 |
Type of Article | Article |
ISSN | 0304-3975 |
Mots-clés | Descent set equivalence, distribution, Patterns in words and permutations, Popularity |
Résumé | Two same length words are d-equivalent if they have same descent set and same underlying alphabet. In particular, two same length permutations are d-equivalent if they have same descent set. The popularity of a pattern in a set of words is the overall number of copies of the pattern within the words of the set. We show the far-from-trivial fact that two patterns are d-equivalent if and only if they are equipopular over any d-equivalence class, and this equipopularity does not follow obviously from a trivial equidistribution. (C) 2020 Elsevier B.V. All rights reserved. |
DOI | 10.1016/j.tcs.2020.02.005 |