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.

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

*)

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?