I know this is an extremely noob question, but I need some help. since I am stuck
Prove the formula
$p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
from this answer.
I know this is an extremely noob question, but I need some help. since I am stuck
Prove the formula
$p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
from this answer.
Recall that $p(n,r)$ is the probability that the first shuffle of the deck of $n$ cards (by the prescribed method) will leave exactly $r$ unsorted cards. In order for this to happen, the first shuffle must put $n_1$ cards in correct order at the top of the deck and $n_2$ cards in correct order at the bottom of the deck, where $n-(n_1+n_2)=r$ is the number of cards left in the middle still to be shuffled.
There are $r!$ possible shuffled arrangements of the unsorted $r$ cards, and they’re all equally likely. However, some of them put the right card at the top of this deck of $r$ cards, which means that it would have been added to the top sorted stack. We don’t want to include those: they don’t leave us with $r$ unsorted cards. If the right card ends up at the top of the $r$ cards, the other $r-1$ cards could still be in any order, so there are $(r-1)!$ such permutations. There are also $(r-1)!$ permutations that put the right card on the bottom of the $r$ cards, where it would have gone into the bottom sorted stack. Thus, so far we have $r!-2(r-1)!$ permutations that leave the whole stack of $r$ cards unsorted.
However, we’ve subtracted too much: we subtracted some permutations twice, because some put the right card on the top and the right card on the bottom. Those merely leave the middle $r-2$ cards shuffled, so there are $(r-2)!$ of them. We subtracted them twice, so we have to add them back in to get the correct total number of permutations that leave all $r$ cards unsorted:
$\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*}$
Now $n_1$, the number of cards in the top sorted set, could be anywhere from a minimum of $0$ up to a maximum of $n-r$, if all of the sorted cards are at the top. To put it a little differently, the first one of the $r$ unsorted cards can be anywhere from the first card in the deck to the $(n-r+1)$-st card. That’s a total of $n-r+1$ different positions that it can occupy. For each of those possible positions of the $r$ unsorted cards there are $(r^2-3r+3)(r-2)!$ permutations of those cards that leave them unsorted, i.e., that don’t put the right card on either the top or the bottom. There is only one possible permutation of the top $n_1$ and bottom $n_2$ cards that gets them in the right places. Thus, we have a total of $(n-r+1)(r^2-3r+3)(r-2)!$ permutations of the whole deck that leave an unsorted section of $r$ cards to be shuffled again.
Finally, there are altogether $n!$ possible permutations of the deck, so the fraction that produce an unsorted batch of exactly $r$ cards is
$\frac{(n-r+1)(r^2-3r+3)(r-2)!}{n!}\;.$
Since the permutations are equally likely, that is also the probability of leaving exactly $r$ cards to be sorted.