Let \mathbf {K}_K denote the chain of values x_1, x_2, x_3, \dots , x_K where a \leq b implies x_a \sqsubseteq x_b. There is one monotonic function \mathbf {K}_1 \rightarrow \mathbf {K}_1:

And there are three monotonic functions \mathbf {K}_2 \rightarrow \mathbf {K}_2:

1. Write down the monotonic functions \mathbf {K}_3 \rightarrow \mathbf {K}_3.

Solution.

• Liam O'Connor

When drawn as a diagram like the above, the monotonic functions are all those whose lines do not cross.

2. Write a simple recursive program to calculate the number of monotonic functions \mathbf {K}_n \rightarrow \mathbf {K}_m.

Solution.

• Liam O'Connor

In Haskell:

monotonics :: Int -> Int -> Int
monotonics n 1 = 1
monotonics n m = sum [monotonics (n-x) (m-1) | x <- [0..n]]