# What is the probability of a given induced ordering of a random permutation?

I ran into the following problem in a calculation involving permutations.

Let $[n] = \{1,...,n\}$, and assume that $[n]$ is partitioned into equivalency classes. That is, $[n]$ is the disjoint union of the nonempty sets $A_1, ... ,A_d$, and $a_i = |A_i|$ denotes the sizes of the classes.

Any ordering $\sigma \in S_n$ induces an ordering $\tau \in S_d$ of the equivalency classes in the following way. $A_i$ precedes $A_j$ if there is an element of $A_i$ that precedes every element of $A_j$ in $\sigma$. In other words, the equivalency classes are ordered according to the positions of their first element in $\sigma$.

My question is: If $\sigma$ is chosen uniformly at random, what is the probability of a given induced ordering $\tau$?

I know that the answer should depend somehow on the $a_i$'s. As an example, if $d=2$ then the ordering of the classes is determined by the first element of $\sigma$, because if $\sigma(1) \in A_1$ then $A_1$ precedes $A_2$ and so $\tau = (1,2)$. Therefore $\Pr\{\tau = (1,2)\} = a_1/n$ and $\Pr\{\tau = (2,1)\} = a_2/n$.

$\Pr\{\tau = (1,2,3)\} = (a_1/n)(a_2/(a_2+a_3))$ and so on: $$\Pr\{\tau = (1,2,3,4)\} = (a_1/n)(a_2/(a_2+a_3+a_4))(a_3/(a_3+a_4))$$
• I see, if we want $\tau = (1,2,3, ... ,d)$ then $\sigma(1) \in A_1$. Given that, we don't care about the other elements of $A_1$, so the problem reduces to a problem with $n-a_1$ elements and $d-1$ sets. Thanks! – Zur Luria Jul 31 '14 at 11:12