Jason (jcreed) wrote,

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.

The type 't xa is the one that is actually the type of nonempty horizontally convex polyominoes that carry data of type 't at each tile. The other functions in the structure serve to draw a little ASCII picture of the polyomino you have represented.

structure Combi =
datatype 't xa = Leaf of 't | AA of 't * 't xa | AB of 't xb | AC of 't xc
and 't xb = BA of 't * 't xa | BD of 't xd
and 't xc = CC of 't * 't xc | CA of 't * 't * 't xa
and 't xd = DB of 't * 't xb | DE of 't xe
and 't xe = EE of 't * 't xe | EC of 't * 't xc

fun addRight x (h::tl) = (h @ [SOME x]) :: tl
| addRight x [] = raise Domain

fun addAboveRight x (h::tl) = ((map (fn x => NONE) (List.tl h)) @ [SOME x]) :: h :: tl
| addAboveRight x [] = raise Domain

fun addAboveLeft x (h::tl) =
fun go (NONE :: tl) = NONE :: go tl
| go (SOME _ :: tl) = [SOME x]
| go _ = raise Domain
go h :: h :: tl
| addAboveLeft x [] = raise Domain

fun addLeft x (h::tl) =
fun go' (rem as (SOME _ :: _)) = (SOME x :: rem)
| go' (NONE :: rem) = NONE :: go' rem
| go' _ = raise Domain
fun go (row as (SOME _ :: _)) = ([NONE], SOME x :: row)
| go (NONE :: row) = ([], go' row)
| go _ = raise Domain
val (ins, h') = go h
val tl' = map (fn row => ins @ row) tl
h' :: tl'
| addLeft x [] = raise Domain

fun swapFirstTwo (h1 :: h2 :: tl) = (h2 :: h1 :: tl)
| swapFirstTwo _ = raise Domain

fun secondRow f t = swapFirstTwo (f (swapFirstTwo t))

fun taba (Leaf x) = [[SOME x]]
| taba (AA (x, a)) = addRight x (taba a)
| taba (AB b) = tabb b
| taba (AC c) = tabc c
and tabb (BA (x, a)) = addAboveRight x (taba a)
| tabb (BD d) = tabd d
and tabc (CA (x, y, a)) = addLeft x (addAboveLeft y (taba a))
| tabc (CC (x, c)) = addLeft x (tabc c)
and tabd (DE e) = tabe e
| tabd (DB (x, b)) = secondRow (addRight x) (tabb b)
and tabe (EC (x, c)) = addAboveLeft x (tabc c)
| tabe (EE (x, e)) = secondRow (addLeft x) (tabe e)

fun fill x = map (map (fn SOME x => x ^ " " | NONE => ". ")) x
fun show x = print (String.concat (map (fn y => String.concat y ^ "\n") x))




let open Combi in (show o fill o taba) (AC(CA("h","k",(AA("x", (AB(BA("g", (AA ("f", Leaf "e")))))))))) end;

h k
. g x
e f

let open Combi in (show o fill o taba) (AC(CA("a", "b", Leaf "e"))) end;

a b
. e

let open Combi in (show o fill o taba) (AC(CC("z", CA("h","k",(AA("x", (AB(BA("g", (AA ("f", Leaf "e"))))))))))) end;

z h k
. . g x
. e f

let open Combi in (show o fill o taba) (AC(( CA("h","k",( (AB(BA("g", (AA ("q", (AA ("f", Leaf "e")))))))))))) end;

. h k
. . g
e f q

let open Combi in (show o fill o taba) (AC (CA("t", "y", (AB (BD (DE (EE ("a", EE ("b", (EC ("c", CC ("d", CA ("e", "f", Leaf "g"))))))))))))) end;
. t y
. . c
a b d e f
. . . . g

let open Combi in (show o fill o taba) (AC (CA("t", "y", (AB (BD (DB("i", (BD (DE (EE ("a", EE ("b", (EC ("c", CC ("d", CA ("e", "f", Leaf "g")))))))))))))))) end;

. t y
. . c
a b d e f i
. . . . g

let open Combi in (show o fill o taba) (AA ("w", (AC (CA("t", "y", (AB (BD (DB("i", (BD (DE (EE ("a", EE ("b", (EC ("c", CC ("d", CA ("e", "f", Leaf "g")))))))))))))))))) end;

. t y w
. . c
a b d e f i
. . . . g



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?
Tags: combinatorial species, combinatorics, math

  • (no subject)

    Something that's bugged me for a long time is this: How many paths, starting at the origin, taking N steps either up, down, left or right, end up at…

  • (no subject)

    Still sad that SAC seems to end up being as complicated as it is. Surely there's some deeper duality between…

  • (no subject)

    I had already been meaning to dig into JaneSt's "Incremental" library, which bills itself as a practical implementation (in ocaml) of the ideas in…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded