Bipartition orders and statistics on words (Q1918878)

From MaRDI portal
Revision as of 22:36, 19 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: reviewed by (P1447): Item:Q590664)
scientific article
Language Label Description Also known as
English
Bipartition orders and statistics on words
scientific article

    Statements

    Bipartition orders and statistics on words (English)
    0 references
    0 references
    21 July 1996
    0 references
    Let \(X\) be any alphabet. For any subset \(U\) of \(X\times X\), \(x\succ y\) if \((x, y)\in U\), and \(x\not\succ y\) if \((x, y)\not\in U\); \(U\) is an ``ordre bipartitionnaire'' if, for all \(x, y, z\in X\), \(z\succ y\) and \(y\succ x\Rightarrow z\succ x\), and \(z\succ y\) and \(x\not\succ y\Rightarrow z\succ x\). For any word \(w= x_1 x_2\dots x_m\in X^*\), the free monoid generated by \(X\), \(\text{inv}_U w= \text{Card}\{(i, j)\mid 1\leq i< j\leq m\) and \(x_i\succ x_j\}\), \(\text{maj}_U w= \sum \{i\mid 1\leq i\leq n- 1\) and \(x_i\succ x_{i+ 1}\}\). \textit{D. Foata} and \textit{D. Zeilberger} [Graphical major indices, submitted for publication] proved Theorem 1: Statistics \(\text{maj}_U\) and \(\text{inv}_U\) are equidistributed iff \(U\) is an ordre bipartitionnaire. For \(x, y\in X\), the (generalized) cyclic interval \(] ]x, y] ]_U\) is defined to equal \(\{z\in X\mid z\succ x\) and \(z\not\succ y\}\) if \(x\not\succ y\), and \(\{z\in X\mid z\succ x\) or \(z\not\succ y\}\) if \(x\succ y\). Where the symbol \(\infty\) is adjoined to an alphabet, one assumes that, for all \(x\), \(x\not\succ \infty\) an \(\infty\succ x\). For a word \(w= x_1 x_2\dots x_m\) one defines, with the convention \(x_{n+ 1}= \infty\), \(\text{maj} 2_U w= \sum^m_{j= 1} \langle x_1 x_2\dots x_{j- 1}, ] ] x_j, x_{j+ 1}] ]_U\rangle\). ``In this note we prove the following theorem: Theorem 2. The statistics \(\text{maj}_U\) and \(\text{maj} 2_U\) are equivalent iff the subset \(U\) is an ordre bipartitionnaire''.
    0 references
    orders
    0 references
    alphabet
    0 references
    word
    0 references
    free monoid
    0 references
    cyclic interval
    0 references
    statistics
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references