Topological orderings of a poset(A, |)?

1,412

HINT: The first and second problems are very easy once you understand what a topological sort of a partial order is: it’s a linear (or total) order on the underlying set that preserves the partial order. In (c), for instance, $2\mid 4$, $2\mid 8$, and $2\mid 16$, so $2$ must precede $4,8$, and $16$ in any topological sort of this partial order. Similarly, $4\mid 8$ and $4\mid 16$, so $4$ must precede $8$ and $16$. And $8\mid 16$, so $8$ must precede $16$. Thus, in any topological sort the four elements $2,4,8$, and $16$ must appear in that order. Similar reasoning will tell you that $3,9,27$, and $81$ must appear in that order. Thus, the number of topological sorts of $\langle\{2,3,4,8,9,16,27,81\},\mid\rangle$ is the number of ways to interlace the two sequence $\langle 2,4,8,16\rangle$ and $\langle 3,9,27,81\rangle$. Interlacing them gives you a sequence of length $8$. If you know which $4$ places in that sequence are occupied by the four even numbers, then you know the whole sequence, because the even numbers must fill those $4$ place in increasing order, and the four odd numbers must fill the remaining $4$ places in increasing order. How many ways are there to choose $4$ positions for the $4$ even numbers?

The reasoning that I used above should give you the answer to (b) immediately. As for (a), does divisibility impose any restriction at all on how you can order the elements?

Share:
1,412

Related videos on Youtube

oneCoderToRuleThemAll
Author by

oneCoderToRuleThemAll

Updated on June 27, 2022

Comments

  • oneCoderToRuleThemAll
    oneCoderToRuleThemAll less than a minute

    enter image description here

    Please explain how I can do this problem.

    • hmakholm left over Monica
      hmakholm left over Monica over 8 years
      What are your thoughts? Drawing some Hasse diagrams might be a good first step.
    • oneCoderToRuleThemAll
      oneCoderToRuleThemAll over 8 years
      I am not sure of what a topological sort is ? As I understand, for a) the hasse diagram would be set of saperated dots since no element is the divisible by any other element in the set ? So how would count the number of topological sorts...is it zero ?
    • hmakholm left over Monica
      hmakholm left over Monica over 8 years
      x @Gdgames: A topological sort of a poset is an arrangement of the elements in a (linear) sequence such that for every two comparable elements $x\prec y$, $x$ comes earlier than $y$ in the sequence. (Or equivalently, it is a total order that agrees with the partial order for every pair of comparable elements).
    • hmakholm left over Monica
      hmakholm left over Monica over 8 years
      In general if you're uncertain about the meaning of a phrase in an excercise, it is much better to ask about that instead of just expecting someone to do the entire problem for you.
  • ILoveMath
    ILoveMath over 8 years
    Thanks Brian! And CONGRATS!! Now you are the number $1$ is MSE. You deserve it! If you dont mind me asking, How does it feel to be number $1$? does it feel euphoric?
  • oneCoderToRuleThemAll
    oneCoderToRuleThemAll over 8 years
    I think for a) order does not matter at all since nothing divides so you would have 8! orderings. Thanks for the straightforward and useful reply. It makes so much sense now.
  • Brian M. Scott
    Brian M. Scott over 8 years
    @GdgamesGamers: $8!$ is correct, for exactly the reason that you give. You’re welcome.
  • Brian M. Scott
    Brian M. Scott over 8 years
    @DonAnselmo: I won’t deny that there’s a small thrill, but I have more time to put into MSE than most, so it wasn’t unexpected. I actually get more of a kick out of the fact that MSE now has two people who would make the first page on the all-time list over at Stack Overflow!