GATE Overflow Test Series | Mock GATE | Test 4 | Question: 31

Question

Consider a Poset on set $A=\{a_1,a_2,\ldots, a_n,x,y\}$ such that

• $x\leq a_i$ for $i = 1,2,3,4,\dots, n $
• $a_i \leq y$ for $i = 1,2,3,4,\dots, n $

For any given values of $x$ and $y,$ the number of ways in which the given partial order can be converted to a Totally Ordered Set is ________

• A. $n!$
• B. $(n+1)!$
• C. $n$
• D. $1$

Answer 1

The total number of topological sorts is the number of tosets compatible with the given poset.

Here, the minimum element is $x$ and maximum element is $y.$ In between $n$ elements are there and any permutation of them gives a valid toset.

So, total number of topological sorts possible $= n!$.

The correct answer is $A$.

Comments

but we have no knowledge about ‘ai’ its a possibility that x=3, a1=4,a2=5,a3=6,y=7 for n=3   and its also possible that x=3, a1=3,a2=3,a3=3,y=3  for n=3 hence isnt the question ambiguous please clarify @gatecse

---

yeah ,  i also think that question is not properly framed

---

@anas_2908 The thing is that we are “given” a poset. But the set definition was missing in the question – just added.

---

Yeah