[math-fun] percolation is odd

My friend Stephan Mertens and I just proved something you might enjoy. Consider filling a subset of the cells of an n-by-m rectangular lattice. Call the resulting configuration “spanning" if there is a path of occupied cells from the top row to the bottom row (stepping orthogonally). Let N_even (N_odd) be the number of spanning configurations with an even (resp. odd) number of occupied cells. Show that N_even-N_odd = +1 or -1, and determine the sign as a function of n and m. As a corollary, the total number of spanning configurations is odd. For instance, for n=m=2 there are 7 spanning configurations, with N_even=3 and N_odd=4. Cris Cris Moore moore@santafe.edu