6533b7d6fe1ef96bd1265cbb

RESEARCH PRODUCT

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

Jean-luc BarilVincent Vajnovszki

subject

FOS: Computer and information sciencesClass (set theory)General Computer ScienceDiscrete Mathematics (cs.DM)010102 general mathematics0102 computer and information sciences01 natural sciencesPopularityTheoretical Computer ScienceCombinatoricsSet (abstract data type)010201 computation theory & mathematicsIf and only if[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: MathematicsMathematics - CombinatoricsCombinatorics (math.CO)0101 mathematicsAlphabetComputingMilieux_MISCELLANEOUSComputer Science::Formal Languages and Automata TheoryMathematicsDescent (mathematics)Computer Science - Discrete Mathematics

description

Abstract 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.

yearjournalcountryeditionlanguage
2020-04-01
http://arxiv.org/abs/1911.05067