2
$\begingroup$

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 and $w_i>w_j$.

  • 0
    Page 63 in the online version. For a better reference: Proof of Proposition 1.7.1.2017-07-06

2 Answers 2

2

Every pair $(i,j)$ of indices of $w$ with $i (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' 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''$.

1

$\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$.

  • 0
    @Marc: It did indeed; thanks.2012-12-04