Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
1  
Continuing what Gjergji wrote, people often use a process called polarization to convert a multiset permutation where $m_i$ is the multiplicity of the letter $i$ for each $i$ to a permutation in $S_{\sum m_i}$ by replacing the $m_1$ copies of 1 by the numbers $1_1,1_2,\dots ,1_{m_1}$ listed in ascending order, then replacing the 2's from left to right by $2_1,2_2,\dots ,2_{m_2}$, etc. Then declare $i_j < k_l$ in your alphabet iff $i<k$ or if $i=k$ and $j<l$ so you really have a permutation of $1,2,\dots ,\sum m_i$. Then the inversion vector for permutations goes through as Gjergji described. –  Patricia Hersh Aug 1 '12 at 13:02
    
For permutation, an inversion vector corresponds to a factoradic number, i.e., $i_k\in [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? –  Kelvin Lee Aug 1 '12 at 15:02
    
I think that introducing factorial expansions is just obscuring the simple method with which one recovers a permutation from its inversion vector. It's likely one can cook up something of that sort for multisets, but I don't see any motivation to do so. –  Gjergji Zaimi Aug 1 '12 at 15:09

Your Answer

 
discard

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.