WorksMathematics
Combinatorial results for semigroups of order-preserving mappings
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.
Introduction
Consider the finite set ordered in the standard way. Let denote the full transformation semigroup on , that is, the semigroup of all mappings under composition. We shall call order-preserving if implies for , and is decreasing if for all . This paper investigates combinatorial properties of the semigroup of all order-preserving mappings on , and of its subsemigroup , which consists of all decreasing and order-preserving mappings.
Combinatorial properties of have been studied over a long period under various guises and many interesting and delightful results have emerged (see, e.g. [7, 8]). Two papers concerned with combinatorial results of are [11] and [3], while little seems to have been written on . The inverse semigroup of partial one-to-one order-preserving maps has been studied by Garba [2]. Nevertheless both and have arisen naturally in language theory: any -trivial finite semigroup divides some (see [14]) while a description of the class of semigroups that are divisors of some remains an interesting open problem. It comes as a pleasant surprise that many classical results from elementary analysis and combinatorics emerge as keys to our combinatorial problems. For instance it transpires that , the th Catalan number, and indeed the standard Catalan identity (Result 1.4) follows easily from a natural partition of . Many of our counting tasks can be formulated as certain ‘ballot’ problems and thus may be solved using André’s Reflection Principle (Result 1.3). From single-variable calculus the Wallis Product arises during the calculation of the mean number of orbits of a randomly chosen and allows us to prove that this number approaches for large . By way of contrast, the mean number of orbits of never exceeds 3: we find the distribution of the orbit number explicitly in this case and obtain the limiting distribution.
2010 Mathematics Subject Classification. 20M20, 05A15, 05A19.
Key words and phrases. order-preserving mappings, transformation semigroups, Catalan numbers, ballot problems, random mappings.
This is the author’s version of the article published in Math. Proc. Camb. Phil. Soc. 113 (1993), 281–296, https://doi.org/10.1017/S0305004100075964. Received 12 March 1992; revised 31 July 1992.
We list some standard combinatorial results germane to our purposes. We shall write the binomial coefficient also as .
Result 1.1.
(i) for .
(ii) .
To see (i), consider a collection of red and blue labelled balls. The number of ways of choosing balls from this collection can be thought of as the sum, from to , of the number of ways of choosing blue balls and red balls, from which the identity follows.
To prove (ii) one can use the factorization . The coefficient of in the binomial expansion of is , while the corresponding coefficient in the geometric series for is . The coefficient in the product is then the required summation.
As explained in [11], the members of are in a natural one-to-one correspondence with the sequences of 's and 's ending in : given such a sequence the corresponding mapping is defined by the rule , where is the number of the next in the sequence following the th . From this we see
Result 1.2. .
Deleting the final in such a sequence gives us an arbitrary sequence of 's and 's which can be thought of as the result of counting a ballot in which the two candidates, and , receive and votes respectively. Such a count can be represented as a lattice path from to , where each point of the count corresponds to a lattice point , and the following point on the path is according as or polls the next vote. The lattice point then signifies a lead of votes for after votes have been counted.
Result 1.3 (the reflection principle). Let , and be positive integers. Then the number of lattice paths from to which touch or cross the -axis equals the total number of lattice paths from to .
The principle follows from the observation that there is a bijection between the two types of path defined by reflecting in the -axis the initial segment of any path of the first type up to the point where it first meets the axis (see Figure 1).
Figure 1. The reflection principle.
The bold path represents a typical lattice path from to which first meets the axis as indicated. The dotted path represents the reflection of the initial segment which, together with the remainder of the path, yields a lattice path from to . In general there will be paths of either type if and only if there is some positive integer (representing the number of down-directed edges of the path from ) such that , that is, if and only if is an even positive integer. The number of such lattice paths is then , corresponding to the number of choices for selecting the positions of the down-edges amongst the edges of the lattice path.
The th Catalan number is . Historically, was defined as the number of distinct bracketings of the -fold product . Equally, may be defined as the number of binary trees with source nodes, and as the number of ways of triangulating a convex -gon by means of non-intersecting diagonals (see [10]). The amenability of Catalan numbers to manipulation stems from the following convolution-style identity.
Result 1.4. .
This result can be verified by partition arguments appropriate to the type of collection used to define ; we provide a new argument based on partitioning in § 3.
§ 2 deals with combinatorial aspects of while corresponding results for appear in § 3. Some results for are stated along the way for the sake of comparison. The content of § 2 was in part the subject of the author’s talk at the Lisbon Conference on Lattices, Semigroups and Universal Algebra, and appears in the proceedings of that meeting [7].
Notation. We shall write , , for the mean, standard deviation, and variance respectively of a random variable (we shall also write for the latter quantity). Each can be pictured as a digraph on vertices with an arc of if . Each component of such a digraph is functional, meaning that it consists of a unique cycle, together with a number of trees rooted around the points of the cycle. The components of the digraph of correspond to the orbits of the mapping , where we say that the orbit of is . The arrows within a tree rooted on the cycle of some component of point along the path towards the root of the tree. Hence if we follow the convention that the cycles of are directed anti-clockwise, then the arrows may be deleted from the picture of without loss of information, provided that one-cycles (which correspond to fixed points) are shaded to avoid ambiguity. For further background see [8].
Proposition 1.5. The cycles of the components of each consist of a unique fixed point. Each orbit of is convex in the ordered set .
Proof. Suppose that are distinct members of some cycle of a component of , so that , for some positive integers and . Suppose that . We then obtain an increasing sequence . But , giving equality throughout, and yielding the contradiction that . The same contradiction results if , so that all cycles of the digraph of are trivial.
Next let be an orbit of with (unique) fixed point say, and let and be the respective minimum and maximum members of . Let be the respective least non-negative integers such that . Then
Let lie between and . Then either for some , or for some . In the first case we obtain
which gives , so that . A similar argument and conclusion applies in the alternative case, and so we conclude that , as required. □
Remark. It follows from Proposition 1.5 that the digraph of any is a forest of rooted, labelled trees (each vertex is labelled by a member of , and each component is a tree with a distinguished root vertex in the unique fixed point of the component). It is easy to verify that this is a necessary and sufficient condition on a subsemigroup of to ensure that is aperiodic or combinatorial, meaning that all the subgroups of are trivial. This is also equivalent to Green’s relation being trivial.
The semigroup of order-preserving mappings
Let with . An order-preserving mapping is determined by the choice of such that , where (). We can then represent as a sequence of A’s and B’s, consisting of B’s followed by an A; B’s followed by an A; ; B’s followed by an A; and finally B’s.
For example, if and then the map
is associated with the sequence . Any such sequence is determined by the choice of the places among the available for the positioning of the A’s. Hence we conclude that the number of order-preserving maps from into is .
Let stand for the random variable, the value of which is the rank of (that is, where is a randomly selected member of ).
Lemma 2.1. .
Proof. We first show that the number of order-preserving mappings such that is given by (): the first factor counts the choices for say, while the second counts the choices for the set , where is the greatest member of such that (). (Note that must equal , and thus for all .) Since is determined by the choice of the pair and different pairs determine different mappings, the assertion is established.
Now take with rank , while is a randomly chosen member of . Denote the random variable with value by . From the foregoing we obtain
(Taking thus gives the distribution of .) Hence
By Result 1.1(i) this equals
If one now takes , (2.3) yields the stated result for . Again by using (2.2) one obtains
We re-write this using the identity
We obtain, using Result 1.1(i),
Then from the general fact that we obtain
and in particular for all values of . The value of the standard deviation of is obtained by putting and taking square roots, thus completing the proof. □
Theorem 2.5. Let be the random variable with value , where are randomly selected members of . Then
Remark. If we replace by in this result then we obtain : see [6].
Proof. We prove by induction on both the stated value for and that as ; that this is true for follows from Lemma 2.1. Assume that our claim holds for some arbitrary value and let be given. From Chebyshev’s Inequality, for any positive number we have
Choose so that . Then choose sufficiently large so that and for all . Thus, for all , implies that , and hence . Therefore
for all . We conclude that for all sufficiently large values of . Now, by (2),
and this is increasing in . Hence
so that
which approaches as . Similarly, splitting the sum in (4) into two sums corresponding to and , and taking appropriate bounds yields
which also approaches as and (5) and (6) together yield that . We complete the proof by verifying inductively that as .
Write , , , , and for . For the moment let be arbitrary and consider
Write as and expand to obtain
Now by (3). Also is identically zero, so that the sum of the first two terms in (7) is . The remaining term equals
By Chebyshev’s Inequality, for any positive value of ,
Let be arbitrary, and take such that . Since , it follows that there exist intervals of length such that the probability that lies outside is less than . Take to be a fixed member of , and put . Now recall that
Hence for all . Therefore the summation of (8) is such that
Therefore we obtain that
and hence that , and since was arbitrary, it follows that , whence , as required. □
Let now denote the random variable the value of which is the number of fixed points of a randomly selected . By Proposition 1.5, also equals the component number of the digraph of , and also the number of cycle points.
The number of mappings with for all is the product of the number of order-preserving mappings from to and the number of such maps from to . By the remark preceding the proof of Lemma 2.1 the number of order-preserving maps from a set of order to a set of order is , whence we conclude that
Hence
where . From Result 1.1(ii) one now obtains the first statement in the next result.
Theorem 2.11. . Moreover as .
Proof. To verify that the mean is of order one readily shows that
This is the product of Wallis which approaches , from which we infer that . In the course of the proof of the Wallis limit it is established that
from which we obtain that
This yields
We deduce from above that the ratio on the right approaches , and thus
from which it follows that . □
Remarks. The closest analogue of this result for concerns the random variable (), the value of which is the order of the stable range of (which corresponds to the number of cycle points of the digraph of ). It is shown in [9] that
The proof of this result is based on Stirling’s factorial approximation formula and a result of Ramanujan concerning the ‘first half’ of the McLaurin series for . By contrast, the component number of has a mean that only increases logarithmically with . It is shown in [9] that if denotes the number of components of a randomly selected then
where is the Euler–Mascheroni constant. The first proof of this fact is due to Kruskal [13]. From Lemma 2.1 it follows readily that the mean value of (the rank of a random ) satisfies
The corresponding result for , the rank of a random , is noted in [9]:
Katz [12] considered the problem of finding the probability of ‘indecomposability’ of a randomly selected , by which was meant the probability that has only one component. He proved that this probability is of order . We shall now solve the corresponding problem for . The ‘ballot’ argument involved also furnishes us with the value of .
Recall from the first section the natural one-to-one correspondence between and a ballot in which candidate polls votes while candidate polls votes. Observe that is a fixed point of if and only if in the count of the corresponding ballot the th appears between the th and the th . In terms of the count, this corresponds to a tie after votes, with polling the next vote. Now to say that is indecomposable means exactly that has a unique fixed point, which, formulated in terms of the corresponding ballot count, means precisely that never surrenders the lead once he has taken it (i.e. once is strictly ahead in the count, he stays strictly ahead).
We consider a more general ballot in which polls votes while his opponent polls votes (), and we seek the probability that never relinquishes the lead once he has gained it. Let denote the set of ballots of this type, let denote the set of ballots in which never trails at any point in the count, and let . Consider , and let be the final point on the lattice path of where the count is tied. Let be the count of the lattice path which results from reflection of that portion of the path of from to in the -axis. Then and we observe that the mapping defines a bijection between and with . In fact, defines a bijection between and as consists precisely of all those counts where leads throughout, which coincides with the set of fixed points of the mapping .
We next find () by calculating the order of the complementary set of counts, which consists of all those counts during which trails at some point. The number of paths that correspond to counts where falls behind at some point equals the number of lattice paths from to which touch or cross the line . By the Reflection Principle (Result 1.3) this equals the number of lattice paths from to , which is ; the corresponds to the places where the path dips, leaving rises. Hence the probability that trails at some time during the count is . Hence the probability of the complementary event that never trails is , and this equals the probability that never loses his lead once he has gained it. By taking and replacing by we obtain our required result.
Theorem 2.12. The probability that is indecomposable is .
The semigroup of all decreasing and order-preserving mappings
We saw in the preceding section that a mapping is indecomposable if and only if in the corresponding ballot count the winning candidate never relinquishes his lead once he has gained it, and that this collection of counts is in bijection with the set of counts where never trails his opponent. We now ask what type of mapping this latter set of counts represents. Candidate never trails in the count if and only if the th vote for appears before the th vote for for ; in other words, the number of votes for preceding the th for in the sequence is always greater than or equal to . In the corresponding mapping, since each is mapped to the number of the next following the th in the sequence, this condition is equivalent to for all . Therefore the collection of mappings corresponding to the set of counts in which the winning candidate never trails is , the semigroup of order-preserving and decreasing mappings, and equals the cardinality of the set of all indecomposable mappings in . This yields our next result.
Theorem 3.1. , the th Catalan number.
Proof. From the preceding argument, together with Theorem 2.12 and Result 1.2, we have
which is the th Catalan number.
Remarks. For each collection of counts of a given ballot there corresponds a dual collection obtained by reversing the count sequence of the ballot. Given a count where never relinquishes his lead once he has gained it, the dual count has the property that never relinquishes his eventual winning lead once he has taken it. In our case, since the winning margin for is one, the characteristic conditions of both types of count are identical, so that the set of indecomposable mappings of is self-dual under this correspondence. On the other hand, the dual of the condition that never trails in the count is that ’s lead never exceeds his eventually winning margin, which in our case is tantamount to saying that ’s lead never exceeds one. This is to say that the number of the next to follow the th vote for in the count is at least , or in terms of the corresponding mapping , for all . Hence the dual to under this correspondence is the isomorphic semigroup of all increasing and order-preserving mappings on .
There are natural bijections between and other standard collections of order which thus yield alternative proofs of Theorem 3.1. We give the specific connection between and the set of all binary trees on source nodes. In this context it is more natural to take the base set to be .
By a binary tree we shall mean a complete binary tree where every node is either a source node, meaning that there are exactly two arcs from leading to its two sons, or that is an endpoint or leaf. Every node except the uppermost root of the tree is the son of exactly one source node, so that it follows that a binary tree with source nodes has nodes in all. We shall also assume that our binary trees are ordered, in the sense that the nodes are consecutively numbered in the order in which they are met while carrying out an anti-clockwise search of the tree, beginning at the root. An example of a binary tree with seven source nodes is given in Figure 2.

Figure 2. A binary tree with seven source nodes.
Given a binary tree on source nodes (and so with leaf nodes) we associate a mapping by the rule that , where leaf nodes precede the th source node in the ordering of the nodes of . To see that observe that our rule certainly defines an order-preserving map on , and since the final source node precedes its two sons in the ordering of the nodes, the maximum possible value of is . We can then prove by induction on that also has the decreasing property: remove the two sons of the final source node from to give a binary tree on source nodes, which, by induction, we may assume is associated with a member of by the above rule. Indeed, the mapping associated with is just the restriction of the mapping to , and so, by the inductive hypothesis, we have that is decreasing, and we have already observed that , allowing us to conclude that . The mapping associated with our binary tree above has its ordered list of images of the members of the tuple .
Conversely, we can associate with any a binary tree on source nodes using the inverse of the foregoing procedure. Suppose inductively that we have associated with a binary tree on source nodes in such a way that is associated with by the procedure of the preceding paragraph. Let denote . The tree has leaf nodes. Take the th leaf node (with ), and replace it by a source node to form the binary tree . By construction, the mapping associated with is , as required.
The number of indecomposable is easily obtained through our ballot correspondence. In terms of the corresponding count,
if and only if never trails in the count,
is indecomposable if and only if never relinquishes the lead once gained.
The conjunction of this pair of conditions is equivalent to the single constraint that leads the count throughout. The enumeration of such counts is the classical Bertrand–Whitworth ballot problem, readily solved by the Reflection Principle (see [1] or [10]), and in general, the probability of such a ballot is . Again, upon putting and replacing by we see that the proportion of such mappings in is
This yields
Proposition 3.2. The proportion of indecomposable mappings in is
It is interesting here that the probability decreases to , and not to , as is the case with and . This suggests the existence of a limiting distribution for , where denotes the component number of a randomly chosen . Our determination of this limiting distribution involves the use of the standard Catalan identity for which we can now offer a new proof.
Proof of Result 1.4. Partition into disjoint sets , where if is the greatest integer such that . Note that if and only if is the unique fixed point of , which is to say that is indecomposable. Then
Now , since, in general, the number of indecomposable mappings in is . Hence
We can use this result to show that the expected number of components of a random is a monotonic function of increasing to a limit of . This contrasts with Theorem 2.11 which shows that the mean component number in is of order .
Proposition 3.3. where is the component number of a random .
Proof. We have
Let .
Lemma 3.4.
Proof. Using Proposition 3.2 we have
as asserted. Using the argument of the proof of Result 1.4, we focus attention on the final fixed point of a mapping in and conclude that
by Result 1.4, and , as required.
We next establish the recurrence
The above calculation shows that (9) is valid for (as ). Take . By considering the final fixed point of with exactly fixed points we see that
By considering the penultimate fixed point we also have
But we know that , and so, by substituting accordingly in (11), we obtain
Therefore , as asserted.
It is now a routine matter, using a double induction on and , to verify that the solution to our recurrence is given by
for .
Theorem 3.8. The probability distribution for the random variable , the component number of a random , is given by
for .
As increases, approaches in distribution and in moments the random variable , where for . In particular, the limiting values of the mean and variance are 3 and 2 respectively. Furthermore, for , the probability sequence is bi-modal, with modes and , and is strictly monotonically decreasing for , features shared with the limiting distribution .
Proof. Except for the statement about moments, this is now immediate: from Theorem 3.1 and Lemma 3.4 we obtain
which simplifies to yield the expression (3.9). That follows on dividing each of the last terms in the numerator and denominator by , so that approaches in distribution. From (3.9) we deduce the recurrence
for from which the statements on modes and on monotonicity follow. The statement on convergence in moments can be deduced from the following fact.
Lemma 3.11. If then for and for .
Proof. Direct calculation using (3.9) allows one to verify the assertions of the Lemma for and 4. It remains only to observe that if for some , then (3.10) yields
from which we infer that . The result now follows by induction on .
To show convergence in moments, first observe that certainly exists for (indeed the values of are integers, and can be calculated recursively). Let be a positive integer, and let be given. Choose such that
Then, for any positive integer $n,
Since approaches in distribution, it follows that for sufficiently large the first term is less than ; the same is true of the second term, and of the third which is bounded by the second. Hence, for all sufficiently large, , and so approaches in moments also. □
Remark. Using the fact that for all sufficiently large, it can be shown that for all positive integers and .
The probability distribution for the component number of a random can be calculated explicitly in a similar fashion. Let us now write for the component number of a randomly chosen , and let be the cardinality of .
Theorem 3.12. Let , where is the component number of a random . Then
The distribution of has a unique mode at , the greatest integer not exceeding , unless is a perfect square, in which case is another mode. The distribution decreases monotonically on either side of the mode(s) with the minimum occurring at . Furthermore, as .
Proof. Assertion (3.13) for is Theorem 2.12; in this case . In order to establish (3.13) for it is enough, by Result 1.2, to verify that
We do this by proving the analogue of Lemma 3.4.
Lemma 3.15. for .
Proof. Let be a typical member of with exactly two components, and thus two fixed points, , say. Bearing in mind the convexity of the orbits of (Proposition 1.5), and letting be the maximum of the orbit of , we see that
Applying Result 1.4 then yields that
In other words, , in agreement with the statement of our lemma.
Next, for , by considering the final, and then the penultimate fixed point of a mapping from with exactly fixed points, we obtain the expressions
Replacing by in (17) yields that
From (16) we see that the first term can be written as
while the summation in the second term equals
Combining these expressions yields
as required. □
A routine calculation now shows that the expression for given in (15) is correct, and thus (14) is also.
From (14) comes the recurrence relation
From (18) it follows that
with equality occurring in both sides simultaneously. Using to denote the greatest integer not exceeding a real number , we see that if is not an integer then has a unique mode at , while otherwise is bi-modal with modes . That the distribution of falls away monotonically on either side of the mode(s) follows from (19), and that the minimum value of occurs at follows by comparing with . Finally, from (14),
and since the bracketed term approaches for large , it follows that as . □
In [11], the cardinality of , the set of idempotents of , was shown to be , the th Fibonacci number. This was achieved by solving a certain recurrence relation. Determining the order of is, however, a simple matter, for any is determined by , the image of . To see this, first recall that is an idempotent if and only if and the set of fixed points of coincide. If we further suppose that then, for any , , is a fixed point of , and since preserves order, must be the greatest fixed point less than or equal to . Hence an idempotent of is determined by its image and thus . Now the subsets of which occur as images of mappings are exactly the subsets of that contain . This yields the first statement in our final result.
Theorem 3.19. . Furthermore, .
Proof. We have , from which one obtains , where is the Wallis product as in the proof of Theorem 2.11. Hence we deduce that as , as required. □
Remark. For an investigation of the number of idempotents of finite full transformation semigroups see [4] and [5].
References
- [1]W. Feller. An Introduction to Probability Theory and its Applications, 3rd edn. vol. 1 (Wiley, 1968).
- [2]G. U. Garba. Nilpotents in semigroups of partial one-to-one order-preserving mappings. Semigroup Forum 41 (1991), 1–15.
- [3]G. M. S. Gomes and J. M. Howie. On the ranks of certain semigroups of order-preserving transformations. Semigroup Forum 40 (1990), 1–15.
- [4]B. Harris. A note on the number of idempotents in symmetric semigroups. J. Combin. Theory Ser. A 3 (1967), 1234–1235.DOI
- [5]B. Harris and L. Schoenfeld. The number of idempotent elements in symmetric semigroups. J. Combin. Theory Ser. A 3 (1967), 12–135.DOI
- [6]P. M. Higgins. The range order of a product of i transformations from a finite full transformation semigroup. Semigroup Forum 37 (1988), 31–36.DOI
- [7]P. M. Higgins. Random products in semigroups of mappings. In Lattices, Semigroups and Universal Algebra (editors J. Almeida et al.), (Plenum Press, 1990), pp. 89–100.DOI
- [8]P. M. Higgins. Techniques of Semigroup Theory (Oxford University Press, 1992).DOI
- [9]P. M. Higgins and E. J. Williams. Random functions on a finite set. Ars Combin. 26A (1988), 93–102.
- [10]P. Hilton and J. Pedersen. Catalan numbers, their generalization, and their uses. Math. Intelligencer 13 (1991), 64–75.DOI
- [11]J. M. Howie. Products of idempotents in certain semigroups of transformations. Proc. Roy. Soc. Edinburgh Sect. A 17 (1971), 223–236.DOI
- [12]L. Katz. Probability of indecomposability of a random mapping function. Ann. Math. Statist. 26 (1955), 512–517.DOI
- [13]M. D. Kruskal. The expected number of components under a random mapping function. Amer. Math. Monthly 61 (1954), 392–397.DOI
- [14]J. E. Pin. Varieties of Formal Languages (Plenum Press, 1986).DOI
