2. Problem Set 2: hints2.1. 2.2. 2.3. 2.4. 2.5. 2.6.2. Problem Set 2: hintsThe goal is to try all the problems and do half of them.2.1. Suppose that C is a category with 2 objects A, B so that thereis only one morphism A → A, only one morphism A → B and onlyone morphism B → B. Then how many morphisms can there be fromB → A ? How can you tell whether a number is possible?Something very strange happens if there are two arrowsg, h : B → A2.2. Noncrossing partitions can be rotated. Rooted binary trees canalso be rotated by attaching an edge at the root, deleting the edgeattached to a leaf, then rotating the new 2-valent node to the top. Dothese rotations correspond? (Does the bijection between rooted binarytrees and noncrossing partitions take the rotated tree to the rotatedpartition?) First do some examples of rotations to see if this seems tobe true. (Or if you know why it is true or not true, do some examplesto illustrate this.)We talked about the bijection from rooted binary trees to noncrossingpartitions today (10/15/08). You take a walk around the tree, goingcounterclockwise starting at the root. You get a picture that looks likea “glove” for the tree. You number the right edges 1,2,3 when you firstcome to them, which will be when you go down these edges. Thenthe parts of the noncrossing partition consists of the numbers on eachstraight line of slope -1.@@@@@@@@@@@@@@@@@@@@@@@@2341This gives (13)(2)(4).232.3. In 1791 Fuss showed that the number of ways to cut up a convexpolygon P with n + 2 sides into triangles with corners at the cornersof P is given by the Catalan number C(n). Show that this is trueby finding a bijection from the set of triangulations of P to the set ofrooted binary trees. Hint: Put one side of P at the top. Put one leafat each of the other sides. Place a node in the center of each triangle.Connect nodes in adjacent triangles. Connect each leaf to the node inthe center of the triangle adjacent to that side. Do an example, drawa picture. What is the inverse process?Draw the binary tree with the leaves in a circle.2.4. If you have a binary rooted tree, you can take its mirror im-age. (Hold the paper up to a mirror.) The corresponding Dyck pathalso changes in some mysterious way: For example LLRRLR becomesLLRLRR. Do more example to figure out the operation on the Dyckpath given by mirror image of the binary tree.This is a challenge (1).2.5. Suppose that a Dyck path is reversed, i.e., write it backwardsand switch L with R: This would make LLRRLR into LRLLRR.(1) Show that the result is still a Dyck path. This is easy. Just cutit any point and count the number of L’s and R’s.(2) Describe what happens to the binary tree. Another challenge(2)As always, you should do example to see if you can spot the pattern.2.6. A mutation of a binary tree is given by changing the position ofone node.(1) What does a mutation do to the Dyck path? Challenge (3)(2) How many mutations will take LLLLLR RRRR to LRLRLRLRLR?Challenges (1),(2),(3) are related. The answer involves “jumpingover” Dyck subpaths. For example, if we have LLRLLLRLRRR thenthe red part is a Dyck subpath and the blue part jumps around the redpart in a mutation to get