El pedido de una baraja de cartas

Question

Si usted shuffle n tarjetas de la siguiente manera: Ir a través de la cubierta en una tarjeta a la vez y en cada tarjeta, lanza una moneda. Si la moneda sale de la cabeza, a continuación, deje la tarjeta donde está, y si sale cruz mover la tarjeta hasta el final de la cubierta. Por ejemplo, si n =4, y el primer pedido es 1,2,3,4, y el resultado de los sucesivos lanzamientos es h,t,t,h, entonces el orden en el final de la ronda es 1,4,2,3. Suponiendo que todos los resultados posibles de la moneda gira son igualmente probables, ¿cuál es la probabilidad de que el orden después de una ronda es el mismo que el primer pedido?

Intento:

Si el pedido después de n flips es el mismo que el primer pedido, entonces usted tiene que rodar todos los jefes ya que rodar cabezas, no cambia el orden. Así que la respuesta sería (1/2)^n?

Answer 1

A ver lo de la cola de cabeza-secuencias de dar la identidad de permutación, ver que si usted obtiene una cabeza, de salir de la correspondiente tarjeta a su lugar, y la describe el proceso que se sigue sólo para las siguientes tarjetas. Lo que estamos haciendo es aplicar a la matriz $[1,\dots,n]$ la permutación $(n\ n\!-\!1 \ \cdots\ 2\ 1)$ mientras estés en la obtención de colas; después de una cabeza de continuar la aplicación para usted es el vector de permutación $(n\ n\!-\!1 \ \cdots\ 3\ 2)$, y después de $m$ cabezas de la permutación $(n\ n\!-\!1 \ \cdots\ m\!+\!2\ m\!+\!1)$. De todas las secuencias que comienzan con todos los jefes y, en algunos poing, iniciar y continuar con todas las colas de dar la identidad, por ejemplo

hhh...hhhtttt...tttt

Para ver que no hay otra cabeza de la cola-secuencia da la identidad, se supone que estás en la tarjeta de $7$ (número de la suerte!), si usted obtiene una cola de poner ese número hasta el final, y ahora se mueve en número de $8$, y si se obtiene el jefe de salir de allí y pasar por encima de... de su cadena final tendrá la $8$ ocurren antes de la $7$!! En general, tener una cabeza después de una cola, no conservan el orden. Por lo que la probabilidad de terminar el proceso con la misma cadena es $(n+1)/2^n$ donde $n+1$ es el número de las cuerdas (descrito anteriormente) de la forma de todos los jefes seguido por todos-colas.

PS tengo que señalar que por $(n\ n\!-\!1 \ \cdots\ 2\ 1)$ me estoy refiriendo a las posiciones, me refiero a $n$ en la notación de la media de la $n$th tarjeta en las tarjetas de matriz, y no el valor de la tarjeta de $n$.