[3.1] [10 marks] Write a function find_equivalent_matchings that takes a matching and returns all matchings with the same pattern (including the original one). Using this function, draw all matchings equivalent to {(0, 7), (1, 4), (2, 3), (5, 6)}. You might find it helpful to generate all permutations of a list using itertools.permutation (imported above) as in the following code template. perms-permutations (list_of_items) for p in perms: # Type your code and comments here [18] Python Along with this Jupyter Notebook, you have been provided with a Python file called "project.py" on QMPlus, which you should save in the same directory as this Jupyter notebook. This file contains a function create_partial_matching, which takes a student ID as an integer and creates a partial matching. (The output will look random, but will be unique to the provided student ID, i.e. no two students will have the same partial matching to work with.) This partial matching will have a few missing entries, indicated by an asterisk (as a string value). For example, a partial matching might be [(0,5),(1,'*'),('*',3)]./nart. The only proviem is that we need to relaven some points in uviny sv. Inserting a point to the left implies that the indices of the other points all have to be increased by one. Moreover, if we insert another point at some position m then all the indices with values m and larger again have to be increased by one. = For example, if we start with an arc diagram with precisely one arc, {(0, 1)}, then inserting a point to the left gives this one index zero and increases the other indices, leading to {(1, 2), (0, ·)} with still to be inserted. We can now insert a second point at positions m 1, 2, 3. This implies that all indices with values m and larger need to be increased. For m = 1 this leads to {(2, 3), (0, 1)}, for m = 2 we get {(1, 3), (0, 2)}, and finally for m = 3 we find {(1,2), (0,3)}. Using this approach, write a function get_all_matchings that takes as argument a non-negative integer n and returns a list of all (2n − 1)!! matchings on n arcs. You may do this recursively or iteratively. Test your function by verifying that len(get_all_matchings(n)) is equal to (2n − 1)!! for n = 0, 1, . . ., 7. # Type your code and comments here 6] Python [2.3] [10 marks] For n = 6, compute the number Ck of arc diagrams with k crossings and 1 nestings for all possible values of k and 7. Store these counting A 16 numbers Cr, in a numny array of integer data tune and annropriate shane meaning that the number of rows and columns should be aligned with the (0 Cell 63 of 75 Go Live D/nCode Markdown Run All Ex Clear All Outputs Outline ... Select Kernel [2.1] [10 marks] The code in Part 1 counts the crossings and nestings for a given matching. We now want to use this to analyze the distribution of crossings and nestings for arc diagrams with 100 arcs. Using your function random_matching from Exercise [1.4], generate 104 such arc diagrams and create histograms for the numbers of crossings and nestings, respectively. Display them in a single plot. Also generate a two-dimensional histogram for the joint distribution of crossings and nestings. What do you observe? # Type your code and comments here 5] (Type your observations in this Markdown cell) Python [2.2] [10 marks] In order to determine the full histogram for all matchings of a given size, we need to generate every single possible matching in a unique way. This is where the inductive description from the introduction becomes useful, as it provides a way to do so recursively: We can generate all arc diagrams with n arcs from all arc diagrams with (n − 1) arcs by adding one arc to each of them in precisely 2n · 1 ways. To this end, we take an arc diagram with (n − 1) arcs, insert one new point at the left end and one more point somewhere to the right of it (2n- 1 options), and then match the newly inserted points to obtain the additional arc. The only "problem" is that we need to relabel some points in doing so. -/nHT HII2 AaITIPI L TIav ISTIt PViiS 9IviTI9 TIP V TVEI aISS. V WIII HTan aII IIJ་ སTS སNSvL HI HI VIT WHHISIT HI PVIS IV JI---ཕ. Parts of this project will involve counting all the different possibilities of drawing arc diagrams with n arcs, so let's do some easy counting arguments to get you started: If you have 2n points then pick the left-most point. The arc starting at this point can be connected to any of the remaining 2n 1 points. Once you have done this, there are 2(n - 1) points left to connect. Repeating this process, you can see that the left-most of these points can be connected to any of 2(n- 1) - 1 points, and so forth. In other words, the total number of arc diagrams with n arcs is ParseError: KaTeX parse error: Can't use function '$' in math mode at position 39: ...Idots3\cdot 1\;, $$ which is usua... Some notation It will be convenient to denote an arc starting at position i and ending at position j (with j > i) by the ordered pair (i, j). In the above example, we have a set of four arcs {(0,6), (1,3), (2, 5), (4, 7)}. Crossings It is easy to see that arcs can cross each other. Two arcs (i, j) and (k,1) are said to be crossing if and only if A 16 (2)0 Cell 5 of 75 Go Live D/nIntroduction to the project In this project you will investigate properties of arc diagrams, particularly so-called crossings and nestings. Arc diagrams Assume you have an even number of points on a line, and denote the number of points by 2n with n Є No. As there is an even number of points, one can connect these points in pairs; this is called a matching. We will label the points by 0, 1,. 2n 1 from left to right. A nice way of visualising such a matching is via an arc diagram, where any matched points are connected by an arc, as in the following image. In this example we have eight points giving rise to four arcs. We will draw all these arcs above the line on which the points are situated. A 16 (A) 0 C Cell 1 of 75 Go Live D 14:39 ENG A

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5