show/hide this revision's text 3 added 923 characters in body

One can define the inversion vector in the same way and the same proof goes through. Given a multiset $M$ and a multipermutation $\pi=\pi_1\cdots \pi_n$, define its inversion vector to be $i(\pi)=(i_1,i_2,\dots,i_n)$, where $$i_k=\left|\lbrace j \text{ such that } j>k \text{ and } \pi_{k}>\pi_j\rbrace\right|.$$ (notice the strict inequalities)

Theorem: Given $i(\pi)$, we can recover $\pi$.

Proof: Suppose we have determined $\pi_1,\pi_2,\dots, \pi_{k-1}$. Let $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. We know from $i_{k}$ the number of indices $j$ so that $k+1\le j\le n$ and $\pi_j<\pi_{k}$. So $\pi_{k}$ is greater than exactly $i_k$ elements of $M'$, and is therefore uniquely determined.


Notice that if your multiset is $\lbrace 1^{m_1},\dots,r^{m_r}\rbrace$, then any inversion vector still satisfies $i_k\le n-k$. But clearly not all such vectors can be achieved as the inversion vector of a permutation of $M$. Now, if one tries to write a generating function of inversion vectors, i.e. $\sum_{M} x_1^{i_1}\cdots x_n^{i_n}$ then this won't factor into $\prod P_i(x_i)$ for a general multiset. For example, if $M=\lbrace 1,1,2 \rbrace$ the generating function is $1+x_2+x_1x_2$. This implies that there cannot be a "natural" radix representation to encode these inversion vectors.

All in all, Patricia's comment gives a much quicker way to get around this problem. Just pretend your multiset is actually a set, by giving it a natural total order and then write the permutations as permutations in this new set (this is called the standard permutation corresponding to the multiset permutation).

show/hide this revision's text 2 fixed a typo

One can define the inversion vector in the same way and the same proof goes through. Given a multiset $M$ and a multipermutation $\pi=\pi_1\cdots \pi_n$, define its inversion vector to be $i(\pi)=(i_1,i_2,\dots,i_n)$, where $$i_k=\left|\lbrace j \text{ such that } j>k \text{ and } \pi_{k}>\pi_j\rbrace\right|.$$ (notice the strict inequalities)

Theorem: Given $i(\pi)$, we can recover $\pi$.

Proof: Suppose we have determined $\pi_1,\pi_2,\dots, \pi_{k-1}$. Let $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. We know from $i_{k}$ the number of indices $j$ so that $k+1\le j\le n$ and $\pi_j<\pi_{k}$. So $\pi_{k}$ is greater than exactly $\pi_k$ i_k$ elements of $M'$, and is therefore uniquely determined.

show/hide this revision's text 1

One can define the inversion vector in the same way and the same proof goes through. Given a multiset $M$ and a multipermutation $\pi=\pi_1\cdots \pi_n$, define its inversion vector to be $i(\pi)=(i_1,i_2,\dots,i_n)$, where $$i_k=\left|\lbrace j \text{ such that } j>k \text{ and } \pi_{k}>\pi_j\rbrace\right|.$$ Given $i(\pi)$, we can recover $\pi$.

Proof: Suppose we have determined $\pi_1,\pi_2,\dots, \pi_{k-1}$. Let $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. We know from $i_{k}$ the number of indices $j$ so that $k+1\le j\le n$ and $\pi_j<\pi_{k}$. So $\pi_{k}$ is greater than exactly $\pi_k$ elements of $M'$, and is therefore uniquely determined.