Estadísticas de permutación aleatoria

Las estadísticas de permutaciones aleatorias , como la estructura cíclica de una permutación aleatoria, son de importancia fundamental en el análisis de algoritmos , especialmente de algoritmos de ordenamiento, que operan sobre permutaciones aleatorias. Supongamos, por ejemplo, que estamos utilizando quickselect (un primo de quicksort ) para seleccionar un elemento aleatorio de una permutación aleatoria. Quickselect realizará un ordenamiento 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 quickselect. La cantidad de desorden que permanece se puede analizar con funciones generadoras. Estas funciones generadoras dependen de manera fundamental de las funciones generadoras de las estadísticas de permutación aleatoria. Por lo 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. Utilizando el caso etiquetado del teorema fundamental de Flajolet-Sedgewick y escribiendo para el conjunto de permutaciones y para el conjunto singleton, tenemos ${\displaystyle \scriptstyle {\mathcal {P}}}$ ${\displaystyle \scriptstyle {\mathcal {Z}}}$

${\displaystyle \operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}}))={\mathcal {P}}.}$

Traduciendo a funciones generadoras exponenciales (EGF), tenemos

${\displaystyle \exp \left(\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}}$

donde hemos utilizado el hecho de que el EGF de la especie combinatoria de permutaciones (hay n ! permutaciones de n elementos) es

${\displaystyle \sum _{n\geq 0}{\frac {n!}{n!}}z^{n}={\frac {1}{1-z}}.}$

Esta ecuación permite obtener una gran cantidad de estadísticas de permutación. En primer lugar, al eliminar términos de , es decir, exp, podemos restringir el número de ciclos que contiene una permutación, por ejemplo, al restringir la EGF a obtenemos permutaciones que contienen dos ciclos. En segundo lugar, observe que la 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 una EGF de las permutaciones que contienen solo ciclos de un tamaño dado. ${\displaystyle \scriptstyle \operatorname {SET} }$ ${\displaystyle \scriptstyle \operatorname {SET} _{2}}$ ${\displaystyle \scriptstyle \operatorname {CYC} ({\mathcal {Z}})}$ $${\displaystyle \sum _{k\geq 1}{\frac {(k-1)!z^{k}}{k!}}=\sum _{k\geq 1}{\frac {z^{k}}{k}}=\log {\frac {1}{1-z}}}$$

En lugar de eliminar y seleccionar ciclos, también se pueden asignar pesos diferentes a ciclos de distintos tamaños. Si es una función de peso que depende únicamente del tamaño k del ciclo y, para abreviar, escribimos ${\displaystyle b:\mathbb {N} \rightarrow \mathbb {R} }$

${\displaystyle b(\sigma )=\sum _{c\in \sigma }b(c),}$

Si definimos el valor de b para una permutación como 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 ${\displaystyle \sigma }$

${\displaystyle g(z,u)=1+\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}u^{b(\sigma )}\right){\frac {z^{n}}{n!}}=\exp \sum _{k\geq 1}u^{b(k)}{\frac {z^{k}}{k}}}$

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. Derivando y evaluando en u  = 1, tenemos

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}=\sum _{n\geq 1}\left(\sum _{\sigma \in S_{n}}b(\sigma )\right){\frac {z^{n}}{n!}}}$

Esta es la función generadora de probabilidad de la expectativa de b . En otras palabras, el coeficiente de en esta serie de potencias es el valor esperado de b en permutaciones en , dado que cada permutación se elige con la misma probabilidad . ${\displaystyle z^{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle 1/n!}$

Este artículo utiliza el operador de extracción de coeficientes [ z ⁿ ], documentado en la página de series de potencia formales .

Número de permutaciones que son involuciones

Una involución es una permutación σ tal que σ ² = 1 bajo la composición de permutaciones. De ello se deduce que σ solo puede contener ciclos de longitud uno o dos, es decir, la función generadora exponencial g ( z ) de estas permutaciones es ^[1]

${\displaystyle g(z)=\exp \left(z+{\frac {1}{2}}z^{2}\right).}$

Esto da la fórmula explícita para el número total de involuciones entre las permutaciones σ ∈  S _n : ^[1] ${\displaystyle I(n)}$

${\displaystyle I(n)=n![z^{n}]g(z)=n!\sum _{a+2b=n}{\frac {1}{a!\;2^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/2\rfloor }{\frac {1}{(n-2b)!\;2^{b}\;b!}}.}$

Dividiendo por n ! se obtiene 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 sonmetroLas raíces de la unidad

Esto generaliza el concepto de una involución. Una raíz m- ésima de la unidad es una permutación σ de modo que σ ^m = 1 bajo la composición de permutaciones. Ahora, cada vez que aplicamos σ, nos movemos un paso en paralelo a lo largo de todos sus ciclos. Un ciclo de longitud d aplicado d veces produce la permutación identidad en d elementos ( d puntos fijos) y d es el valor más pequeño que lo hace. Por lo 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 la FGE g ( x ) de estas permutaciones es

${\displaystyle g(z)=\exp \left(\sum _{d\mid m}{\frac {z^{d}}{d}}\right).}$

Cuando m = p , donde p es primo, esto se simplifica a

${\displaystyle n![z^{n}]g(z)=n!\sum _{a+pb=n}{\frac {1}{a!\;p^{b}\;b!}}=n!\sum _{b=0}^{\lfloor n/p\rfloor }{\frac {1}{(n-pb)!\;p^{b}\;b!}}.}$

Número de permutaciones de orden exactamentea

Esto se puede hacer por inversión de Möbius . Trabajando con el mismo concepto que en la entrada anterior notamos que la especie combinatoria de permutaciones cuyo orden divide a k está dada por ${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{d\mid k}\operatorname {CYC} _{=d}({\mathcal {Z}})\right).}$

Trasladándola a funciones generadoras exponenciales obtenemos la EGF de permutaciones cuyo orden divide a k , que es

${\displaystyle Q_{k}(z)=\exp \left(\sum _{d\mid k}{\frac {z^{d}}{d}}\right).}$

Ahora podemos usar esta función generadora para contar permutaciones de orden exactamente k . Sea el número de permutaciones en n cuyo orden es exactamente d y el número de permutaciones en n el recuento de permutaciones cuyo orden divide a k . Entonces tenemos ${\displaystyle p_{n,d}}$ ${\displaystyle q_{n,k}}$

${\displaystyle \sum _{d|k}p_{n,d}=q_{n,k}.}$

Por inversión de Möbius se deduce que

${\displaystyle \sum _{d|k}q_{n,d}\times \mu (k/d)=p_{n,k}.}$

Por lo tanto, tenemos el EGF

${\displaystyle Q(z)=\sum _{d\mid k}\mu (k/d)\times Q_{d}(z)=\sum _{d\mid k}\mu (k/d)\exp \left(\sum _{m\mid d}{\frac {z^{m}}{m}}\right).}$

El recuento deseado se da entonces por

${\displaystyle n![z^{n}]Q(z).}$

Esta fórmula produce, por ejemplo, para k  = 6 el EGF

${\displaystyle Q(z)={\rm {e}}^{z}-{\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/3\,z^{3}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/6\,z^{6}}}$

con la secuencia de valores comenzando en n  = 5

${\displaystyle 20,240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280,\ldots }$(secuencia A061121 en la OEIS )

Para k  = 8 obtenemos el EGF

${\displaystyle Q(z)=-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}+{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}+1/8\,z^{8}}}$

con la secuencia de valores comenzando en n  = 8

${\displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800,\ldots }$(secuencia A061122 en la OEIS )

Finalmente para k  = 12 obtenemos el EGF

${\displaystyle Q(z)={\rm {e}}^{z+1/2\,z^{2}}-{\rm {e}}^{z+1/2\,z^{2}+1/4\,z^{4}}-{\rm {e}}^{z+1/2\,z^{2}+1/3\,{z}^{3}+1/6\,z^{6}}+{\rm {e}}^{z+1/2\,z^{2}+1/3\,z^{3}+1/4\,z^{4}+1/6\,z^{6}+1/12\,z^{12}}}$

con la secuencia de valores comenzando en n  = 7

${\displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600,\ldots }$(secuencia A061125 en la OEIS )

Número de permutaciones que son alteraciones

Supongamos que hay n personas en una fiesta, cada una de las cuales trajo un paraguas. Al final de la fiesta, todos eligen un paraguas de la pila de paraguas y se van. ¿Cuál es la probabilidad de que nadie se haya ido con su propio paraguas? Este problema es equivalente a contar permutaciones sin puntos fijos (llamadas desajustes ), y por lo tanto el EGF, donde restamos los puntos fijos (ciclos de longitud 1) eliminando el término z de la relación fundamental es

${\displaystyle \exp \left(-z+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}.}$

La multiplicación por suma los coeficientes de , por lo que , el número total de trastornos, viene dado por: ${\displaystyle 1/(1-z)}$ ${\displaystyle e^{-z}}$ ${\displaystyle D(n)}$

${\displaystyle D(n)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\;\approx \;{\frac {n!}{e}}.}$

Por lo tanto, hay aproximadamente desajustes y la probabilidad de que una permutación aleatoria sea un desajuste es ${\displaystyle n!/e}$ ${\displaystyle 1/e.}$

Este resultado también puede demostrarse por inclusión-exclusión . Utilizando los conjuntos donde para denotar el conjunto de permutaciones que fijan p , tenemos ${\displaystyle A_{p}}$ ${\displaystyle {\begin{matrix}1\leq p\leq n\end{matrix}}}$

${\displaystyle \left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.}$

Esta fórmula cuenta el número de permutaciones que tienen al menos un punto fijo. Las cardinalidades son las siguientes:

${\displaystyle \left|A_{p}\right|=(n-1)!\;,\;\;\left|A_{p}\cap A_{q}\right|=(n-2)!\;,\;\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=(n-3)!\;,\;\ldots }$

Por lo tanto, el número de permutaciones sin punto fijo es

${\displaystyle n!\;\;-\;\;{n \choose 1}(n-1)!\;\;+\;\;{n \choose 2}(n-2)!\;\;-\;\;{n \choose 3}(n-3)!\;\;+\;\;\cdots \;\;\pm \;\;{n \choose n}(n-n)!}$

o

${\displaystyle n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\cdots \pm {\frac {1}{n!}}\right)=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

y tenemos el reclamo.

Existe una generalización de estos números, que se conoce como números de encuentro , es decir, el número de permutaciones de que contienen m puntos fijos. La función generadora de ecuaciones diferenciales correspondiente se obtiene marcando ciclos de tamaño uno con la variable u , es decir, eligiendo b ( k ) igual a uno en caso contrario y cero en caso contrario, lo que da como resultado la función generadora del conjunto de permutaciones por el número de puntos fijos: ${\displaystyle D(n,m)}$ ${\displaystyle [n]}$ ${\displaystyle k=1}$ ${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\exp \left(-z+uz+\sum _{k\geq 1}{\frac {z^{k}}{k}}\right)={\frac {e^{-z}}{1-z}}e^{uz}.}$

Resulta que

${\displaystyle [u^{m}]g(z,u)={\frac {e^{-z}}{1-z}}{\frac {z^{m}}{m!}}}$

y por lo tanto

${\displaystyle D(n,m)=n![z^{n}][u^{m}]g(z,u)={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}$

Esto implica inmediatamente que

${\displaystyle D(n,m)={n \choose m}D(n-m,0)\;\;{\text{ and }}\;\;{\frac {D(n,m)}{n!}}\approx {\frac {e^{-1}}{m!}}}$

para n grande, m fijo.

Orden de una permutación aleatoria

Si P es una permutación, el orden de P es el entero positivo más pequeño n para el cual es la permutación identidad. Este es el mínimo común múltiplo de las longitudes de los ciclos de P. ${\displaystyle P^{n}}$

Un teorema de Goh y Schmutz ^[2] establece que si es el orden esperado de una permutación aleatoria de tamaño n , entonces ${\displaystyle \mu _{n}}$

${\displaystyle \log \mu _{n}\sim c{\sqrt {\frac {n}{\log n}}}}$

donde la constante c es

${\displaystyle 2{\sqrt {2\int _{0}^{\infty }\log \log \left({\frac {e}{1-e^{-t}}}\right)dt}}\approx 1.1178641511899}$

Trastornos que contienen un número par y uno impar de ciclos

Podemos utilizar la misma construcción que en la sección anterior para calcular el número de desarreglos que contienen un número par de ciclos y el número que contiene un número impar de ciclos. Para ello, necesitamos marcar todos los ciclos y restar los puntos fijos, lo que da ${\displaystyle D_{0}(n)}$ ${\displaystyle D_{1}(n)}$

${\displaystyle g(z,u)=\exp \left(-uz+u\log {\frac {1}{1-z}}\right)=\exp(-uz)\left({\frac {1}{1-z}}\right)^{u}.}$

Ahora, un razonamiento muy básico muestra que el EGF de está dado por ${\displaystyle q(z)}$ ${\displaystyle D_{0}(n)}$

${\displaystyle q(z)={\frac {1}{2}}\times g(z,-1)+{\frac {1}{2}}\times g(z,1)={\frac {1}{2}}\exp(-z){\frac {1}{1-z}}+{\frac {1}{2}}\exp(z)(1-z).}$

Así pues, tenemos

${\displaystyle D_{0}(n)=n![z^{n}]q(z)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}n!{\frac {1}{n!}}-{\frac {1}{2}}n!{\frac {1}{(n-1)!}}}$

cual es

${\displaystyle {\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}+{\frac {1}{2}}(1-n)\sim {\frac {1}{2e}}n!+{\frac {1}{2}}(1-n).}$

Restando de , encontramos ${\displaystyle D_{0}(n)}$ ${\displaystyle D(n)}$

${\displaystyle D_{1}(n)={\frac {1}{2}}n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}-{\frac {1}{2}}(1-n).}$

La diferencia entre estos dos ( y ) es ${\displaystyle D_{0}(n)}$ ${\displaystyle D_{1}(n)}$ ${\displaystyle n-1.}$

Cien prisioneros

Un director de prisión quiere hacer sitio en su prisión y está considerando la posibilidad de liberar a cien presos, con lo que liberaría cien celdas. Por ello, reúne a cien presos y les pide que jueguen al siguiente juego: pone en fila cien urnas, cada una con el nombre de un preso, donde el nombre de cada preso aparece exactamente una vez. El juego se desarrolla de la siguiente manera: cada preso puede mirar dentro de cincuenta urnas. Si no encuentra su nombre en ninguna de las cincuenta urnas, todos los presos serán ejecutados inmediatamente; de ​​lo contrario, el juego continúa. Los presos tienen unos momentos para decidir una estrategia, sabiendo que una vez que el juego haya comenzado, no podrán comunicarse entre ellos, marcar las urnas de ninguna manera o mover las urnas o los nombres dentro de ellas. Al elegir las urnas al azar, sus posibilidades de supervivencia son casi nulas, pero existe una estrategia que les da un 30% de posibilidades de supervivencia, suponiendo que los nombres se asignan a las urnas al azar. ¿Cuál es?

En primer lugar, la probabilidad de supervivencia utilizando elecciones aleatorias es

${\displaystyle \left({\frac {99 \choose 49}{100 \choose 50}}\right)^{100}={\frac {1}{2^{100}}},}$

Así que definitivamente esta no es una estrategia práctica.

La estrategia de supervivencia del 30% consiste en considerar el contenido de las urnas como una permutación de los prisioneros y recorrer ciclos. Para simplificar la notación, se asigna un número a cada prisionero, 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 prisionero abre una urna y sobrevive si encuentra su nombre; de ​​lo contrario, abre la urna con el número que acaba de recuperar, 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 es exactamente equivalente 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 continúa recorriendo su ciclo hasta un límite de cincuenta urnas. El número de la urna que contiene su número es la preimagen de ese número bajo la permutación. Por lo 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%.

Obsérvese que esto supone que el director elige la permutación aleatoriamente; si el director anticipa esta estrategia, puede simplemente 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.

Consideremos el caso general de prisioneros y urnas abiertas. Primero calculamos la probabilidad complementaria, es decir, que haya un ciclo de más de elementos. Con esto en mente, presentamos ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle g(z,u)=\exp \left(z+{\frac {z^{2}}{2}}+{\frac {z^{3}}{3}}+\cdots +u{\frac {z^{n+1}}{n+1}}+u{\frac {z^{n+2}}{n+2}}+\cdots \right)}$

o

${\displaystyle {\frac {1}{1-z}}\exp \left((u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

de modo que la probabilidad deseada es

${\displaystyle [z^{2n}][u]g(z,u),}$

porque el ciclo de más de elementos será necesariamente único. Utilizando el hecho de que , encontramos que ${\displaystyle n}$ ${\displaystyle 2(n+1)>2n}$

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}][u]{\frac {1}{1-z}}\left(1+(u-1)\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)\right),}$

que produce

${\displaystyle [z^{2n}][u]g(z,u)=[z^{2n}]{\frac {1}{1-z}}\left({\frac {z^{n+1}}{n+1}}+{\frac {z^{n+2}}{n+2}}+\cdots \right)=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

Finalmente, utilizando una estimación integral como la suma de Euler-Maclaurin , o la expansión asintótica del n -ésimo número armónico , obtenemos

${\displaystyle H_{2n}-H_{n}\sim \log 2-{\frac {1}{4n}}+{\frac {1}{16n^{2}}}-{\frac {1}{128n^{4}}}+{\frac {1}{256n^{6}}}-{\frac {17}{4096n^{8}}}+\cdots ,}$

de modo que

${\displaystyle [z^{2n}][u]g(z,u)<\log 2\quad {\mbox{and}}\quad 1-[z^{2n}][u]g(z,u)>1-\log 2=0.30685281,}$

o al menos el 30%, como se afirma.

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 prisioneros para obtener enlaces a estas referencias.

El cálculo anterior se puede realizar de una manera más simple y directa, de la siguiente manera: primero observe que una permutación de elementos contiene como máximo un ciclo de longitud estrictamente mayor que . Por lo tanto, si denotamos ${\displaystyle 2n}$ ${\displaystyle n}$

${\displaystyle p_{k}=\Pr[{\mbox{there is a cycle of length }}k],}$

entonces

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}p_{k}.}$

Para , el número de permutaciones que contienen un ciclo de longitud exactamente es ${\displaystyle k>n}$ ${\displaystyle k}$

${\displaystyle {{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!.}$

Explicación: es el número de formas de elegir los elementos que componen el ciclo; es el número de formas de organizar los elementos en un ciclo; y es el número de formas de permutar los elementos restantes. No hay doble conteo aquí porque hay como máximo un ciclo de longitud cuando . Por lo tanto, ${\displaystyle {{2n} \choose k}}$ ${\displaystyle k}$ ${\displaystyle {\frac {k!}{k}}}$ ${\displaystyle k}$ ${\displaystyle (2n-k)!}$ ${\displaystyle k}$ ${\displaystyle k>n}$

${\displaystyle p_{k}={\frac {{{2n} \choose k}\cdot {\frac {k!}{k}}\cdot (2n-k)!}{(2n)!}}={\frac {1}{k}}.}$

Concluimos que

${\displaystyle \Pr[{\mbox{there is a cycle of length}}>n]=\sum _{k=n+1}^{2n}{\frac {1}{k}}=H_{2n}-H_{n}.}$

Una variación del problema de los 100 prisioneros (llaves y cajas)

Hay un problema estrechamente relacionado que se ajusta bastante bien al método presentado aquí. Digamos que tienes n cajas ordenadas. Cada caja contiene una llave para alguna otra caja o posiblemente para sí misma, dando una permutación de las llaves. Puedes seleccionar k de estas n cajas a la vez y abrirlas simultáneamente, obteniendo acceso a k llaves. ¿Cuál es la probabilidad de que usando estas llaves puedas abrir las n cajas, donde usas una llave encontrada para abrir la caja a la que pertenece y repites el proceso?

El enunciado matemático de este problema es el siguiente: se elige una permutación aleatoria de n elementos y k valores en el rango de 1 a n , también al azar, y se les llama 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 .

La especie de permutaciones por ciclos con algún subconjunto no vacío de cada ciclo marcado tiene la especificación ${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} \left(\sum _{q\geq 1}\operatorname {CYC} _{=q}({\mathcal {Z}})\times \sum _{p=1}^{q}{q \choose p}{\mathcal {U}}^{p}\right).}$

El índice de 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

${\displaystyle G(z,u)=\exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}\sum _{p=1}^{q}{q \choose p}u^{p}\right).}$

Esto se simplifica a

${\displaystyle \exp \left(\sum _{q\geq 1}{\frac {z^{q}}{q}}(u+1)^{q}-\sum _{q\geq 1}{\frac {z^{q}}{q}}\right)}$

o

${\displaystyle \exp \left(\log {\frac {1}{1-(u+1)z}}-\log {\frac {1}{1-z}}\right)={\frac {1-z}{1-(u+1)z}}.}$

Para extraer coeficientes de esta reescritura de la siguiente manera

${\displaystyle (1-z)\sum _{q\geq 0}(u+1)^{q}z^{q}.}$

De ello se deduce ahora que

${\displaystyle [z^{n}]G(z,u)=(u+1)^{n}-(u+1)^{n-1}}$

y por lo tanto

${\displaystyle [u^{k}][z^{n}]G(z,u)={n \choose k}-{n-1 \choose k}.}$

Dividir por para obtener ${\displaystyle {n \choose k}}$

${\displaystyle 1-{\frac {(n-1)!}{k!(n-1-k)!}}{\frac {k!(n-k)!}{n!}}=1-{\frac {n-k}{n}}={\frac {k}{n}}.}$

No necesitamos dividir por n! porque es exponencial en z . ${\displaystyle G(z,u)}$

Número de permutaciones que contienenmetrociclos

Aplicando el teorema fundamental de Flajolet-Sedgewick , es decir, el teorema de enumeración etiquetado con , al conjunto ${\displaystyle G=S_{m}}$

${\displaystyle \operatorname {SET} _{=m}(\operatorname {CYC} ({\mathcal {Z}}))}$

obtenemos la función generadora

${\displaystyle g_{m}(z)={\frac {1}{|S_{m}|}}\left(\log {\frac {1}{1-z}}\right)^{m}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m}.}$

El término

${\displaystyle (-1)^{n+m}n!\;[z^{n}]g_{m}(z)=s(n,m)}$

produce los números de Stirling con signo del primer tipo , y es la EGF de los números de Stirling sin signo del primer tipo, es decir ${\displaystyle g_{m}(z)}$

${\displaystyle n![z^{n}]g_{m}(z)=\left[{\begin{matrix}n\\m\end{matrix}}\right].}$

Podemos calcular el OGF de los números de Stirling con signo para n fijo, es decir

${\displaystyle s_{n}(w)=\sum _{m=0}^{n}s(n,m)w^{m}.}$

Empezar con

${\displaystyle g_{m}(z)=\sum _{n\geq m}{\frac {(-1)^{n+m}}{n!}}s(n,m)z^{n}}$

que produce

${\displaystyle (-1)^{m}g_{m}(z)w^{m}=\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}.}$

Sumando esto, obtenemos

${\displaystyle \sum _{m\geq 0}(-1)^{m}g_{m}(z)w^{m}=\sum _{m\geq 0}\sum _{n\geq m}{\frac {(-1)^{n}}{n!}}s(n,m)w^{m}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}z^{n}\sum _{m=0}^{n}s(n,m)w^{m}.}$

Utilizando la fórmula que involucra el logaritmo de a la izquierda, la definición de a la derecha y el teorema binomial , obtenemos ${\displaystyle g_{m}(z)}$ ${\displaystyle s_{n}(w)}$

${\displaystyle (1-z)^{w}=\sum _{n\geq 0}{w \choose n}(-1)^{n}z^{n}=\sum _{n\geq 0}{\frac {(-1)^{n}}{n!}}s_{n}(w)z^{n}.}$

Comparando los coeficientes de , y utilizando la definición del coeficiente binomial , finalmente tenemos ${\displaystyle z^{n}}$

${\displaystyle s_{n}(w)=w\;(w-1)\;(w-2)\;\cdots \;(w-(n-1))=(w)_{n},}$

un factorial descendente . El cálculo del OGF de los números de Stirling sin signo de primera especie funciona de manera similar.

Número esperado de ciclos de un tamaño determinadometro

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 es de tamaño m es cero, y uno para un ciclo de tamaño m . Tenemos

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z^{m}}{m}}}$

o

${\displaystyle {\frac {1}{m}}z^{m}\;+\;{\frac {1}{m}}z^{m+1}\;+\;{\frac {1}{m}}z^{m+2}\;+\;\cdots }$

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.

El OGF del número esperado de ciclos de longitud menor o igual a m es por lo tanto

${\displaystyle {\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}{\mbox{ and }}[z^{n}]{\frac {1}{1-z}}\sum _{k=1}^{m}{\frac {z^{k}}{k}}=H_{m}{\mbox{ for }}n\geq m}$

donde H _m es el m -ésimo número armónico . Por lo tanto, el número esperado de ciclos de longitud como máximo m en una permutación aleatoria es aproximadamente ln  m .

Momentos de puntos fijos

El GF mixto del conjunto de permutaciones por el número de puntos fijos es ${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\exp \left(-z+uz+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp(-z+uz).}$

Sea la variable aleatoria X el número de puntos fijos de una permutación aleatoria. Utilizando números de Stirling de segunda especie , tenemos la siguiente fórmula para el momento m de X :

${\displaystyle E(X^{m})=E\left(\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}(X)_{k}\right)=\sum _{k=0}^{m}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}E((X)_{k}),}$

donde es un factorial descendente . Utilizando , tenemos ${\displaystyle (X)_{k}}$ ${\displaystyle g(z,u)}$

${\displaystyle E((X)_{k})=[z^{n}]\left({\frac {d}{du}}\right)^{k}g(z,u){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}}\exp(-z+uz){\Bigg |}_{u=1}=[z^{n}]{\frac {z^{k}}{1-z}},}$

que es cero cuando , y uno en caso contrario. Por lo tanto, solo los términos con contribuyen a la suma. Esto da ${\displaystyle k>n}$ ${\displaystyle k<=n}$

${\displaystyle E(X^{m})=\sum _{k=0}^{n}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}.}$

Número esperado de puntos fijos en una permutación aleatoria elevado a alguna potenciaa

Supongamos que se elige una permutación aleatoria y se la eleva a una determinada potencia con un entero positivo y se pregunta cuál es la cantidad esperada de puntos fijos en el resultado. Denotemos este valor con . ${\displaystyle \sigma }$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle E[F_{k}]}$

Para cada divisor de un ciclo de longitud se divide en puntos fijos cuando se eleva a la potencia Por lo tanto, necesitamos marcar estos ciclos con Para ilustrar esto, considere ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle k.}$ ${\displaystyle u^{d}.}$ ${\displaystyle E[F_{6}].}$

Nosotros lo conseguimos

${\displaystyle g(z,u)=\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}+\log {\frac {1}{1-z}}\right)}$

cual es

${\displaystyle {\frac {1}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right).}$

Una vez más, continuando como se describe en la introducción, encontramos

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}\exp \left(uz-z+u^{2}{\frac {z^{2}}{2}}-{\frac {z^{2}}{2}}+u^{3}{\frac {z^{3}}{3}}-{\frac {z^{3}}{3}}+u^{6}{\frac {z^{6}}{6}}-{\frac {z^{6}}{6}}\right)\right|_{u=1}}$

cual es

${\displaystyle {\frac {z+z^{2}+z^{3}+z^{6}}{1-z}}.}$

La conclusión es que para y hay cuatro puntos fijos en promedio. ${\displaystyle E[F_{6}]=4}$ ${\displaystyle n\geq 6}$

El procedimiento general es

${\displaystyle g(z,u)=\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)+\log {\frac {1}{1-z}}\right)={\frac {1}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right).}$

Una vez más, continuando como antes, encontramos

${\displaystyle \left.{\frac {\partial }{\partial u}}g(z,u)\right|_{u=1}=\left.{\frac {\sum _{d\mid k}z^{d}}{1-z}}\exp \left(\sum _{d\mid k}\left(u^{d}{\frac {z^{d}}{d}}-{\frac {z^{d}}{d}}\right)\right)\right|_{u=1}={\frac {\sum _{d\mid k}z^{d}}{1-z}}.}$

Hemos demostrado que el valor de es igual a (el número de divisores de ) tan pronto como comienza en para y aumenta en uno cada vez que llega a un divisor de hasta e incluido él mismo. ${\displaystyle E[F_{k}]}$ ${\displaystyle \tau (k)}$ ${\displaystyle k}$ ${\displaystyle n\geq k.}$ ${\displaystyle 1}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$

Número esperado de ciclos de cualquier longitud de una permutación aleatoria

Construimos la función generadora bivariada usando , donde es uno para todos los ciclos (cada ciclo contribuye con uno al número total de ciclos). ${\displaystyle g(z,u)}$ ${\displaystyle b(k)}$ ${\displaystyle b(k)}$

Tenga en cuenta que tiene la forma cerrada ${\displaystyle g(z,u)}$

${\displaystyle g(z,u)=\left({\frac {1}{1-z}}\right)^{u}}$

y genera los números de Stirling sin signo del primer tipo .

Tenemos

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\sum _{k\geq 1}{\frac {z^{k}}{k}}={\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

Por lo tanto, el número esperado de ciclos es el número armónico , o aproximadamente . ${\displaystyle H_{n}}$ ${\displaystyle \log n}$

Número de permutaciones con un ciclo de longitud mayor quenorte/2

(Nótese que la Sección Cien prisioneros contiene exactamente el mismo problema con un cálculo muy similar, además de una prueba elemental más simple.)

Una vez más, comenzamos con la función generadora exponencial , esta vez de la clase de permutaciones según tamaño donde los ciclos de longitud mayor que están marcados con la variable : ${\displaystyle g(z,u)}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle n/2}$ ${\displaystyle u}$

${\displaystyle g(z,u)=\exp \left(u\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}+\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right).}$

Sólo puede haber un ciclo de longitud mayor que , por lo tanto la respuesta a la pregunta está dada por ${\displaystyle {\frac {n}{2}}}$

${\displaystyle n![uz^{n}]g(z,u)=n![z^{n}]\exp \left(\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

o

${\displaystyle n![z^{n}]\exp \left(\log {\frac {1}{1-z}}-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}}$

cual es

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\exp \left(-\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n![z^{n}]{\frac {1}{1-z}}\sum _{m=0}^{\infty }{\frac {(-1)^{m}}{m!}}\left(\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}\right)^{m+1}}$

El exponente de en el término que se eleva a la potencia es mayor que y, por lo tanto, ningún valor de puede contribuir a ${\displaystyle z}$ ${\displaystyle m+1}$ ${\displaystyle \lfloor {\frac {n}{2}}\rfloor }$ ${\displaystyle m>0}$ ${\displaystyle [z^{n}].}$

De ello se deduce que la respuesta es

${\displaystyle n![z^{n}]{\frac {1}{1-z}}\sum _{k>\lfloor {\frac {n}{2}}\rfloor }^{\infty }{\frac {z^{k}}{k}}=n!\sum _{k=\lfloor {\frac {n}{2}}\rfloor +1}^{n}{\frac {1}{k}}.}$

La suma tiene una representación alternativa que se encuentra, por ejemplo, en la OEIS OEIS : A024167 .

${\displaystyle \sum _{k=1}^{n}{\frac {1}{k}}-\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{k}}=\sum _{k=1}^{n}{\frac {1}{k}}-2\sum _{k=1}^{\lfloor {\frac {n}{2}}\rfloor }{\frac {1}{2k}}=\sum _{k=1 \atop k\;{\text{even}}}^{n}(1-2){\frac {1}{k}}+\sum _{k=1 \atop k\;{\text{odd}}}^{n}{\frac {1}{k}}}$

finalmente dando

${\displaystyle n!\sum _{k=1}^{n}{\frac {(-1)^{k+1}}{k}}\sim n!\log 2.}$

Número esperado de transposiciones de una permutación aleatoria

Podemos utilizar la descomposición en ciclos disjuntos 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 se factoriza como . La función para ciclos es igual a y obtenemos ${\displaystyle (1\;2\;34)}$ ${\displaystyle (1\;2)\;(2\;3)\;(3\;4)}$ ${\displaystyle b(k)}$ ${\displaystyle k-1}$

${\displaystyle g(z,u)=\left({\frac {1}{1-uz}}\right)^{1/u}}$

y

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}(k-1){\frac {z^{k}}{k}}={\frac {z}{(1-z)^{2}}}-{\frac {1}{1-z}}\log {\frac {1}{1-z}}.}$

Por lo tanto, el número esperado de transposiciones es ${\displaystyle T(n)}$

${\displaystyle T(n)=n-H_{n}}$

donde es el número armónico . También podríamos haber obtenido esta fórmula notando 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). ${\displaystyle H_{n}}$ ${\displaystyle n^{th}}$ ${\displaystyle \log n}$

Nótese que nuevamente se generan los números Stirling sin signo del primer tipo , pero en orden inverso. Más precisamente, tenemos ${\displaystyle g(z,u)}$

${\displaystyle (-1)^{m}n!\;[z^{n}][u^{m}]g(z,u)=\left[{\begin{matrix}n\\n-m\end{matrix}}\right]}$

Para ver esto, tenga en cuenta que lo anterior es equivalente a

${\displaystyle (-1)^{n+m}n!\;[z^{n}][u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=\left[{\begin{matrix}n\\m\end{matrix}}\right]}$

Y eso

${\displaystyle [u^{m}]g(z,u)|_{u=1/u}|_{z=uz}=[u^{m}]\left({\frac {1}{1-z}}\right)^{u}={\frac {1}{m!}}\left(\log {\frac {1}{1-z}}\right)^{m},}$

que vimos que era el EGF de los números de Stirling sin signo del primer tipo en la sección sobre permutaciones que constan de precisamente m ciclos.

Tamaño de ciclo esperado de un elemento aleatorio

Seleccionamos un elemento aleatorio q de una permutación aleatoria y preguntamos por el tamaño esperado del ciclo que contiene a 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 . Nótese 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 ${\displaystyle \sigma }$ ${\displaystyle b(k)}$ ${\displaystyle k^{2}}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}k^{2}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {z}{(1-z)^{2}}}={\frac {z}{(1-z)^{3}}}.}$

Por lo tanto, la longitud esperada del ciclo que contiene q es

${\displaystyle {\frac {1}{n}}[z^{n}]{\frac {z}{(1-z)^{3}}}={\frac {1}{n}}{\frac {1}{2}}n(n+1)={\frac {1}{2}}(n+1).}$

Probabilidad de que un elemento aleatorio se encuentre en un ciclo de tamañometro

Este parámetro promedio representa la probabilidad de que si seleccionamos nuevamente un elemento aleatorio de una permutación aleatoria, el elemento se encuentre en un ciclo de tamaño m . La función es igual a para y cero en caso contrario, porque solo contribuyen los ciclos de longitud m , es decir, m elementos que se encuentran en un ciclo de longitud m . Tenemos ${\displaystyle [n]}$ ${\displaystyle b(k)}$ ${\displaystyle m}$ ${\displaystyle m=k}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq 1}b(k){\frac {z^{k}}{k}}={\frac {1}{1-z}}\;m\;{\frac {z^{m}}{m}}={\frac {z^{m}}{1-z}}.}$

De ello se deduce que la probabilidad de que un elemento aleatorio se encuentre en un ciclo de longitud m es

${\displaystyle {\frac {1}{n}}[z^{n}]{\frac {z^{m}}{1-z}}={\begin{cases}{\frac {1}{n}},&{\mbox{if }}n\geq m\\0,&{\mbox{otherwise.}}\end{cases}}}$

Probabilidad de que un subconjunto aleatorio de [norte] se encuentra en el mismo ciclo

Seleccione un subconjunto aleatorio Q de [ n ] que contenga m elementos y una permutación aleatoria, y pregunte por la probabilidad de que todos los elementos de Q se encuentren en el mismo ciclo. Este es otro parámetro promedio. La función b ( k ) es igual a , porque un ciclo de longitud k contribuye con subconjuntos de tamaño m , donde para k < m . Esto da como resultado ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$ ${\displaystyle {\begin{matrix}{k \choose m}\end{matrix}}}$ ${\displaystyle {\begin{matrix}{k \choose m}=0\end{matrix}}}$

${\displaystyle {\frac {\partial }{\partial u}}g(z,u){\Bigg |}_{u=1}={\frac {1}{1-z}}\sum _{k\geq m}{k \choose m}{\frac {z^{k}}{k}}={\frac {1}{1-z}}{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m}}}={\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}.}$

Promediando obtenemos que la probabilidad de que los elementos de Q estén en el mismo ciclo es

${\displaystyle {n \choose m}^{-1}[z^{n}]{\frac {1}{m}}{\frac {z^{m}}{(1-z)^{m+1}}}={n \choose m}^{-1}{\frac {1}{m}}[z^{n-m}]{\frac {1}{(1-z)^{m+1}}}}$

o

${\displaystyle {\frac {1}{m}}{n \choose m}^{-1}{(n-m)\;+\;m \choose m}={\frac {1}{m}}.}$

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 utilizar 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 utilizaremos). Por ejemplo, el conjunto de permutaciones que contiene un número par de ciclos pares está dado por

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{\operatorname {even} }({\mathcal {Z}})).}$

Traduciendo a funciones generadoras exponenciales (EGF), obtenemos

${\displaystyle \exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\cosh \left({\frac {1}{2}}\log {\frac {1}{1-z^{2}}}\right)}$

o

${\displaystyle {\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}+\log {\frac {1}{1-z^{2}}}\right)\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\left(\log {\frac {1+z}{1-z}}-\log {\frac {1}{1-z^{2}}}\right)\right).}$

Esto se simplifica a

${\displaystyle {\frac {1}{2}}\exp \left({\frac {1}{2}}\log {\frac {1}{(1-z)^{2}}}\right)+{\frac {1}{2}}\exp \left({\frac {1}{2}}\log(1+z)^{2}\right)}$

o

${\displaystyle {\frac {1}{2}}{\frac {1}{1-z}}+{\frac {1}{2}}(1+z)=1+z+{\frac {1}{2}}{\frac {z^{2}}{1-z}}.}$

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 par), una permutación de tamaño uno (el punto fijo, que también contiene cero ciclos de longitud par), y que para , existen tales permutaciones. ${\displaystyle n\geq 2}$ ${\displaystyle n!/2}$

Permutaciones que son cuadrados

Considere lo que sucede cuando elevamos al cuadrado 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 . Los ciclos pares 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 dadas por ${\displaystyle (1\;8\;9\;11\;13)}$ ${\displaystyle (1\;9\;13\;8\;11)}$ ${\displaystyle (5\;13\;6\;9)}$ ${\displaystyle (5\;6)\;(9\;13)}$

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=2}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=4}({\mathcal {Z}}))\operatorname {SET} _{\operatorname {even} }(\operatorname {CYC} _{=6}({\mathcal {Z}}))\cdots }$

que produce el EGF

${\displaystyle \exp \left({\frac {1}{2}}\log {\frac {1+z}{1-z}}\right)\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}={\sqrt {\frac {1+z}{1-z}}}\prod _{m\geq 1}\cosh {\frac {z^{2m}}{2m}}.}$

Invariantes de ciclo impar

Los tipos de permutaciones presentados en las dos secciones anteriores, es decir, las permutaciones que contienen un número par de ciclos pares y las 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 clase combinatoria respectiva es independiente del tamaño y número de ciclos impares que ocurren en la permutación. De hecho, podemos demostrar 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 impar.

Permutaciones donde la suma de las longitudes de los ciclos pares es seis

Esta clase tiene la especificación

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{=3}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {CYC} _{=2}({\mathcal {Z}})\operatorname {CYC} _{=4}({\mathcal {Z}})+\operatorname {CYC} _{=6}({\mathcal {Z}})\right)}$

y la función generadora

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\left({\frac {1}{6}}\left({\frac {z^{2}}{2}}\right)^{3}+{\frac {z^{2}}{2}}{\frac {z^{4}}{4}}+{\frac {z^{6}}{6}}\right)={\frac {5}{16}}z^{6}{\sqrt {\frac {1+z}{1-z}}}.}$

Los primeros valores son

${\displaystyle 0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500,\ldots }$

Permutaciones donde todos los ciclos pares tienen la misma longitud

Esta clase tiene la especificación

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\left(\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=2}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=4}({\mathcal {Z}}))+\operatorname {SET} _{\geq 1}(\operatorname {CYC} _{=6}({\mathcal {Z}}))+\cdots \right)}$

y la función generadora

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\left(\exp \left({\frac {z^{2}}{2}}\right)-1\,+\,\exp \left({\frac {z^{4}}{4}}\right)-1\,+\,\exp \left({\frac {z^{6}}{6}}\right)-1\,+\,\cdots \right).}$

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

${\displaystyle 0,1,3,15,75,405,2835,22155,199395,1828575,\ldots }$

Permutaciones donde la longitud máxima de un ciclo par es cuatro

Esta clase tiene la especificación

${\displaystyle \operatorname {SET} (\operatorname {CYC} _{\operatorname {odd} }({\mathcal {Z}}))\operatorname {SET} (\operatorname {CYC} _{=2}({\mathcal {Z}})+\operatorname {CYC} _{=4}({\mathcal {Z}}))}$

y la función generadora

${\displaystyle {\sqrt {\frac {1+z}{1-z}}}\exp \left({\frac {z^{2}}{2}}+{\frac {z^{4}}{4}}\right).}$

Los primeros valores son

${\displaystyle 1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640,\ldots }$

La recurrencia

Observe cuidadosamente cómo se construyen las especificaciones del componente de ciclo par. Es mejor pensar en ellas 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 par del singleton . Los nodos en el nivel medio representan restricciones del operador de conjunto. Finalmente, el nodo en el nivel superior suma productos de 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, conservarán esta característica, es decir, producirán otra función generadora par. Pero todas las entradas a los operadores de conjunto son pares ya que surgen de ciclos de longitud par. El resultado es que todas las funciones generadoras involucradas tienen la forma ${\displaystyle {\mathcal {Z}}}$

${\displaystyle g(z)=h(z){\sqrt {\frac {1+z}{1-z}}},}$

donde es una función par. Esto significa que ${\displaystyle h(z)}$

${\displaystyle {\frac {1}{1+z}}\;g(z)=h(z)\;{\frac {1}{\sqrt {1-z^{2}}}}}$

es par, también, y por lo tanto

${\displaystyle {\frac {1}{1+z}}\;g(z)={\frac {1}{1-z}}\;g(-z)\quad {\mbox{ or }}\quad (1-z)\;g(z)=(1+z)\;g(-z).}$

Dejando y extrayendo coeficientes, encontramos que ${\textstyle g_{n}=n![z^{n}]g(z)}$

${\displaystyle {\frac {g_{2m+1}}{(2m+1)!}}-{\frac {g_{2m}}{(2m)!}}=-{\frac {g_{2m+1}}{(2m+1)!}}+{\frac {g_{2m}}{(2m)!}}\quad {\mbox{ or }}\quad 2{\frac {g_{2m+1}}{(2m+1)!}}=2{\frac {g_{2m}}{(2m)!}}}$

Lo que produce la recurrencia

${\displaystyle g_{2m+1}=(2m+1)g_{2m}\,.}$

Un problema de la competición Putnam de 2005

En la sección Enlaces externos aparece un enlace al sitio web de la competencia de Putnam . El problema pide una prueba de que

${\displaystyle \sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}=(-1)^{n+1}{\frac {n}{n+1}},}$

donde la suma es sobre todas las permutaciones de , es el signo de , es decir, si es par y si es impar, y es el número de puntos fijos de . ${\displaystyle n!}$ ${\displaystyle [n]}$ ${\displaystyle \sigma (\pi )}$ ${\displaystyle \pi }$ ${\displaystyle \sigma (\pi )=1}$ ${\displaystyle \pi }$ ${\displaystyle \sigma (\pi )=-1}$ ${\displaystyle \pi }$ ${\displaystyle \nu (\pi )}$ ${\displaystyle \pi }$

Ahora el signo de viene dado por ${\displaystyle \pi }$

${\displaystyle \sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1},}$

donde el producto es sobre todos los ciclos c de , como se explica, por ejemplo, en la página sobre permutaciones pares e impares . ${\displaystyle \pi }$

Por lo tanto, consideramos la clase combinatoria

${\displaystyle \operatorname {SET} (-{\mathcal {Z}}+{\mathcal {V}}{\mathcal {Z}}+\operatorname {CYC} _{=1}({\mathcal {Z}})+{\mathcal {U}}\operatorname {CYC} _{=2}({\mathcal {Z}})+{\mathcal {U}}^{2}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}\operatorname {CYC} _{=4}({\mathcal {Z}})+\cdots )}$

donde marca uno menos la longitud de un ciclo contribuyente y marca puntos fijos. Traduciendo a funciones generadoras, obtenemos ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {V}}}$

${\displaystyle g(z,u,v)=\exp \left(-z+vz+\sum _{k\geq 1}u^{k-1}{\frac {z^{k}}{k}}\right)}$

o

${\displaystyle \exp \left(-z+vz+{\frac {1}{u}}\log {\frac {1}{1-uz}}\right)=\exp(-z+vz)\left({\frac {1}{1-uz}}\right)^{1/u}.}$

Ahora tenemos

${\displaystyle n![z^{n}]g(z,-1,v)=n![z^{n}]\exp(-z+vz)(1+z)=\sum _{\pi \in S_{n}}\sigma (\pi )v^{\nu (\pi )}}$

y por lo tanto la cantidad deseada viene dada por

${\displaystyle n![z^{n}]\int _{0}^{1}g(z,-1,v)dv=\sum _{\pi \in S_{n}}{\frac {\sigma (\pi )}{\nu (\pi )+1}}.}$

Haciendo el cálculo, obtenemos

${\displaystyle \int _{0}^{1}g(z,-1,v)dv=\exp(-z)(1+z)\left({\frac {1}{z}}\exp(z)-{\frac {1}{z}}\right)}$

o

${\displaystyle \left({\frac {1}{z}}+1\right)\left(1-\exp(-z)\right)={\frac {1}{z}}+1-\exp(-z)-{\frac {1}{z}}\exp(-z).}$

Extrayendo los coeficientes, encontramos que el coeficiente de es cero. La constante es uno, lo que no concuerda con la fórmula (debería ser cero). Sin embargo, para positivo, obtenemos ${\displaystyle 1/z}$ ${\displaystyle n}$

${\displaystyle n![z^{n}]\left(-\exp(-z)-{\frac {1}{z}}\exp(-z)\right)=n!\left(-(-1)^{n}{\frac {1}{n!}}-(-1)^{n+1}{\frac {1}{(n+1)!}}\right)}$

o

${\displaystyle (-1)^{n+1}\left(1-{\frac {1}{n+1}}\right)=(-1)^{n+1}{\frac {n}{n+1}},}$

Cuál es el resultado deseado.

Como dato interesante, observamos que se puede utilizar para evaluar el siguiente determinante de una matriz: ${\displaystyle g(z,u,v)}$ ${\displaystyle n\times n}$

${\displaystyle d(n)=\det(A_{n})={\begin{vmatrix}a&&b&&b&&\cdots &&b\\b&&a&&b&&\cdots &&b\\b&&b&&a&&\cdots &&b\\\vdots &&\vdots &&\vdots &&\ddots &&\vdots \\b&&b&&b&&\cdots &&a\end{vmatrix}}.}$

donde . Recordemos la fórmula para el determinante: ${\displaystyle a,b\neq 0}$

${\displaystyle \det(A)=\sum _{\pi \in S_{n}}\sigma (\pi )\prod _{i=1}^{n}A_{i,\pi (i)}.}$

Ahora bien, el valor del producto de la derecha para una permutación es , donde f es el número de puntos fijos de . Por lo tanto ${\displaystyle \pi }$ ${\displaystyle a^{f}b^{n-f}}$ ${\displaystyle \pi }$

${\displaystyle d(n)=b^{n}n![z^{n}]g\left(z,-1,{\frac {a}{b}}\right)=b^{n}n![z^{n}]\exp \left({\frac {a-b}{b}}z\right)(1+z)}$

que produce

${\displaystyle b^{n}\left({\frac {a-b}{b}}\right)^{n}+b^{n}n\left({\frac {a-b}{b}}\right)^{n-1}=(a-b)^{n}+nb(a-b)^{n-1}}$

Y finalmente

${\displaystyle d(n)=(a+(n-1)b)(a-b)^{n-1}\,.}$

La diferencia entre el número de ciclos en permutaciones pares e impares

Aquí buscamos demostrar que esta diferencia está dada por

${\displaystyle (-1)^{n}(n-2)!}$

Recordemos que el signo de una permutación viene dado por ${\displaystyle \sigma (\pi )}$ ${\displaystyle \pi }$

${\displaystyle \sigma (\pi )=\prod _{c\in \pi }(-1)^{|c|-1}}$

donde el producto varía a lo largo de los ciclos c a partir de la composición del ciclo disjunto de . ${\displaystyle \pi }$

De ello se deduce que la especie combinatoria que refleja los signos y el recuento de ciclos del conjunto de permutaciones está dada por ${\displaystyle {\mathcal {Q}}}$

${\displaystyle {\mathcal {Q}}=\operatorname {SET} ({\mathcal {V}}\operatorname {CYC} _{1}({\mathcal {Z}})+{\mathcal {U}}{\mathcal {V}}\operatorname {CYC} _{=2}({\mathcal {Z}}))+{\mathcal {U}}^{2}{\mathcal {V}}\operatorname {CYC} _{=3}({\mathcal {Z}})+{\mathcal {U}}^{3}{\mathcal {V}}\operatorname {CYC} _{=4}({\mathcal {Z}})+{\mathcal {U}}^{4}{\mathcal {V}}\operatorname {CYC} _{=5}({\mathcal {Z}})+\cdots )}$

donde hemos utilizado para marcar señales y para el conteo cíclico. ${\displaystyle {\mathcal {U}}}$ ${\displaystyle {\mathcal {V}}}$

Traduciendo a funciones generadoras tenemos

${\displaystyle Q(z,u,v)=\exp \left(v{\frac {z}{1}}+vu{\frac {z^{2}}{2}}+vu^{2}{\frac {z^{3}}{3}}+vu^{3}{\frac {z^{4}}{4}}+vu^{4}{\frac {z^{5}}{5}}+\cdots \right).}$

Esto se simplifica a

${\displaystyle Q(z,u,v)=\exp \left({\frac {v}{u}}\left({\frac {zu}{1}}+{\frac {z^{2}u^{2}}{2}}+{\frac {z^{3}u^{3}}{3}}+{\frac {z^{4}u^{4}}{4}}+{\frac {z^{5}u^{5}}{5}}+\cdots \right)\right)}$

cual es

${\displaystyle \exp \left({\frac {v}{u}}\log {\frac {1}{1-uz}}\right)=\left({\frac {1}{1-uz}}\right)^{\frac {v}{u}}.}$

Ahora las dos funciones generadoras y de permutaciones pares e impares por conteo de ciclos están dadas por ${\displaystyle Q_{1}(z,v)}$ ${\displaystyle Q_{2}(z,v)}$

${\displaystyle Q_{1}(z,v)={\frac {1}{2}}Q(z,+1,v)+{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}+{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}}$

y

${\displaystyle Q_{2}(z,v)={\frac {1}{2}}Q(z,+1,v)-{\frac {1}{2}}Q(z,-1,v)={\frac {1}{2}}\left({\frac {1}{1-z}}\right)^{v}-{\frac {1}{2}}\left({\frac {1}{1+z}}\right)^{-v}.}$

Necesitamos la cantidad

${\displaystyle G(z,v)=\left.{\frac {d}{dv}}(Q_{1}(z,v)-Q_{2}(z,v))\right|_{v=1}}$

cual es

${\displaystyle \left.{\frac {d}{dv}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-\left.\log {\frac {1}{1+z}}\left({\frac {1}{1+z}}\right)^{-v}\right|_{v=1}=-(1+z)\log {\frac {1}{1+z}}.}$

Finalmente, extrayendo coeficientes de esta función generadora, obtenemos

${\displaystyle -n\log {\frac {1}{1+z}}=-n!\left({\frac {(-1)^{n}}{n}}+{\frac {(-1)^{n-1}}{n-1}}\right)}$

cual es

${\displaystyle -n!(-1)^{n-1}\left(-{\frac {1}{n}}+{\frac {1}{n-1}}\right)=n!(-1)^{n}{\frac {n-(n-1)}{n(n-1)}}}$

que a su vez es

${\displaystyle n!(-1)^{n}{\frac {1}{n(n-1)}}=(-1)^{n}(n-2)!}$

Con esto concluye la prueba.

Generalizaciones

Existen estadísticas similares para endomorfismos aleatorios en un conjunto finito. ^{[3] [4]}

Véase también

• Constante de Golomb-Dickman

Referencias

1. Chowla, S. ; Herstein, IN ; Moore, WK (1951), "Sobre recursiones conectadas con grupos simétricos. I", Revista Canadiense de Matemáticas , 3 : 328–334, doi : 10.4153/CJM-1951-038-3 , MR  0041849, S2CID  123802787
2. Goh, William MY; Schmutz, Eric (1991). "El orden esperado de una permutación aleatoria". Boletín de la Sociedad Matemática de Londres . 23 (1): 34–42. doi :10.1112/blms/23.1.34. Archivado desde el original el 25 de febrero de 2020.URL alternativa
3. Bernard Harris (1960). "Distribuciones de probabilidad relacionadas con asignaciones aleatorias". Ann. Math. Statist . 31 (4): 1045–1062. doi : 10.1214/aoms/1177705677 .
4. Philippe Flajolet, Andrew M. Odlyzko (1989). Estadísticas de mapeo aleatorio (Informe de investigación RR-1114). INRIA. inria-00075445.

Enlaces externos

• Sung, Philip; Zhang, Yan (2003). "Recurrencias recurrentes en el conteo de permutaciones". CiteSeerX  10.1.1.91.1088 .
• Marko Riedel et al., La diferencia del número de ciclos de permutaciones pares e impares
• Marko Riedel et al., Llaves dentro de cajas cerradas, una cuestión de probabilidad

100 prisioneros

• Varios autores, Permutaciones con un 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 has escuchado correctamente
• Varios autores, Les-Mathematiques.net . Cent prisonniers (en francés)