Resolviendo esta permutación

Question

Sé que esta es una pregunta extremadamente noob, pero necesito algo de ayuda. ya que estoy atascado

Demostrar la fórmula

$$p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$$

de esta respuesta .

Answer 1

Recordemos que $p(n,r)$ es la probabilidad de que la primera barajada del mazo de $n$ tarjetas (por el método prescrito) dejará exactamente $r$ tarjetas sin clasificar. Para que esto ocurra, la primera baraja debe poner $n_1$ cartas en orden correcto en la parte superior del mazo y $n_2$ cartas en orden correcto en el fondo del mazo, donde $n-(n_1+n_2)=r$ es el número de cartas que quedan en el centro por barajar.

Hay $r!$ posibles arreglos barajados de los no clasificados $r$ tarjetas, y todas son igual de probables. Sin embargo, algunos de ellos ponen la carta correcta en la parte superior de esta baraja de $r$ tarjetas, lo que significa que se habría añadido a la pila superior ordenada. No queremos incluirlas: no nos dejan con $r$ tarjetas sin clasificar. Si la carta correcta termina en la parte superior del $r$ tarjetas, el otro $r-1$ Las tarjetas podrían seguir en cualquier orden, por lo que hay $(r-1)!$ tales permutaciones. También hay $(r-1)!$ permutaciones que pongan la carta correcta en el fondo de la $r$ tarjetas, donde habría ido a parar a la pila de abajo ordenada. Así, hasta ahora tenemos $r!-2(r-1)!$ permutaciones que dejan toda la pila de $r$ tarjetas sin clasificar.

Sin embargo, hemos restado demasiado: restamos algunas permutaciones dos veces, porque algunas ponen la carta correcta en la parte superior et la tarjeta derecha en la parte inferior. Esos simplemente dejan el medio $r-2$ cartas barajadas, por lo que hay $(r-2)!$ de ellos. Los restamos dos veces, así que tenemos que volver a sumarlos para obtener el número total correcto de permutaciones que dejan todos $r$ tarjetas sin clasificar:

$$\begin{align*} r!-2(r-1)!+(r-2)!&=r(r-1)(r-2)!-2(r-1)(r-2)!+(r-2)!\\ &=\Big(r(r-1)-2(r-1)+1\Big)(r-2)!\\ &=(r^2-3r+3)(r-2)!\;. \end{align*}$$

Ahora $n_1$ el número de cartas en el conjunto superior ordenado, podría ser de un mínimo de $0$ hasta un máximo de $n-r$ si todas las cartas clasificadas están en la parte superior. Para decirlo de otra manera, el primero de los $r$ Las cartas no clasificadas pueden estar en cualquier lugar desde la primera carta del mazo hasta la $(n-r+1)$ -Tarjeta de la calle. Eso es un total de $n-r+1$ diferentes posiciones que puede ocupar. Para cada una de esas posibles posiciones del $r$ tarjetas sin clasificar hay $(r^2-3r+3)(r-2)!$ permutaciones de esas cartas que las dejan sin clasificar, es decir, que no ponen la carta correcta ni arriba ni abajo. Sólo hay una permutación posible de la parte superior $n_1$ y el fondo $n_2$ tarjetas que los coloca en los lugares correctos. Así, tenemos un total de $$(n-r+1)(r^2-3r+3)(r-2)!$$ permutaciones de todo el mazo que dejan una sección sin clasificar de $r$ las cartas para ser barajadas de nuevo.

Por último, hay en total $n!$ permutaciones posibles de la baraja, por lo que la fracción que produce un lote sin clasificar de exactamente $r$ tarjetas es

$$\frac{(n-r+1)(r^2-3r+3)(r-2)!}{n!}\;.$$

Como las permutaciones son igualmente probables, esa es también la probabilidad de dejar exactamente $r$ tarjetas que hay que clasificar.