## Partial Ordering: Strings

Let A be a set and S be the set of strings of A. That is an element of S is of the form s = a1a2 ... an where ai is an element of A for all 1 ≤ i ≤ n. Elements of A will be called letters. A full bracketing of a string s of length n is defi ned as grouping letters of s into pairs using parenthesis. For instance, a full bracketing of the string a1a2a3a4 is of the form (((a1a2)a3)a4).

Question 1
1. Find all possible full bracketing of strings of length 3, 4, and 5.
2. How many pairs of parenthesis is used in a full bracketing of a string of length n? Explain.

Description of the Problem (cont'd)
Let s be a string of length n and Gn be the set of all possible full bracketings of s. We defi ne an order on the set Gn as follows. For any g1; g2 in the set Gn(i.e. g1 and g2 are two full bracketings) g1 ≤ g2 if g2 is obtained from g1 by a rightward parenthesis movement. For instance, (((a1a2)a3)a4) and (a1(a2(a3a4))) are two different elements of G4. According to the order defined above (((a1a2)a3)a4) ≤ (a1(a2(a3a4))). For everyone's sake, we are going to assume without proof that (Gn, ≤) is a poset for all n.

Question 2
If they are comparable, compare the following full bracketings.
1. ((a1(a2a3))a4) and (a1((a2a3)a4))
2. (((a1a2)a3)(a4a5)) and ((a1((a2a3)a4))a5)

Question 3
1. Construct the Hasse diagram of the poset (G4, ≤).
2. If they exist nd the maximal and minimal element of (G4, ≤).