Letting algebra do it

It's easy to get confused by phrases like "the product of no numbers at all" or "the product of -3 numbers, each of which is equal to 5". But the formulas (n-1)! = n!/n and a^(n-1) = (a^n)/a give us a down-to-earth way of understanding why defining 0! as 1, or defining 5^(-3) as 1/(5^3), is simply The Right Thing to Do. A good general principle to learn from these two cases, suitable for use as a mathematical mantra, is that when it comes to extending a sequence backward, "Let algebra do it."

How can we apply this mantra when the "sequence" that we are studying is the sequence whose nth term is the set of perfect matchings of the 2-by-n grid? By encoding each of these sets as a (multivariate) polynomial!

For instance, consider the 2-by-3 grid, this time with a variable labelling each of its edges:

                               o--x_1--o--x_2--o
                               |       |       |
                              z_1     z_2     z_3
                               |       |       |
                               o--y_1--o--y_2--o

We can convert each of the three matchings of this graph into a polynomial of degree 3, by multiplying together the variables that label the constituent edges. The matching that consists of three vertical edges is represented by the monomial z_1 z_2 z_3 while the other two matchings of the graph are represented by the monomials x_1 y_1 z_3 and z_1 x_2 y_2. If we sum these three monomials, we get a multivariate polynomial each of whose terms encodes a perfect matching of the grid.

If we just want to recover the total number of perfect matchings, all we have to do is replace all of the variables by 1. But there are much more interesting things to do. More generally, let M(n) be the polynomial in the variables x_1, ..., x_(n-1), y_1, ..., y_(n-1), z_1, ..., z_n whose constituent monomials encode all the matchings of the 2-by-n grid graph. Then we have

M(n) = z_n M(n-1) + x_(n-1) y_(n-1) M(n-2)

We can rearrange this equation to get

x_(n-1) y_(n-1) M(n-2) = M(n) - z_n M(n-1)

M(n-2) = [M(n) - z_n M(n-1)] / x_(n-1) y_(n-1)

and replace n by n+2, obtaining

M(n) = [M(n+2) - z_(n+2) M(n+1)] / x_(n+1) y_(n+1) .

And THIS is a recurrence that we can run backwards, obtaining in succession

M(3)  = x_1 y_1 z_3 + z_1 x_2 y_2 + z_1 z_2 z_3 , 
M(2)  = x_1 y_1 + z_1 z_2 ,
M(1)  = z_1 ,
M(0)  = 1 ,
M(-1) = 0 ,
M(-2) = 1 / x_(-1) y(-1)
M(-3) = - z_(-1) / x_(-1) y_(-1) x_(-2) y_(-2)
M(-4) = (x_(-2) y_(-2) + z_(-2) z_(-1)) / x_(-1) y_(-1) x_(-2) y_(-2) x_(-3) y_(-3) 
...

It turns out that M(-5), M(-6), etc. are all "Laurent polynomials": that is, each of them is a rational function that can be turned into an ordinary polynomial by multiplying by a suitably large monomial. By looking at the structure of these Laurent polynomials, one can read out the underlying combinatorics (which can then be imputed to some mystical "2-by-(-5) grid-graph" or whatever). We don't need to worry too much about what these funny generalized graphs really are; the point is that algebra (suitably employed) teaches us what the matchings of these graphs are.

This example should make it pretty clear why the computer is such an important tool for this kind of research. When you're looking at polynomials in lots of variables, it's easy to make mistakes when computing by hand; a computer frees you from drudgery and error. Furthermore, when the computer is available as an assistant, one's attitude to big hairy polynomials undergoes a subtle change. No longer are they intimdating (since the computer takes care of all the computational details); instead, their very hairiness becomes a comfort. All the combinatorics is encoded by the polynomials; it's just a matter of figuring out how to read it off.