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

We can defined the descent set of a word $w\in\mathbb{N}^n$ to be the set $$D(w)=\{i\in[n-1]:w(i)>w(i+1)\}.$$ Also, we can take as definition for the major index of $w$ to be $\text{maj}(w)=\sum_{d\in D(w)}d$.

Now let $k_i$ be the number of instances of $i$ in $w$. If $w\in[r]^n$ and $w(n)=s$, why is it then that $w'=(12\cdots r)^{r-s}\circ w$ has major index $\text{maj}(w')=\text{maj}(w)-k_{s+1}+\cdots+k_r$?

I assume theres some sort of shift going on, but I don't see the relationship between the $\text{maj}$s. Thank you.

share|cite|improve this question
up vote 4 down vote accepted

First off, I think that you have a small error in the statement of the result. Suppose that $n=5$, $r=3$, and $w=12321$, so that $s=1$, $D(w)=\{3,4\}$, and $\operatorname{maj}(w)=7$. Then $w\,'=31213$, $D(w\,')=\{1,3\}$, and $\operatorname{maj}(w\,')=4=7-(k_2+k_3)$. It appears that the conclusion should be that $\operatorname{maj}(w\,')=\operatorname{maj}(w)-(k_{s+1}+\dots+k_r)$.

The transformation $w\mapsto w\,'$ replaces each element $i$ of $w$ by

$$i\,'=\begin{cases} i+r-s,&\text{if }1\le i\le s\\\\ i-s,&\text{if }s<i\le r\;. \end{cases}\tag{1}$$

Suppose that $d\in D(w)$, and let $i=w(d)$. There are two cases.

If $i\le s$, then $w\,'(d)=i+r-s$, and $w(d+1)<w(d)$, so $w\,'(d+1)=w(d+1)+r-s$, and $d\in D(w\,')$.

Now suppose that $s<i\le r$, so that $i\,'=i-s$. If $w(d+1)>s$ as well, then $d$ remains a descent of $w\,'$, just as in the first case. If $w(d+1)\le s$, then

$$w\,'(d+1)=w(d+1)+r-s>r-s\ge i-s=i\,'\;,$$

so $d\notin D(w\,')$.

Putting the two cases together, we see that $$D(w)\setminus D(w\,')=\{d\in D(w):w(d+1)\le s<w(d)\}\;,$$

and we need now to identify the indices that belong to $D(w\,')\setminus D(w)$.

Suppose that $d\in D(w\,')\setminus D(w)$. It’s clear from $(1)$ that this happens iff $w(d)\le s<w(d+1)$ and $w(d)+r-s>w(d+1)-s$, i.e., iff $w(d)\le s<w(d+1)<w(d)+r$. The final inequality is automatic, so $d\in D(w\,')\setminus D(w)$ iff $w(d)\le s<w(d+1)$.

Let $m=\operatorname{maj}(w)-\operatorname{maj}(w\,')$; clearly

$$\begin{align*}m&=\sum\{d:d\in D(w)\setminus D(w\,')\}-\sum\{d:d\in D(w\,')\setminus D(w)\}\\\\ &=\sum\{d:w(d+1)\le s<w(d)\}-\sum\{d:w(d)\le s<w(d+1)\}\;.\tag{2} \end{align*}$$

Say that an element of $w$ is small if it is at most $s$ and large otherwise. Let $\bar w$ be the $n$-bit string obtained from $w$ by replacing each small element of $w$ by $0$ and each large element by $1$. Let $D(\bar w)$ be the set of descents of $\bar w$, and let $A(\bar w)$ be the set of ascents of $\bar w$. It follows from $(2)$ that $$m=\sum_{d\in D(\bar w)}d-\sum_{a\in A(\bar w)}a\;.\tag{3}$$ Let $k$ be the number of $1$’s in $\bar w$; clearly $k=k_{s+1}+\dots+k_r$, so we’re done if we can show that $(3)$ counts the number of $1$’s in $\bar w$.

Note first that that the last bit of $\bar w$ is $0$. If every bit of $\bar w$ is $0$, then $m=0=k$. Otherwise let $t>0$ be the number of descents of $\bar w$, and let $d_1<\ldots<d_t$ be the descents. If the first bit of $\bar w$ is $0$, there must also be $t$ ascents, say $a_1<\ldots<a_t$, and they must alternate with the descents: $$a_1<d_1<a_2<d_2<\ldots<a_t<d_t\;.\tag{4}$$ $(4)$ also holds if the first bit of $\bar w$ is $1$, provided that in that case we set $a_1=0$. Thus, we can rewrite $(3)$ as $$m=\sum_{i=1}^t(d_i-a_i)\;.\tag{5}$$ But $d_i-a_i$ is just the number of $1$’s in the $i$-th maximal block of consecutive $1$’s, so the righthand side of $(5)$ is $k$, and we’re done.

(There may well be an easier way to do this; it’s new to me, and I was working it out as I went along.)

share|cite|improve this answer
Wow, many thanks Brian, and you're right, I think I missed some parentheses. I appreciate the details of your answer. – Nastassja Feb 17 '12 at 8:02

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.