×

Bipartition orders and statistics on words. (Ordres bipartitionnaires et statistiques sur les mots.) (French) Zbl 0854.05005

Electron. J. Comb. 3, No. 2, Research paper R3, 5 p. (1996); printed version J. Comb. 3, No. 2, 127-131 (1996).
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}\}\). D. Foata and 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”.

MSC:

05A10 Factorials, binomial coefficients, combinatorial functions
05E10 Combinatorial aspects of representation theory
20B99 Permutation groups
Full Text: EuDML EMIS