Vector de inversión para la permutación de multiconjunto

Question

La definición de vector de inversión para una permutación está muy bien definida. Cada permutación puede ser asignada a un vector de inversión único. ¿Existe un vector de inversión bien definido para cada permutación de multiconjunto, que mantenga tal correspondencia uno a uno? Estoy especialmente interesado en las permutaciones de multiconjuntos donde la multiplicidad de cada elemento es igual.

Pregunta adicional:

Para una permutación, un vector de inversión corresponde a un número factorico, es decir, $i_k[0,i1]$. El número decimal convertido del número factorico podría ser usado para clasificar una permutación. Parece que el vector de inversión de una permutación de multiconjunto pierde tales buenas propiedades ya que el rango de $i_k$ ya no solo depende de i. ¿O existe un sistema de numeración similar al sistema de números factoriales que corresponde al vector de inversión de una permutación de multiconjunto?

Answer 1

Se puede definir el vector de inversión de la misma manera y la misma prueba se aplica. Dado un multiconjunto $M$ y una multipermutación $\pi=\pi_1\cdots \pi_n$, define su vector de inversión como $i(\pi)=(i_1,i_2,\dots,i_n)$, donde $$i_k=\left|\lbrace j \text{ tal que } j>k \text{ y } \pi_{k}>\pi_j\rbrace\right|.$$ (observe las desigualdades estrictas)

Teorema: Dado $i(\pi)$, podemos recuperar $\pi.

Prueba: Supongamos que hemos determinado $\pi_1,\pi_2,\dots, \pi_{k-1}$. Sea $M'=M/\lbrace \pi_1,\dots, \pi_{k-1}\rbrace$. Sabemos a partir de $i_{k}$ el número de índices $j$ tal que $k+1\le j\le n$ y $\pi_j<\pi_{k}$. Entonces $\pi_{k}$ es mayor que exactamente $i_k$ elementos de $M'$, y por lo tanto está determinado de manera única.

---

Observa que si tu multiconjunto es $\lbrace 1^{m_1},\dots,r^{m_r}\rbrace$, entonces cualquier vector de inversión sigue cumpliendo $i_k\le n-k$. Pero claramente no todos los vectores de inversión pueden ser obtenidos como el vector de inversión de una permutación de $M$. Ahora, si intentamos escribir una función generadora de vectores de inversión, es decir $\sum_{M} x_1^{i_1}\cdots x_n^{i_n}$ entonces esto no se factoriza en $\prod P_i(x_i)$ para un multiconjunto general. Por ejemplo, si $M=\lbrace 1,1,2 \rbrace$ la función generadora es $1+x_2+x_1x_2$. Esto implica que no puede haber una representación de radix "natural" para codificar estos vectores de inversión.

En resumen, el comentario de Patricia ofrece una forma mucho más rápida de resolver este problema. Simplemente finge que tu multiconjunto es en realidad un conjunto, dándole un orden total natural y luego escribe las permutaciones como permutaciones en este nuevo conjunto (esto se llama la permutación estándar correspondiente a la permutación del multiconjunto).