Conteo de permutaciones en $S_n$ $1,2,..,k$ todos en el mismo ciclo

Question

El número de permutaciones en $S_n$ para que la primera $k$ elementos $1,2,...,k$ están todos en el mismo ciclo puede ser demostrado (por un poco tedioso argumento) a $n!/k.$ estoy buscando menos computacional maneras de ver por qué esto es así. O para cualquier referencias/enlaces sobre este recuento.

Para mi prueba computacional supuse cada ciclo en el ciclo completo de la descomposición comienza con por lo menos su elemento, y que los ciclos se organizan en orden de menos a los elementos de izquierda a derecha. El primer ciclo, a continuación, debe tener la longitud $r$ $k \le r \le n,$ y comienza con la $1.$ son $\binom{r-1}{k-1}$ maneras de colocar el resto de los $2,3,...,k$ artículos en este primer ciclo. Cualquier zona que no han rellenado debe ser llenado de la $n-k$ elementos más allá de $k$ y después de que, con la $r$ ciclo de llenado, que se mantendrá $n-r$ elementos para ser permutada en cualquier forma. Visto de otra manera, hay $n-k$ elementos de la izquierda para rellenar tanto los puestos vacantes en la $r$ ciclo y todas las otras posiciones. Esto le da a $\binom{r-1}{k-1}\cdot (n-k)!$ formas en que el primer ciclo tiene una longitud de $r.$ Esto es que se va a sumar de a $r=k$ $n$para el conteo completo, y después de multiplicar por $k$ y la reordenación de las cosas (y la aplicación de la factorial de la versión de los coeficientes binomiales) el $n!/k$ respuesta se convirtió en el equivalente a un conocido binomio suma, en el cual uno sumas $\binom{a}{a}+\binom{a+1}{a}+ \cdots + \binom{b}{a}$ y consigue $\binom{b+1}{a+1}.$

Como se puede observar este es un poco prolijos argumento para establecer el afirmaron contar. Pero desde que salió como una simple expresión en términos de $n$ $k,$ pensé que podría haber algún modo de mirar el recuento pregunta, así como para ver el resultado de forma más simple.

Answer 1

Con $q$ el número total de elementos en el ciclo que contiene $1,2,\ldots,k$ , se obtiene la fórmula

$$\sum_{q=k}^n \frac{q!}{q} {n-k\choose q-k} (n-q)!$$

el que dice que no se $(q-1)!$ ciclos en la $q$ elementos, debemos elegir el resto de $q-k$ elementos para el ciclo de los elementos a excepción de la primera $k$ y combinar esto con cualquier permutación de los resto de los elementos. (En realidad, los podemos combinar con cualquier factorización en los ciclos de los elementos restantes, pero hay $(n-q)!$ de estos por la obvia bijection con el factorizations en los ciclos de $S_{n-q}.$)

Este es

$$\sum_{q=k}^n (p-1)! {n-k\elegir q-k} (n-p)! = \sum_{q=0}^{n-k} {n-k\elegir q} (q+k-1)! (n-k-p)!.$$

Observar que cuando multiplicamos dos exponenciales funciones de generación de las secuencias de $\{a_n\}$ $\{b_n\}$ obtenemos que

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\elegir k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

es decir, el producto de las dos funciones de generación es la exponencial la generación de la función de $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Aquí tenemos

$$A(z) = \sum_{q\ge 0} (q+k-1)! \frac{z^p}{q!} = (k-1)! \sum_{q\ge 0} {q+k-1\elegir q} z^q = (k-1)! \frac{1}{(1-z)^k}$$

y

$$B(z) = \sum_{q\ge 0} q! \frac{z^q}{q!} = \frac{1}{1-z}.$$

El resultado es, por tanto,

$$ (n-k)! [z^{n-k}] A(z) B(z) \\ = (n-k)! [z^{n-k}] (k-1)! \frac{1}{(1-z)^{k+1}} = (n-k)! (k-1)! {n\elegir k} = \frac{n!}{k}.$$