Count number of total orders on a set

385 Views Asked by At

The question is like: There is two sets A and B such that A and B are total different sets and |A| = m and |B| = n. There is two total orders R on A and S on B. C = A unite with B. How much total orders on c contain both R and S.

Solution is like:

Choose a total order on C that contains both R and S is like order C items in a row such that A items are ordered respectively to R and B items are ordered respectively to S. To choose an order like that, we will choose the places of the items of A in the row. there is (m+n, m) options for that, than we will order them respectively to R and than we will order B items respectively to S. Therefore, there is (m+n, m) total orders on C that contains R and S.

Problem is:

Can't see why to choose a total order on C that contains both R and S is like order C items in a row such that A items ordered respectively to R and B items are ordered respectively to S.

1

There are 1 best solutions below

0
On BEST ANSWER

Here is a different way to rephrase their argument. Consider the following question:

How many where are there to choose a total order on $C$?

Obviously, the answer is $(n+m)!$. However, we can answer the question in a different way. To choose a total order on $C$, you have to...

  1. Choose a total ordering on $A$ (since every ordering on $C$ creates an ordering on $A$). This can be done in $n!$ ways. Call this ordering $R$.

  2. Choose a total ordering on $B$, in $m!$ ways. Call this ordering $S$.

  3. Finally, you must choose the ordering on $C$ which is consistent with these last two choices. That is, you must choose an ordering on $C$ containing $R$ and $S$. This is exactly the quantity you are trying to count.

By equating the two different ways to answer the same question, you get $$ (n+m)!=n!\times m!\times \left(\begin{matrix}\text{# ways to choose a total ordering}\\\text{on C containing $R$ and $S$}\end{matrix}\right) $$ Divide by $n!m!$ and you have your answer.