3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Zur Luria Jul 31 '14 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.