¿Por qué

Question

Este es un resultado conocido, pero no puedo encontrar una prueba. ¿Por qué $$ \sum_{\sigma\en S_n}p^{\ell(\sigma)}=\frac{(1-q)(1-p^2)\cdots(1-p^n)}{(1-p)^n}? $$

Aquí $\ell(\sigma)$ es la longitud de $\sigma$, lo que es equivalente, el número de inversiones de $\sigma$.

Sé que puede contar el número de permutaciones en $n$ letras con $k$ inversiones $I_n(k)$ recursivamente por $$ I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\cdots+I_{n-1}(0) $$ Así que usted podría conseguir un cierto polinomio $$ \sum_{\sigma\en S_n}p^{\ell(\sigma)}=1+I_n(1)q+I_n(2)q^2+\cdots+q^{n(n-1)/2} $$ pero tiene que ser de un modo limpio para obtener el valor de la mano derecha?

Answer 1

Considere la posibilidad de una permutación de $S_n.$ Primero hacer una elección donde la disponibilidad de $n$ posiciones de colocar el valor de uno. En el futuro todos los elementos a la izquierda de este valor va a contribuir de una inversión. Que da a la generación de la función $$q^{n-1}+q^{n-2}+\cdots+1.$$ Having positioned one we position two and once again we have all remaining elements to the left of two will contribute an inversion. This gives the term $$q^{n-2}+q^{n-3}+\cdots+1$$ (inversions with one has been counted if indeed it participates). Continuing until we place the $n$ element we obtain the product $$\prod_{k=0}^{n-1}\left(q^{k}+p^{k-2}+\cdots+1\right) = \prod_{k=0}^{n-1} \frac{1-p^{k+1}}{1-p} = \frac{(1-p^n)(1-p^{n-1})\cdots (1-p)}{(1-p)^n}.$$

Aquí hemos clasificado las inversiones $(a,b)$ por el valor de derecho de $b$ y el plazo para $k=0$ es uno que es correcta ya que el elemento $n$ no participa en ninguna de las inversiones. En general, el elemento $b$ puede participar en la mayoría de los $n-b$ de las inversiones.

Answer 2

Deje $P_n(q)$ ser el LHS polinomio y $Q_n(q)$ ser la RHS polinomio. Claramente $P_1(q) = Q_1(q)$, e $Q_n(q)$ satisface la recurrencia $$Q_{n+1}(q) = \frac{1-q^{n+1}}{1-q} Q_n(q) = (1+q+q^2+\cdots+q^n)Q_n(q).$$

La pregunta que queda es ¿por qué $P_n$ satisface la misma recurrencia. Para ver esto, definimos $s_i \in S_n$ por la transposición $s_i = (i \quad i+1)$, que se define para todos (suficientemente grande) $n$ a través de la natural incrustaciones $S_n \hookrightarrow S_{n+1}$. Recordemos que para $\sigma \in S_n$, $\ell(\sigma)$ es de forma equivalente se define como la longitud de un mínimo representante de la descomposición de $\sigma$ como producto de la $s_i$'s.

Reclamo: El conjunto de $$C_{n+1} := \{1, s_n, s_{n-1}s_{n}, \ldots, s_1s_2\cdots s_{n}\}$$ defines a complete set of left coset representatives of $S_n \subconjunto S_{n+1}$. That is, the multiplication map $$C_{n+1} \times S_n \to S_{n+1}$$ define un bijection.

Por otra parte, afirmo que para $\omega \in C_{n+1}$ e $\sigma \in S_n$, tenemos $\ell(\omega\sigma) = \ell(\omega)+\ell(\sigma)$. Probar estos hechos, y utilizar esto para completar la prueba.