You have n objects, which you wish to put in order using the relations < and =. Let count(n) be the number of different orderings possible for n objects. For example,

count(1) = 1: A count(2)=3: A=B,A

Note that for n=3, A=B=C is the same ordering as B=A=C, and A=B

(a) What is count(4)?

(b) Give a dynamic programming algorithm that computes count(n) in O(n2) worst-case time.

Hint 1: There are a lot of possible orderings for n = 4. You may want to work on part (b) first to figure out a systematic way of generating orderings before working on part (a). Of course, if you have no idea about part (b), working on part (a) first may give you some ideas.

Hint 2: I dont think that a table can be built to compute count(n) directly. What I did is to first define count(n) in terms of another function f, use dynamic programming to compute f, and finally determine count(n) using the table constructed.