Las estadísticas de permutaciones aleatorias , como la estructura de ciclo de una permutación aleatoria, son de fundamental importancia en el análisis de algoritmos , especialmente de los algoritmos de clasificación, que operan sobre permutaciones aleatorias. Supongamos, por ejemplo, que estamos usando quickselect (un primo de quicksort) para seleccionar un elemento aleatorio de una permutación aleatoria. Quickselect realizará una ordenación parcial en la matriz, ya que divide la matriz de acuerdo con el pivote. Por lo tanto, una permutación estará menos desordenada después de que se haya realizado una selección rápida. La cantidad de desorden que queda puede analizarse con funciones generadoras. Estas funciones generadoras dependen fundamentalmente de las funciones generadoras de la estadística de permutación aleatoria. Por tanto, es de vital importancia calcular estas funciones generadoras.
El artículo sobre permutaciones aleatorias contiene una introducción a las permutaciones aleatorias.
La relación fundamental
Las permutaciones son conjuntos de ciclos etiquetados. Usando el caso etiquetado del teorema fundamental de Flajolet-Sedgewick y escribiendo para el conjunto de permutaciones y para el conjunto singleton, tenemos
donde hemos utilizado el hecho de que el EGF de las especies combinatorias de permutaciones (hay n ! permutaciones de n elementos) es
Esta única ecuación permite derivar una gran cantidad de estadísticas de permutación. En primer lugar, eliminando términos de, es decir, exp, podemos restringir el número de ciclos que contiene una permutación, por ejemplo, restringiendo el EGF aobtenemos permutaciones que contienen dos ciclos. En segundo lugar, tenga en cuenta que el EGF de los ciclos etiquetados, es decir, de, es
porque hay k ! / k ciclos etiquetados. Esto significa que al eliminar términos de esta función generadora, podemos restringir el tamaño de los ciclos que ocurren en una permutación y obtener un EGF de las permutaciones que contienen solo ciclos de un tamaño dado.
En lugar de eliminar y seleccionar ciclos, también se pueden poner diferentes pesos en ciclos de diferentes tamaños. Sies una función de peso que depende solo del tamaño k del ciclo y por brevedad escribimos
definir el valor de b para una permutaciónpara ser la suma de sus valores en los ciclos, entonces podemos marcar ciclos de longitud k con u b ( k ) y obtener una función generadora de dos variables
Esta es una función generadora "mixta": es una función generadora exponencial en z y una función generadora ordinaria en el parámetro secundario u. Diferenciando y evaluando en u = 1, tenemos
Ésta es la función generadora de probabilidad de la expectativa de b . En otras palabras, el coeficiente deen esta serie de potencias es el valor esperado de b en permutaciones en, dado que cada permutación se elige con la misma probabilidad .
Este artículo utiliza el operador de extracción de coeficientes [ z n ], documentado en la página para series de potencias formales .
Número de permutaciones que son involuciones
Una involución es una permutación σ de modo que σ 2 = 1 bajo composición de permutación. De ello se deduce que σ solo puede contener ciclos de uno o dos de longitud, es decir, la función generadora exponencial g ( z ) de estas permutaciones es [1]
Esto da la fórmula explícita para el número total de involuciones entre las permutaciones σ ∈ S n : [1]
Dividiendo por n ! da la probabilidad de que una permutación aleatoria sea una involución. Estos números se conocen como números de teléfono .
Número de permutaciones que son raíces m ésimas de la unidad
Esto generaliza el concepto de involución. Una m ésima raíz de la unidad es una permutación σ de modo que σ m = 1 bajo la composición de permutación. Ahora, cada vez que aplicamos σ, avanzamos un paso en paralelo a lo largo de todos sus ciclos. Un ciclo de longitud d aplicado d veces produce la permutación de identidad en d elementos ( d puntos fijos) y d es el valor más pequeño para hacerlo. Por tanto, m debe ser un múltiplo de todos los tamaños de ciclo d , es decir, los únicos ciclos posibles son aquellos cuya longitud d es un divisor de m . De ello se deduce que el EGF g ( x ) de estas permutaciones es
Cuando m = p , donde p es primo, esto se simplifica a
Número de permutaciones de orden exactamente k
Este se puede hacer mediante inversión de Möbius . Trabajando con el mismo concepto que en la entrada anterior observamos que la especie combinatoriade permutaciones cuyo orden divide k viene dado por
Traslado a funciones generadoras exponenciales obtenemos el EGF de permutaciones cuyo orden divide k , que es
Ahora podemos usar esta función generadora para contar permutaciones de orden exactamente k . Dejarser el número de permutaciones de n cuyo orden es exactamente d eel número de permutaciones en n el recuento de permutaciones cuyo orden divide k . Entonces nosotros tenemos
Supongamos que hay n personas en una fiesta, cada una de las cuales trajo un paraguas. Al final de la fiesta, todos toman un paraguas de la pila de paraguas y se van. ¿Cuál es la probabilidad de que nadie se vaya con su propio paraguas? Este problema es equivalente a contar permutaciones sin puntos fijos (llamados desarreglos ) y, por lo tanto, el EGF, donde restamos puntos fijos eliminando el término z , es
Ahora multiplicación por solo suma coeficientes, por lo que tenemos la siguiente fórmula para , el número total de trastornos:
Por lo tanto, hay sobre trastornos y la probabilidad de que una permutación aleatoria sea un trastorno es
Este resultado también puede probarse mediante inclusión-exclusión . Usando los conjuntos dónde para denotar el conjunto de permutaciones que fijan p , tenemos
Esta fórmula cuenta el número de permutaciones que tienen al menos un punto fijo. Las cardinalidades son las siguientes:
Por tanto, el número de permutaciones sin punto fijo es
o
y tenemos el reclamo.
Hay una generalización de estos números, que se conoce como números rencontres , es decir, el número de permutaciones de que contiene m puntos fijos. El EGF correspondiente se obtiene marcando ciclos de tamaño uno con la variable u , es decir, eligiendo b ( k ) igual a uno para y cero en caso contrario, lo que produce la función generadora del conjunto de permutaciones por el número de puntos fijos:
Resulta que
y por lo tanto
Esto implica inmediatamente que
para n grande, m fijo.
Orden de una permutación aleatoria
Si P es una permutación, el orden de P es el menor entero positivo n para el cuales la permutación de la identidad. Este es el mínimo común múltiplo de las longitudes de los ciclos de P .
Un teorema de Goh y Schmutz [2] establece que sies el orden esperado de una permutación aleatoria de tamaño n , entonces
donde la constante c es
Trastornos que contienen un número par e impar de ciclos
Podemos usar la misma construcción que en la sección anterior para calcular el número de trastornos que contiene un número par de ciclos y el número que contiene un número impar de ciclos. Para hacer esto, necesitamos marcar todos los ciclos y restar puntos fijos, dando
Ahora, un razonamiento muy básico muestra que el EGF de es dado por
Así tenemos
cual es
Restando de , encontramos
La diferencia de estos dos ( y ) es
Cien prisioneros
Un director de la prisión quiere hacer espacio en su prisión y está considerando liberar a cien prisioneros, liberando así cien celdas. Por lo tanto, reúne a cien prisioneros y les pide que jueguen al siguiente juego: coloca cien urnas en fila, cada una con el nombre de un prisionero, donde el nombre de cada prisionero aparece exactamente una vez. El juego se desarrolla de la siguiente manera: a cada prisionero se le permite mirar dentro de cincuenta urnas. Si no encuentra su nombre en una de las cincuenta urnas, todos los prisioneros serán ejecutados inmediatamente; de lo contrario, el juego continúa. Los presos disponen de unos instantes para decidir una estrategia, sabiendo que una vez iniciado el juego, no podrán comunicarse entre sí, marcar las urnas de ninguna forma ni mover las urnas o los nombres dentro de ellas. Al elegir urnas al azar, sus posibilidades de supervivencia son casi nulas, pero existe una estrategia que les da un 30% de posibilidades de supervivencia, asumiendo que los nombres se asignan a las urnas al azar, ¿qué es?
En primer lugar, la probabilidad de supervivencia utilizando elecciones aleatorias es
por lo que definitivamente esta no es una estrategia práctica.
La estrategia de supervivencia del 30% es considerar el contenido de las urnas como una permutación de los prisioneros y ciclos transversales. Para mantener la notación simple, asigne un número a cada preso, por ejemplo, ordenando sus nombres alfabéticamente. A partir de entonces, se puede considerar que las urnas contienen números en lugar de nombres. Ahora claramente el contenido de las urnas define una permutación. El primer prisionero abre la primera urna. Si encuentra su nombre, ha terminado y sobrevive. De lo contrario, abre la urna con el número que encontró en la primera urna. El proceso se repite: el preso abre una urna y sobrevive si encuentra su nombre, de lo contrario abre la urna con el número recién recuperado, hasta un límite de cincuenta urnas. El segundo prisionero comienza con la urna número dos, el tercero con la urna número tres, y así sucesivamente. Esta estrategia equivale precisamente a un recorrido de los ciclos de la permutación representada por las urnas. Cada prisionero comienza con la urna que lleva su número y sigue recorriendo su ciclo hasta un límite de cincuenta urnas. El número de la urna que contiene su número es la imagen previa de ese número bajo la permutación. Por tanto, los prisioneros sobreviven si todos los ciclos de la permutación contienen como máximo cincuenta elementos. Tenemos que demostrar que esta probabilidad es al menos del 30%.
Tenga en cuenta que esto supone que el alcaide elige la permutación al azar; si el alcaide anticipa esta estrategia, simplemente puede elegir una permutación con un ciclo de longitud 51. Para superar esto, los prisioneros pueden acordar de antemano una permutación aleatoria de sus nombres.
Consideramos el caso general de prisioneros y urnas que se abren. Primero calculamos la probabilidad complementaria, es decir, que haya un ciclo de más deelementos. Con esto en mente, presentamos
o
de modo que la probabilidad deseada es
porque el ciclo de más de los elementos serán necesariamente únicos. Usando el hecho de que, encontramos eso
Un resultado relacionado es que, asintóticamente, la longitud esperada del ciclo más largo es λn, donde λ es la constante de Golomb-Dickman , aproximadamente 0,62.
Este ejemplo se debe a Anna Gál y Peter Bro Miltersen; consulte el artículo de Peter Winkler para obtener más información, y vea la discusión en Les-Mathematiques.net . Consulte las referencias sobre 100 presos para obtener enlaces a estas referencias.
El cálculo anterior se puede realizar de una manera más simple y directa, como sigue: primero tenga en cuenta que una permutación de elementos contiene a lo sumo un ciclo de longitud estrictamente mayor que . Por tanto, si denotamos
luego
Para , el número de permutaciones que contienen un ciclo de longitud exactamente es
Explicación: es el número de formas de elegir el elementos que componen el ciclo; es la cantidad de formas de organizar elementos en un ciclo; yes el número de formas de permutar los elementos restantes. Aquí no hay doble recuento porque hay como máximo un ciclo de duración Cuándo . Por lo tanto,
Concluimos que
Variante del problema de los 100 prisioneros (llaves y cajas)
Existe un problema estrechamente relacionado que se ajusta bastante bien al método presentado aquí. Digamos que tiene n cajas pedidas. Cada caja contiene una clave para alguna otra caja o posiblemente ella misma dando una permutación de las claves. Se le permite seleccionar k de estos n cuadros a la vez y abrirlos simultáneamente, obteniendo acceso a k teclas. ¿Cuál es la probabilidad de que con estas claves puedas abrir todas las n casillas, donde utilizas una clave encontrada para abrir la casilla a la que pertenece y repetir?
La expresión matemática de este problema es el siguiente: recoger una permutación aleatoria de n elementos y k valores de la gama de 1 a n , también al azar, llamar a estas marcas. ¿Cuál es la probabilidad de que haya al menos una marca en cada ciclo de la permutación? La afirmación es que esta probabilidad es k / n .
Las especies de permutaciones por ciclos con algún subconjunto no vacío de cada ciclo marcado tiene la especificación
El índice en la suma interna comienza en uno porque debemos tener al menos una marca en cada ciclo.
Traduciendo la especificación a funciones generadoras obtenemos la función generadora bivariada
Esto simplifica a
o
Para extraer coeficientes de esta reescritura así
Ahora se sigue que
y por lo tanto
Dividido por para obtener
¡No necesitamos dividir por n! porquees exponencial en z .
Podemos calcular el OGF de los números de Stirling con signo para n fijo, es decir
Empezar con
cuyos rendimientos
Sumando esto, obtenemos
Usando la fórmula que involucra el logaritmo para a la izquierda, la definición de a la derecha, y el teorema del binomio , obtenemos
Comparando los coeficientes de , y usando la definición del coeficiente binomial , finalmente tenemos
un factorial en caída . El cálculo del OGF de los números de Stirling sin firmar del primer tipo funciona de manera similar.
Número esperado de ciclos de un tamaño dado m
En este problema usamos una función generadora bivariada g ( z , u ) como se describe en la introducción. El valor de b para un ciclo que no sea de tamaño m es cero y uno para un ciclo de tamaño m . Tenemos
o
Esto significa que el número esperado de ciclos de tamaño m en una permutación de longitud n menor que m es cero (obviamente). Una permutación aleatoria de longitud al menos m contiene en promedio 1 / m ciclos de longitud m . En particular, una permutación aleatoria contiene aproximadamente un punto fijo.
Por lo tanto, el OGF del número esperado de ciclos de longitud menor o igual am es
donde H m es el m ésimo número armónico . Por tanto, el número esperado de ciclos de longitud como máximo m en una permutación aleatoria es de aproximadamente ln m .
Momentos de puntos fijos
El GF mixto del conjunto de permutaciones por el número de puntos fijos es
Sea la variable aleatoria X el número de puntos fijos de una permutación aleatoria. Usando números de Stirling del segundo tipo , tenemos la siguiente fórmula para el momento m de X :
que es cero cuando y uno de lo contrario. Por tanto, sólo términos concontribuir a la suma. Esto produce
Número esperado de puntos fijos en permutación aleatoria elevado a alguna potencia k
Suponga que elige una permutación aleatoria y levántalo a algo de poder , con un entero positivo y pregunte sobre el número esperado de puntos fijos en el resultado. Denote este valor por.
Por cada divisor de un ciclo de duración se divide en puntos fijos cuando se eleva a la potencia Por lo tanto, debemos marcar estos ciclos con Para ilustrar esto, considere
Obtenemos
cual es
Una vez más, continuando como se describe en la introducción, encontramos
cual es
La conclusión es que por y hay cuatro puntos fijos en promedio.
El procedimiento general es
Una vez más continuando como antes, encontramos
Hemos demostrado que el valor de es igual a (el número de divisores de) tan pronto como Comienza en por y aumenta en uno cada vez golpea un divisor de hasta e incluyendo sí mismo.
Número esperado de ciclos de cualquier duración de una permutación aleatoria
Construimos la función generadora bivariada utilizando , dónde es uno para todos los ciclos (cada ciclo aporta uno al número total de ciclos).
Por lo tanto, el número esperado de ciclos es el número armónico, o sobre .
Número de permutaciones con un ciclo de longitud superior a n / 2
(Tenga en cuenta que la Sección Cien presos contiene exactamente el mismo problema con un cálculo muy similar, además de una prueba elemental más simple).
Una vez más, comience con la función de generación exponencial , esta vez de la clase de permutaciones según el tamaño donde los ciclos de longitud superior a están marcados con la variable :
Solo puede haber un ciclo de más de , por lo tanto, la respuesta a la pregunta viene dada por
o
cual es
El exponente de en el término siendo elevado al poder Es mas grande que y por lo tanto no tiene valor para posiblemente pueda contribuir a
De ello se deduce que la respuesta es
La suma tiene una representación alternativa que se encuentra, por ejemplo, en la OEIS OEIS : A024167 .
finalmente dando
Número esperado de transposiciones de una permutación aleatoria
Podemos usar la descomposición de ciclo disjunto de una permutación para factorizarla como un producto de transposiciones reemplazando un ciclo de longitud k por k - 1 transposiciones. Por ejemplo, el ciclo factores como . La función para ciclos es igual a y obtenemos
y
De ahí el número esperado de transposiciones es
dónde es el Número armónico . También podríamos haber obtenido esta fórmula observando que el número de transposiciones se obtiene sumando las longitudes de todos los ciclos (lo que da n ) y restando uno por cada ciclo (lo que da por la sección anterior).
Tenga en cuenta que genera de nuevo los números de Stirling sin firmar del primer tipo , pero en orden inverso. Más precisamente, tenemos
Para ver esto, tenga en cuenta que lo anterior es equivalente a
y eso
que vimos que era el EGF de los números de Stirling sin signo del primer tipo en la sección sobre permutaciones que consisten precisamente en m ciclos.
Tamaño de ciclo esperado de un elemento aleatorio
Seleccionamos un elemento q aleatorio de una permutación aleatoriay pregunte sobre el tamaño esperado del ciclo que contiene q . Aquí la función es igual a , porque un ciclo de longitud k aporta k elementos que están en ciclos de longitud k . Tenga en cuenta que, a diferencia de los cálculos anteriores, necesitamos promediar este parámetro después de extraerlo de la función generadora (dividir por n ). Tenemos
Por tanto, la duración esperada del ciclo que contiene q es
Probabilidad de que un elemento aleatorio se encuentre en un ciclo de tamaño m
Este parámetro promedio representa la probabilidad de que si nuevamente seleccionamos un elemento aleatorio de de una permutación aleatoria, el elemento se encuentra en un ciclo de tamaño m . La función es igual a por y cero en caso contrario, porque sólo contribuyen los ciclos de longitud m , es decir, m elementos que se encuentran en un ciclo de longitud m . Tenemos
De ello se deduce que la probabilidad de que un elemento aleatorio se encuentre en un ciclo de longitud m es
Probabilidad de que un subconjunto aleatorio de [ n ] se encuentre en el mismo ciclo
Seleccione un subconjunto aleatorio Q de [ n ] que contenga m elementos y una permutación aleatoria, y pregunte acerca de la probabilidad de que todos los elementos de Q se encuentren en el mismo ciclo. Este es otro parámetro medio. La función b ( k ) es igual a, porque un ciclo de longitud k contribuyesubconjuntos de tamaño m , dondepara k < m . Esto produce
Al promediar obtenemos que la probabilidad de que los elementos de Q estén en el mismo ciclo es
o
En particular, la probabilidad de que dos elementos p < q estén en el mismo ciclo es 1/2.
Número de permutaciones que contienen un número par de ciclos pares
Podemos usar el teorema fundamental de Flajolet-Sedgewick directamente y calcular estadísticas de permutación más avanzadas. (Consulte esa página para obtener una explicación de cómo se calculan los operadores que usaremos). Por ejemplo, el conjunto de permutaciones que contienen un número par de ciclos pares viene dado por
Traduciendo a funciones generadoras exponenciales (EGF), obtenemos
o
Esto simplifica a
o
Esto dice que hay una permutación de tamaño cero que contiene un número par de ciclos pares (la permutación vacía, que contiene cero ciclos de longitud uniforme), una de esas permutación de tamaño uno (el punto fijo, que también contiene cero ciclos de longitud uniforme). ), y eso para , existen tales permutaciones.
Permutaciones que son cuadrados
Considere lo que sucede cuando cuadramos una permutación. Los puntos fijos se asignan a puntos fijos. Los ciclos impares se asignan a ciclos impares en una correspondencia uno a uno, p. Ej. se convierte en . Incluso los ciclos se dividen en dos y producen un par de ciclos de la mitad del tamaño del ciclo original, p. Ej. se convierte en . Por lo tanto, las permutaciones que son cuadrados pueden contener cualquier número de ciclos impares y un número par de ciclos de tamaño dos, un número par de ciclos de tamaño cuatro, etc., y están dados por
que produce el EGF
Invariantes de ciclo impar
Los tipos de permutaciones presentados en las dos secciones anteriores, es decir, permutaciones que contienen un número par de ciclos pares y permutaciones que son cuadrados, son ejemplos de los llamados invariantes de ciclo impar , estudiados por Sung y Zhang (ver enlaces externos ). El término invariante de ciclo impar simplemente significa que la pertenencia a la respectiva clase combinatoria es independiente del tamaño y número de ciclos impares que ocurren en la permutación. De hecho, podemos probar que todos los invariantes de ciclo impar obedecen a una recurrencia simple, que derivaremos. Primero, aquí hay algunos ejemplos más de invariantes de ciclo impares.
Permutaciones donde la suma de las longitudes de los ciclos pares es seis
Esta clase tiene la especificación
y la función generadora
Los primeros valores son
Permutaciones donde todos los ciclos pares tienen la misma duración
Esta clase tiene la especificación
y la función generadora
Aquí hay un matiz semántico. Podríamos considerar que las permutaciones que no contienen ciclos pares pertenecen a esta clase, ya que cero es par . Los primeros valores son
Permutaciones donde la longitud máxima de un ciclo par es cuatro
Esta clase tiene la especificación
y la función generadora
Los primeros valores son
La recurrencia
Observe cuidadosamente cómo se construyen las especificaciones del componente de ciclo par. Es mejor pensar en ellos en términos de árboles de análisis sintáctico. Estos árboles tienen tres niveles. Los nodos en el nivel más bajo representan sumas de productos de ciclos de longitud uniforme del singleton. Los nodos del nivel medio representan restricciones del operador del conjunto. Finalmente, el nodo del nivel superior suma los productos de las contribuciones del nivel medio. Tenga en cuenta que las restricciones del operador de conjunto, cuando se aplican a una función generadora que es par, preservarán esta característica, es decir, producirán otra función generadora par. Pero todas las entradas a los operadores de conjuntos son pares, ya que surgen de ciclos de longitud uniforme. El resultado es que todas las funciones generadoras involucradas tienen la forma
dónde es una función par. Esto significa que
es incluso, también, y por lo tanto
Dejando y extrayendo coeficientes, encontramos que
que produce la recurrencia
Un problema de la competencia de Putnam de 2005
En la sección Enlaces externos aparece un enlace al sitio web del concurso de Putnam . El problema pide una prueba de que
donde la suma está por encima de todo permutaciones de , es el signo de , es decir Si es par y Si es extraño, y es el número de puntos fijos de .
Ahora el signo de es dado por
donde el producto está en todos los ciclos c de, como se explica, por ejemplo, en la página sobre permutaciones pares e impares .
Por tanto, consideramos la clase combinatoria
dónde marca uno menos la duración de un ciclo contributivo, y marca puntos fijos. Traduciendo a funciones generadoras, obtenemos
o
Ahora tenemos
y por tanto la cantidad deseada viene dada por
Haciendo el cálculo, obtenemos
o
Extrayendo coeficientes, encontramos que el coeficiente de es cero. La constante es uno, que no concuerda con la fórmula (debería ser cero). Para positivo, sin embargo, obtenemos
o
que es el resultado deseado.
Como un aparte interesante, observamos que puede utilizarse para evaluar el siguiente determinante de una matriz:
dónde . Recuerde la fórmula para el determinante:
Ahora el valor del producto a la derecha para una permutación es , donde f es el número de puntos fijos de. Por eso
cuyos rendimientos
y finalmente
La diferencia entre el número de ciclos en permutaciones pares e impares
Aquí buscamos mostrar que esta diferencia viene dada por
Recuerda que el letrero de una permutación es dado por
donde el producto varía a lo largo de los ciclos c de la composición del ciclo disjunto de.
De ello se deduce que la especie combinatoria que refleja los signos y el ciclo de recuento del conjunto de permutaciones viene dado por
donde hemos usado para marcar letreros y para el recuento de ciclos.
Traduciendo a funciones generadoras tenemos
Esto simplifica a
cual es
Ahora las dos funciones generadoras y de permutaciones pares e impares por recuento de ciclos están dadas por
y
Requerimos la cantidad
cual es
Finalmente, extrayendo coeficientes de esta función generadora, obtenemos
cual es
que es a su vez
Con esto concluye la prueba.
Ver también
Constante de Golomb-Dickman
Referencias
↑ a b Chowla, S .; Herstein, IN ; Moore, WK (1951), "Sobre recursiones conectadas con grupos simétricos. I", Canadian Journal of Mathematics , 3 : 328–334, doi : 10.4153 / CJM-1951-038-3 , MR 0041849
^Goh, William MY; Schmutz, Eric (1991). "El orden esperado de una permutación aleatoria" . Boletín de la London Mathematical Society . 23 (1): 34–42. doi : 10.1112 / blms / 23.1.34 . Archivado desde el original el 25 de febrero de 2020. URL alternativa
enlaces externos
Panholzer, Alois; Prodinger, Helmut; Riedel, Marko. "Medición del trastorno posterior a la selección rápida" (PDF) . Cite journal requiere |journal=( ayuda )
Archivo de la competencia William Lowell Putnam
Cantado, Felipe; Zhang, Yan. "Recurrencias recurrentes en el conteo de permutaciones". CiteSeerX 10.1.1.91.1088 . Cite journal requiere |journal=( ayuda )
Marko Riedel et al., La diferencia de número de ciclos de permutaciones pares e impares
Marko Riedel et al., Claves dentro de cajas cerradas, una pregunta sobre probabilidad
100 prisioneros
Anna Gál, Peter Bro Miltersen, La complejidad de la sonda celular de estructuras de datos sucintas
Varios autores, Permutaciones con ciclo> n / 2
Varios autores, una propiedad de los trastornos
Varios autores, Número esperado de puntos fijos
Peter Winkler, Siete acertijos que crees que no debes haber escuchado correctamente
Varios autores, Les-Mathematiques.net . Cent prisonniers (en francés)