REACH minutes, 9.26.02 Note taker David Offner We introduced ourselves again. This time we talked about our mathematical selves and what we enjoy. Jim likes combinatorics and telling people what to do. Jim will find out the name of the book on species which connects combinatorics and category theory Room and location issues: Jim will look into the availability of the computer lab until 5:15. Harvard students and Jim will look into finding rooms closer to the science center. Alice will look into meeting spaces in the houses at Harvard. Gabriel will look into classrooms in the yard. Andy will look into a meeting room at cabot house. Contracts were handed out, discussed, and signed. Grad students were asked to help with supervisorial duties. Web sites should be started by Oct. 1. Web sites should be up and running by Oct. 8. -write something about what you're doing, even if it's generic Jim put a contact list on the web. Students should read it and note errors and updates. Jim suggested to consult the REACH page and references for those looking to fulfill their 6 hours: -links from REACH web page -somos sequence web site -bilinear forum -read articles (may want to start with ones written by undergrads) -investigate connections between combinatorics and other fields of interest -follow what seems interesting to you Those who need to read .ps files should download ghostscript (available free--search on google) We discussed the homework problem. We broke into 5 groups of 5 and discussed different approaches for 20 minutes After 20 minutes a representative from each group reported to the whole group a general summary of what was discussed in each group. -removing the corner dot -writing a(n) as a sum of previous terms and "popping out" the solution Various numbers of people wanted to hear about solutions using: dot removal no dot removal bijections generating functions Other wanted to discuss generalizing for more than 2 rows. we took a break and decided to remain in the classroom and continue the discussion rather than moving to the science center. Andy presented one "dot removal" solution: Let a(n) = the number of matchings on a 2-by-n grid (we will call this an n-grid). we count cases: case 1: an n-grid with no vertices connected in the nth column has a(n-1) matchings. case 2: an n-grid with the vertices in the nth column connected to each other has a(n-1) matchings. case 3: So we need to count the number of matchings of an n-grid with a horizontal edge already chosen between columns n and n-1: There are two choices for how to choose this edge, each having a certain number of matchings. Call this number S(n). We've shown that a(n)=2a(n-1)+2S(n)-a(n-2). Now to find S(n). Say we pick the horizontal edge in row 1. We can draw a picture with these two vertices missing, ........ .......... ----n----- or alternatively, move the far right vertex to the n-1 column, disallowing the horizontal connection to it. ......... ......... --(n-1)-- How many matchings are there on this grid? S(n) = a(n-1) - S(n-1) = a(n-1) - (a(n-2) - S(n-2)) = a(n-1) - (a(n-2) - (a(n-3) - S(n-3))) = ... Put the cases together, and do a little algebra to derive the recurrence. Inn pointed out that we can solve for S(n) in a(n)=2a(n-1)+2S(n)-a(n-2), which allows us to express everything in terms of a(n),a(n-1),... and obtain the recurrence. Rui presented a second dot removal solution: a(n) = 2a(n-1) +a(n-2) + 2b(n-1) where b(n) = the number of matchings of an n-grid with a corner dot removed. We can see b(n) = a(n-1) + b(n-1). Putting these two recurrences together, we solve for the recurrence we want: a(n) = a(n-2) + 2b(n) 2b(n) = a(n-1) + a(n-3) =>... Jim presented a more generally valid technique: take the type of equations we worked with above and encode them with generating functions. A(x) = a(1) x + a(2)x^2 + a(3)x^3 +... B(x) = b(1) x + b(2)x^2 + b(3)x^3 +... encode equation 1: sum(n=1..ifty) b(n)x^n = sum(n=1..infty) a(n-1)x^n + sum(n=1..ifty) b(n-1)x^n B(x) = sum(n = 0..infinity)a(n)x^(n+1) + sum(n=0..ifty) b(n)x^(n+1) B(x) = x + xA(x) + xB(x) Assignment for next Tuesday: encode equation 2 We will find two linear equations in unknowns A(x) and B(x). => We can solve directly for A(x) and B(x), verifying the generating function without proving the recurrence. Assignment for next Tuesday: do it Jim then presented some magic: Call a matching of the 2-by-n grid-graph primitive (or irreducible) if it can't be chopped into two pieces (2-by-a and 2-by-b, with a+b=n) without chopping through an edge in the matching. Every non-primitive matching of the 2-by-n grid-graph can be displayed as a bunch of (two or more) primitive matchings put side by side. P(x) = generating function for primitive (i.e. irreducible) matchings of the 2-by-n grid. = 2x^1 + 3x^2 + 2x^3 + 2x^4 + 2x^5 + ... (all coefficients from here will be 2) = (2x + x^2 - x^3)/(1-x) Now look at: M(x) = generating function for all matchings of the 2-by-n grid = 1 + P(x) + P(x)P(x) + P(x)P(x)P(x) + ... (this is a geometric series) = 1/(1-P(x)), and we already know what P(x) is. Done. Assignment for next week: verify this solution. If not comfortable with generating functions, consult H. Wilf's book Generatingfunctionology (available online). Also: find a solution (either a recurrence relation or a generating function) for the number of matchings of a 1-by-n ladder, and a 3-by-n ladder. Try to find a solution using the Cayley-Hamilton Theorem. (This will explain why our generating function is a rational function.) Can C-H be applied to the 3-by-n case? Also: As you find generating functions for various sequences of matchings, look for patterns.