Problem 1 - Temperley again

For various reasons few people got the Temperley bijection running on Assignment 4.

This week, I'd like you to take another shot at it. Please implement the Temperley bijection, if you have not done so. Its input should be a spanning tree on the $m \times n$ grid; its output should be a perfect matching on the $2m \times 2n-1$ grid, with a corner removed.

Then, I'd like you to refactor the code into python classes. Make classes for at least:

• spanning trees on grid graphs
• matchings on (subgraphs of) grid graphs

You can feel free to make other classes and/or other design choices (e.g. you might want to make a class for grid graphs themselves, or a different class for dual trees, or for forests, etc).

These classes should have __init__(), __str__(), __repr__(), and should be able to draw pictures of themselves (if that makes sense). The other functions you've defined as part of the temperley map (for computing the dual tree, finding perfect matching edges, etc.) should become methods of these classes.

Problem 2 - Desnanot-Jacobi

Let $a,b,c$ be nonnegative integers. We have a conjecture, from last week's classes, that

$$\det \left[ \binom{a+b}{a-i+j}\right]_{1 \leq i,j \leq n} = \prod_{i=1}^a\prod_{j=1}^b \frac{i+j+c-1}{i+j-1}. $$

and I sketched in class how one might prove this, using the Desnanot-Jacobi identity. Finish the proof.

Problem 3 - Random Reduced Word

We'll soon start to think about random generation of combinatorial objects - so here is a warm-up problem. Describe, and then implement, an algorithm for producing a uniformly random reduced word for a permutation $\pi \in S_n$. (One way to do this is to produce a list of all reduced words, and then take a random element from that list - I am asking you to do something more efficient).

I suggest you start by reviewing your old code for iterating over reduced words (you may want to refactor it too, as above). Start by modifying it so that it just counts reduced words, without generating them all. Then, use the counts to generate reduced words with the proper probabilities.