Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\pi\in S_n$ be a permutation. Define $m_k=|\{i: \ i\leq k, \ \pi(i)>k\}|$. For example, if $\pi=(597216384)$, then it's $m$ vector is $m(\pi):=(m_1,m_2,\ldots,m_{n-1})=(1,2,3,3,2,2,1,1)$. Is there some commonly associated name for $m_k$? In particular, for the sum $M:=\sum_{k=1}^{n-1}m_k$? This function came out of a paper related to reduced words. Quoting the paper, starting from the identity permutation, convert this permutation to $\pi$ by means of adjacent transpositions. Then one can interpret $m_k$ as the least number of times one needs to apply an adjacent swap $(k,k+1)\rightarrow (k+1,k)$.

Also, is there some nice relation between $M,m_k$ and the number of inversions in a permutation: $L(\pi):=\sum_{k=1}^{n-1}L_k(\pi),$ where $L_k(\pi)=\{i:\ i\geq k, \ \pi(k)>\pi(i)\}$? In other words, is there a connection between $m$ vectors and Lehmer codes? If there are no obvious connections between $m_k$ and inversions, are there some crude bounds that one can deduce between $L$and $M$? It seems to me that if one starts with the identity, $M=L$ for the sequence of the first few adjacent transpositions and then they begin to differ.

My inspiration for the latter question is based on the known bijection between major index and inversions.

share|cite|improve this question

I doubt that this has a name. I like to refer to a nice table page 388 in Kitaev's book. If it's not there, it's unlikely this has been widely studied.

S. Kitaev, Patterns in permutations and words, Springer, 2011.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.