Tuesday, August 13, 2013

Endomorphisms of a finite total order

The number of endomorphisms of a finite totally ordered set is given by the sequence 1, 1, 3, 10, 35, 126, 462, 1716, 6435, ... as specified by the sequence A088218. Here is a function that generates these endomorphisms:
(defn monotone-functions
[size minimum maximum]

(cond
(= size 0) (list [])
:else (mapcat
(fn [i]
(map
(comp vec (partial cons i))
(monotone-functions (dec size) i maximum)))
(range minimum (inc maximum)))))

For monotone functions on an infinite total order we can study the rate in which the function grows towards infinity but for a finite total order we know that finiteness implies that the monotone function converges to a single maximal constant. We can weakly ordered monotone functions by their eventual maximal value with gradings described by the following number triangle:
(1)
(1 2)
(1 3 6)
(1 4 10 20)
(1 5 15 35 70)
(1 6 21 56 126 252)

Another possibility is that we can partially order the monotone paths by the product order. This poset produces the following grading instead:
(1)
(1 1 1)
(1 1 2 2 2 1 1)
(1 1 2 3 4 4 5 4 4 3 2 1 1)
(1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1)

Since the weak order only requires that the last element of one endomorphism is larger then the last element of the other endomorphism and the product order requires that all elements are larger the product order is an extension of the weak order.