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]](https://imgprx.livejournal.net/55970e971eb3aa5a5611e99a84cceb71c11261fe/NmhV1f2QhsUe2iljceDYNjwjNfr92kHbqRr0UwDGUkvpNN4V84nJl4g9gGIPF2cwG9I0POgk_8eTkY-VXOxZbNZ7WtGGeAfNlCpcRel7OiI)
![[Picture]](https://imgprx.livejournal.net/580b833feec71c9a8408d05fdce2701ae46c90b9/NmhV1f2QhsUe2iljceDYNjwjNfr92kHbqRr0UwDGUkvpNN4V84nJl4g9gGIPF2cwG9I0POgk_8eTkY-VXOxZbBnczmASrjse-h-Oyb6d7X0)
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.
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 =
struct
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) =
let
fun go (NONE :: tl) = NONE :: go tl
| go (SOME _ :: tl) = [SOME x]
| go _ = raise Domain
in
go h :: h :: tl
end
| addAboveLeft x [] = raise Domain
fun addLeft x (h::tl) =
let
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
in
h' :: tl'
end
| 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))
end
(*
Tests
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?
