Topological Sort

Question

How many Topological Orderings possible?

Comments

48 is correct

---

https://gateoverflow.in/240938/topological-sort

Both are equivalent, close your question.

---

yes done, but without answer how do we know if some state is missing or not?

Answer 1

${\color{Green} {ABC}}{\color{Red} {DEF}}=3!3!=36$

Starting with AB or AC or BC and permuted last two elements

${\color{Green} {ABDC}}{\color{Red} {EF}} \text{and}{\color{Green} {ABDC}}{\color{Red} {FE}} =2$

${\color{Green} {ACEB}}{\color{Red} {DF}} \text{and}{\color{Green} {ACEB}}{\color{Red} {FD}} =2$

${\color{Green} {BCFA}}{\color{Red} {DE}} \text{and}{\color{Green} {BCFA}}{\color{Red} {ED}} =2$

Next 6 same as previous and just permuted first 2

${\color{Blue}{BA}\color{Green} {DC}}{\color{Red} {EF}} \text{and}{\color{Blue}{BA}\color{Green} {DC}}{\color{Red} {FE}} =2$

${\color{Blue}{CA}\color{Green} {EB}}{\color{Red} {DF}} \text{and}{\color{Blue}{CA}\color{Green} {EB}}{\color{Red} {FD}} =2$

${\color{Blue}{CB}\color{Green} {FA}}{\color{Red} {DE}} \text{and}{\color{Blue}{CB}\color{Green} {FA}}{\color{Red} {ED}} =2$

Total $48$

Answer 2

48 is the answer