Número de permutaciones con una determinada partición de tamaños de ciclo

Question

Parte de mi demasiado complicado intento en el Google CodeJam GoroSort problema calcular el número de permutaciones con una determinada partición de ciclo de tamaños. O, equivalentemente, la probabilidad de que una partición particular del ciclo de tamaños.

Por ejemplo, ¿cuántas permutaciones de 1..10 a 5 del ciclo, un ciclo 3 y 1 de dos ciclos? O lo que es Contar(5, 3, 1, 1)?

Para aclarar, yo puedo figura el fácil casos.

• Contar(1, 1, ..., 1) = 1
• Recuento(n) = n!/n
• Recuento(n - 1, 1) = n!/(n-1) (creo que suponiendo que n-1 > n/2)

¿Cómo puedo conteo de permutaciones para el caso general?

(El concurso, pero me gustaría llenar en esta pieza, a ver si el resto de mi lógica era correcta).

Answer 1

Creo que esto es relativamente simple. Si usted está tratando de encontrar una permutación de $n$ elementos con $a_k$ ciclos de tamaño $k$, entonces el número es:

$$\frac{n!}{\prod { {a_k}! k^{a_k}}}$$

Así, en el caso de $(5,3,1,1)$, lo que da $a_5=1$, $a_3=1$, $a_1=2$, y todos los demás $a_k=0.$

Que le da un denominador de $1! 5^1 1! 3^1 2! 1^2 = 30$, y la cuenta de $10!/30 = 120960$.

Esto es relativamente fácil contar el argumento. Tome una de las $n!$ permutaciones de $\{1,...,n\}$. Lista de las permutaciones y que se rompen en bloques de tamaño adecuado en un orden fijo (es decir, ordenados.) Así que si usted comenzó con la permutación de tamaño de 10: $$(9,1,3,5,6,2,7,8,10,4)$$

Que se rompen en los ciclos del tamaño requerido, produciendo una salida de permutación:

$$(9\,1\,3\,5\,6)(2\,7\,8)(10)(4)$$ A continuación, la cuenta de cuantas veces cada permutación sale de este proceso, que es el denominador de la fórmula anterior.