10 votos

Función generadora de permutaciones en $S_n$ con $k$ ciclos.

Estuve leyendo un poco sobre la teoría de Galois, y leí que algunos programas de álgebra computacional tratan de calcular los grupos de Galois encontrando tipos de ciclos.

En fin, esto me llevó a una pregunta curiosa. Si arreglo algunos $n$ y que $c(n,k)$ por el número de permutaciones en $S_n$ con $k$ ciclos, entonces cuál es la función generadora $$ \sum_k c(n,k)x^k? $$ He buscado por ahí, y creo que es algo así como $$ \sum_k c(n,k)x^k=x(x+1)\cdots(x+n-1) $$ pero no entiendo por qué. ¿Hay alguna prueba de por qué esas expresiones son iguales? Gracias.

6voto

Tas Puntos 11

Usted está buscando permutaciones de $n$ y cada ciclo aporta un factor $x$ .

Ahora, cuando se coloca el primer elemento, sólo hay una posibilidad, se inicia un ciclo, esto da $x$ . Cuando se coloca el segundo elemento, se inicia un nuevo ciclo dando $x$ o se coloca en el ciclo del primer elemento, esto da $x+1$ Cuando se coloca el elemento $k$ o bien inicia un nuevo ciclo dando $x$ o se coloca como imagen de uno de los elementos que ya están ahí, esto da $x+k-1$ .

Así que, en total, se obtiene el producto de la derecha.

4voto

Marko Riedel Puntos 19255

Esta también puede hacerse utilizando funciones generadoras exponenciales. Empezar por la especie marcada $$\mathcal{Q} = \mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z}))$$ que representa permutaciones marcadas según el número de ciclos.

Esto produce inmediatamente la función generadora $$Q(z, u) = \exp\left(u\log\frac{1}{1-z}\right)$$ de lo que se deduce que $$\left[n\atop k\right] = n! [z^n] [u^k] \exp\left(u\log\frac{1}{1-z}\right)$$ lo que implica que $$\sum_{k=1}^n \left[n\atop k\right] x^k = n! [z^n] \exp\left(x\log\frac{1}{1-z}\right) = n! [z^n] \left(\frac{1}{1-z}\right)^x.$$ Para concluir aplique el binomio de Newton para obtener $$n! {n+x-1\choose n} = n! \frac{(x+n-1)(x+n-2)\cdots x}{n!} \\ = (x+n-1)(x+n-2)\cdots(x+1)x.$$

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