7 votos

Sobre una estadística para las permutaciones

Dada una permutación $\pi$ podemos escribir $\pi=s_{i_1} ... s_{i_l}$ como producto de transposiciones simples $s_i=(i,i+1)$ de manera mínima.

Pregunta 1: ¿Existe un nombre "oficial" para la estadística de permutación dada por la cardinalidad del conjunto $\{i_1,...,i_l \}$ ? (como la longitud de Coxeter parece ser el nombre oficial de $l$ )

Ver http://www.findstat.org/StatisticsDatabase/St000019 para esta estadística.

Pregunta 2: ¿Existe alguna referencia de que la función generadora de esta estadística de permutaciones restringida a las permutaciones que evitan 321 está dada por el triángulo de Catalán? http://oeis.org/A009766 ?

1voto

Peter Puntos 163

Para la primera parte de su pregunta, soporte no parece ser una palabra adecuada, ya que en el contexto de las permutaciones se utiliza normalmente para el conjunto de puntos no fijos. En general, una matemática soporte como ayuda al acto principal.

Para intentar definir el término, primero podemos definir el proceso que llega a la estadística:

Dejemos que $T_n$ sea el conjunto de todas las transposiciones simples no triviales en un conjunto de tamaño $n$ , digamos que $S$ .

Dejemos que $\pi$ sea una permutación de $S$ y que $$\;_\pi T_n=\left\{\{t_1,\dots t_k\}\in T_n^k:\pi\prod_\limits{i=1}^k t_i=S\right\}$$

es decir $\;_\pi T_n$ es el conjunto de conjuntos de transposiciones simples que toman $\pi$ a la identidad $S$ .

Definir:

$$\;_\pi U_n(t\in \;_\pi T_n) =\{u:u\in t\}$$

como el conjunto de elementos únicos de un conjunto $t$ y

$$_\pi U_n=\bigcup_t \;_\pi U_n(t)$$

como el conjunto de conjuntos que contienen los elementos únicos de los conjuntos de transposición simple de $\;_\pi T_n$ .

Definir $\;_\pi V_n=\{|v|:v\in \;_\pi U_n\}$ y entonces la estadística que queremos es $\min(\;_\pi V_n)$ .

Así que, cardinalidad mínima de los conjuntos identificadores de transposiciones simples para una permutación $\pi$ o tal vez, el número mínimo de transposiciones simples necesarias para devolver $\pi$ a $S$ .

La estadística real se puede calcular fácilmente creando una matriz de $n-1$ , y marcando cada celda que se cruza devolviendo un elemento en un camino recto a su posición original, y contando el número de ticks, máximo 1 por celda.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X