Probability of shuffling problem

Question

Given integers $a_1,\dots,a_{nt}$ all distinct we fix $t$ indices $0<i_1<\dots<i_t<nt+1$ and we randomly permute the integers and parition the permuted integers in to block $B_1,\dots,B_t$ each of size $n$. What is the probability that each of $t$ indices fall in distinct blocks?

Answer 1

There are $\frac{(nt)!}{(n!)^t}$ ways to group the integers into $t$ distinct blocks, each of size $n$.

Now, there are $t!$ ways to assign the special integers, one to a block. After this, there are $\frac{(nt-t)!}{(n-1)!^t}$ ways to group the remaining integers into the $t$ blocks, each of size $n-1$.

Dividing, we get $$\frac{t!(nt-t)!n!^t}{(n-1)!^t(nt)!}=\frac{t!(nt-t)!n^t}{(nt)!}$$

Answer 2

vadim123 already gave a nice answer. Here is another approach.

Notice that, the permutation or exchange of the $t$ indices does not affect the event that each of them belongs to one block. Also, permutation of the other $nt-t$ indices does not affect that event.

So the original probability equals the probability of the following event $A$. First we divide (the sorted indices) 1 to $nt$ into $t$ blocks, $B_i = \{n(i-1)+1,\cdots,ni\}$. Then we randomly pick $t$ indices from 1 to $nt$. Now $A$ is defined as the event that each of the $t$ indices falls into one blocks.

Denote $\Omega$ as the collection of all possible trials, then $|\Omega| = {nt\choose t}$, i.e., the number of ways of choosing $t$ out of $nt$ without replacement.

$|A| = n^t$, because we may pick one index from each block. So the probability is $$ P(A) = \frac{|A|}{|\Omega|} = \frac{n^t}{{nt\choose t}} = \frac{t!(nt-t)!n^t}{(nt)!}. $$

For the asymptotics, I think you may need some other conditions on the relationship between $t$ and $n$, like $t=\sqrt{n}$ or something else, because if $t=1$ the probability would be $1$.