Popularity of patterns over d-equivalence classes of words and permutations

Affiliation auteurs!!!! Error affiliation !!!!
TitrePopularity of patterns over d-equivalence classes of words and permutations
Type de publicationJournal Article
Year of Publication2020
AuteursBaril J-L, Vajnovszki V
JournalTHEORETICAL COMPUTER SCIENCE
Volume814
Pagination249-258
Date PublishedAPR 24
Type of ArticleArticle
ISSN0304-3975
Mots-clésDescent 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.

DOI10.1016/j.tcs.2020.02.005