Paperlane

no. 14 · Friday 13 November 2026

Combinatorial results for semigroups of order-preserving mappings

Peter M. Higgins

math.CO

Abstract

We investigate combinatorial properties of the semigroup of all order- preserving mappings on {1, 2, . . . , n} and of its subsemigroup of all decreasing order-preserving mappings. We show that the cardinal of the latter is the nth Catalan number and obtain a new proof of the standard Catalan identity. Using ballot arguments and the Reflection principle we find the probability that a random order-preserving mapping is indecomposable, and via the Wallis product we show that the mean number of orbits is of order root n. By contrast, the mean number of orbits of a random decreasing mapping of this type never exceeds 3; we find the distribution of the orbit number explicitly in both cases and obtain the limiting distribution for the Catalan monoid.

comments
This is a slightly adjusted copy of my paper of that name published in 1993: Math. Proc. Camb. Phil. Soc. (1993), 113, 281-296. Printed in Great Britain. I am often asked about it (it has 125 citations on Google Scholar)
journal
Math. Proc. Camb. Phil. Soc. (1993), 113, 281-296
fields
Combinatorics
pdf ↗ page arXiv:2611.15369 ↗