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$.



What is the probability of a given induced ordering of a random permutation?
Nice problem but actually its solution is simple.


$\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))$$


