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

On page 63 of Volume 1 of Stanley’s Enumerative Combinatorics there is a statement,

Clearly $w$ is uniquely determined by $w'$ and $w''$, and $\operatorname{inv}(w) = \operatorname{inv}(w') + \operatorname{inv}(w'')$.

Can someone explain why this is true? how is $w$ uniquely determined by $w'$ and $w''$?

Here $w$ is any permutation of the multiset $\left\{1^{a_1},\dots,m^{a_m}\right\}$; $w'$ is the permutation of $\left\{2^{a_2},\dots,m^{a_m}\right\}$ obtained by removing the $1$’s from $w$; and $w''$ is the permutation of $\left\{1^{a_1},2^{n-a_1}\right\}$ obtained from $w$ by changing every element greater than $2$ to $2$, where $n=\sum_{k=1}^ma_k$. The expression $\operatorname{inv}(w)$ designates the number of inversions of $w$, which is the number of pairs of indices $(i,j)$ with $i<j$ and $w_i>w_j$.

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

Every pair $(i,j)$ of indices of $w$ with $i<j$ (a potential inversion) is of exactly one of the following two types:

  1. neither $w_i$ nor $w_j$ equals $1$;
  2. $w_i=1$ or $w_j=1$

In case 1. the positions $i,j$ in $w$ will have corresponding positions $i',j'$ in $w'$, with $i'<j'$ where the letters $w_i$ and $w_j$ end up after removal of the letters "$1$", and since $w_i=w'_{i'}$ and $w_j=w'_{j'}$, the pair $(i,j)$ is an inversion of $w$ if and only if the pair $(i',j')$ is an inversion of $w'$. In case 2., one easily checks that $(i,j)$ is an inversion of $w$ if and only if it is an inversion of $w''$. Moreover all inversions of $w''$, which must involve one occurrence of "$2$" and one of "$1$", are also inversions of $w$ of type 2. So counting the inversions of $w$ separately for the two types, we get the numbers of inversion of $w'$ respectively of $w''$, and it follows that $\def\inv{\operatorname{inv}}\inv(w)=\inv(w')+\inv(w'')$.

To reconstruct the full multiset permutation $w$ (rather than just its set of inversions) from $w'$ and $w''$, just place the letters of $w'$, keeping their relative order, at the positions where $w''$ has a letter "$2$", and at the remaining positions retain the letter "$1$" from $w''$.

share|cite|improve this answer

$\newcommand{\inv}{\operatorname{inv}}$The permutation $w''$ of $\{1^{a_1},2^{n-a_1}\}$ tells you in which positions of $w$ the $1$’s are, and $w'$ tells you the order of the non-$1$’s in $w$; put the pieces together, and you have $w$.

As an example, suppose that $M=\big\{1^3,2^2,3^2\big\}$ and $w=\langle2,1,1,3,2,1,3\rangle$; then $w'=\langle 2,3,2,3\rangle$ and $w''=\langle 2,1,1,2,2,1,2\rangle$. From $w''$ you can see that the $1$’s of $w$ are in the second, third, and sixth positions, so $w$ has the form $\langle x,1,1,x,x,1,x\rangle$, where $x$ represents any non-$1$ entry. From $w'$ you can see that the four non-$1$ elements appear in the order $2,3,2,3$, so just slot them into the blanks in $\langle x,1,1,x,x,1,x\rangle$ to get $\langle2,1,1,3,2,1,3\rangle$, which is of course $w$.

To see that $\inv(w)=\inv(w')+\inv(w'')$, note that the inversions of $w$ can be split into two disjoint categories: those that involve a $1$ and those that don’t. The inversions of $w''$ occur in exactly the same places as those of $w$ that involve a $1$, and the inversions of $w'$ exactly match the inversions of $w$ that involve numbers greater than $1$.

share|cite|improve this answer
@Marc: It did indeed; thanks. – Brian M. Scott Dec 4 '12 at 7:38

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.