February 17th, 2010

beartato phd

(no subject)

Here is a lovely bijective proof I found on mathoverflow of a weird combinatorial fact about horizontally convex polyominoes. That's a mouthful, I know, but all it means is a collection of 1xN rows of tiles that are connected. Or to put it another way, if there are two tiles in the polynomial in the same horizontal row, then any tile-spots between them have to actually be filled by tiles. (If you're not familiar with "convexity", it is usually exactly this sort of flavor of "if two points are in a set, then things between them must also be in the set") To quote the page:

A polyomino P is horizontally convex if each horizontal line meets P in a single line segment, or not at all. For example, the first polyomino below is horizontally convex; the second one is not.
[Picture] [Picture]
Horizontally convex Not horizontally convex

Anyway if a(n) is the number of these guys that exist that have n tiles, then you get a recurrence
a(n) = 5 a(n-1) - 7 a(n-2) + 4 a(n-3)
which is totally weird, right? But the linked paper walks cleverly through several lemmas each of which establishes a little fact about how removing or adding one tile in the right place can preserve or transform slightly more fine-grained properties of horizontally convex polyominoes. And chaining all the isomorphisms together is a nice isomorphism witness to the above numerical fact.

I think it would make a cute homework exercise in some class somewhere (although I don't know what class it would be suitable for) to write some ML or Haskell datatype 'a hcpoly that exactly captures these guys.

Collapse )


Another totally weird thing that I wish I knew the answer to, but there weren't any answers to it at the time of writing, is the question: is there any combinatorial reason with the (-1)st Catalan number seems like it ought to be -1/2? If you just take the usual formula (1/(n+1))Choose(2n, n) for the Catalan numbers, and take the limit as n goes to -1 (using the Γ function, of course, to define fractional factorials) you get -1/2. For all other negative integers, you get zero. Why the heck is this? What does it mean?