The definition of inversion vector for permutation is very well defined. Each permutation can be mapped to a unique inversion vector. So is there a well defined inversion vector for each multiset permutation, which maintains such one-to-one correspondence? I'm particularly interested in the multiset permutations where the multiplicity of each element is equal.


Question added:


For permutation, an inversion vector corresponds to a factoradic number, i.e., $i\_k∈[0,i−1]$. The decimal number converted from the factoradic number could be used for ranking a permutation. Seems the inversion vector of a multiset permutation looses such good properties as the range of $i\_k$ no longer only depends on i ? Or is there a numeral system similar to factoradic numeral system which corresponds to the inversion vector of a multiset permutation?



inversion vector for multiset permutation
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).


