betaFeedback

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 Xn={1,2,…,n}X_n=\{1,2,\ldots,n\} ordered in the standard way. Let TnT_n denote the full transformation semigroup on XnX_n, that is, the semigroup of all mappings α:Xn→Xn\alpha:X_n\to X_n under composition. We shall call α\alpha order-preserving if i≤ji\leq j implies iα≤jαi\alpha\leq j\alpha for i,j∈Xni,j\in X_n, and α\alpha is decreasing if iα≤ii\alpha\leq i for all i∈Xni\in X_n. This paper investigates combinatorial properties of the semigroup On\mathcal{O}_n of all order-preserving mappings on XnX_n, and of its subsemigroup Cn\mathcal{C}_n, which consists of all decreasing and order-preserving mappings.

Combinatorial properties of TnT_n 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 On\mathcal{O}_n are [11] and [3], while little seems to have been written on Cn\mathcal{C}_n. The inverse semigroup of partial one-to-one order-preserving maps has been studied by Garba [2]. Nevertheless both On\mathcal{O}_n and Cn\mathcal{C}_n have arisen naturally in language theory: any J\mathcal{J}-trivial finite semigroup divides some Cn\mathcal{C}_n (see [14]) while a description of the class of semigroups that are divisors of some On\mathcal{O}_n 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 ∣Cn∣=Cn|\mathcal{C}_n|=C_n, the nnth Catalan number, and indeed the standard Catalan identity (Result 1.4) follows easily from a natural partition of Cn\mathcal{C}_n. 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 α∈On\alpha\in\mathcal{O}_n and allows us to prove that this number approaches 12nπ\frac{1}{2}\sqrt{n\pi} for large nn. By way of contrast, the mean number of orbits of α∈Cn\alpha\in\mathcal{C}_n 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 (nr)\binom{n}{r} also as C(n,r)C(n,r).

Result 1.1.

(i) ∑k=0nC(n,k)C(m,k)=C(n+m,m)\sum_{k=0}^{n} C(n,k)C(m,k)=C(n+m,m) for n≤mn\le m.

(ii) ∑k=0nC(2k,k)C(2n−2k,n−k)=4n\sum_{k=0}^{n} C(2k,k)C(2n-2k,n-k)=4^n.

To see (i), consider a collection of nn red and mm blue labelled balls. The number of ways of choosing mm balls from this collection can be thought of as the sum, from k=0k=0 to nn, of the number of ways of choosing kk blue balls and m−km-k red balls, from which the identity follows.

To prove (ii) one can use the factorization (1−4x)−1=(1−4x)−12⋅(1−4x)−12(1-4x)^{-1}=(1-4x)^{-\frac{1}{2}}\cdot(1-4x)^{-\frac{1}{2}}. The coefficient of xnx^n in the binomial expansion of (1−4x)−12(1-4x)^{-\frac{1}{2}} is C(2n,n)C(2n,n), while the corresponding coefficient in the geometric series for (1−4x)−1(1-4x)^{-1} is 4n4^n. The coefficient in the product is then the required summation.

As explained in [11], the members of OnO_n are in a natural one-to-one correspondence with the sequences of nn AA's and nn BB's ending in BB: given such a sequence the corresponding mapping α∈On\alpha\in O_n is defined by the rule iα=ji\alpha=j, where jj is the number of the next BB in the sequence following the iith AA. From this we see

Result 1.2. ∣On∣=C(2n−1,n−1)|O_n|=C(2n-1,n-1).

Deleting the final BB in such a sequence gives us an arbitrary sequence of nn AA's and (n−1)(n-1) BB's which can be thought of as the result of counting a ballot in which the two candidates, AA and BB, receive nn and n−1n-1 votes respectively. Such a count can be represented as a lattice path from (0,0)(0,0) to (2n−1,1)(2n-1,1), where each point of the count corresponds to a lattice point (p,q)(p,q), and the following point on the path is (p+1,q±1)(p+1,q\pm1) according as AA or BB polls the next vote. The lattice point (p,q)(p,q) then signifies a lead of qq votes for AA after pp votes have been counted.

Result 1.3 (the reflection principle). Let aa, bb and cc be positive integers. Then the number of lattice paths from (0,a)(0,a) to (b,c)(b,c) which touch or cross the xx-axis equals the total number of lattice paths from (0,−a)(0,-a) to (b,c)(b,c).

The principle follows from the observation that there is a bijection between the two types of path defined by reflecting in the xx-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 (0,a)(0,a) to (b,c)(b,c) 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 (0,−a)(0,-a) to (b,c)(b,c). In general there will be paths of either type if and only if there is some positive integer dd (representing the number of down-directed edges of the path from (0,−a)(0,-a)) such that 2d+a+c=b2d+a+c=b, that is, if and only if b−(a+c)b-(a+c) is an even positive integer. The number of such lattice paths is then C(b,d)C(b,d), corresponding to the number of choices for selecting the positions of the dd down-edges amongst the bb edges of the lattice path.

The nnth Catalan number CnC_n is C(2n,n)/(n+1)=C(2n,n−1)/nC(2n,n)/(n+1)=C(2n,n-1)/n. Historically, CnC_n was defined as the number of distinct bracketings of the (n+1)(n+1)-fold product x1x2⋯xn+1x_1x_2\cdots x_{n+1}. Equally, CnC_n may be defined as the number of binary trees with nn source nodes, and as the number of ways of triangulating a convex (n+2)(n+2)-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. ∑k=1nCk−1Cn−k=Cn\sum_{k=1}^{n} C_{k-1}C_{n-k}=C_n.

This result can be verified by partition arguments appropriate to the type of collection used to define CnC_n; we provide a new argument based on partitioning CnC_n in § 3.

§ 2 deals with combinatorial aspects of OnO_n while corresponding results for CnC_n appear in § 3. Some results for TnT_n 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 μX\mu_X, σX\sigma_X, σX2\sigma_X^2 for the mean, standard deviation, and variance respectively of a random variable XX (we shall also write Var⁡(X)\operatorname{Var}(X) for the latter quantity). Each α∈Tn\alpha\in T_n can be pictured as a digraph on nn vertices with ijij an arc of α\alpha if iα=ji\alpha=j. 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 α\alpha correspond to the orbits of the mapping α\alpha, where we say that the orbit of i∈Xni\in X_n is {j∈Xn:iαr=jαs for some positive integers r,s}\{j\in X_n:i\alpha^r=j\alpha^s\text{ for some positive integers }r,s\}. The arrows within a tree rooted on the cycle of some component of α\alpha point along the path towards the root of the tree. Hence if we follow the convention that the cycles of α\alpha are directed anti-clockwise, then the arrows may be deleted from the picture of α\alpha 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 α∈On\alpha\in O_n each consist of a unique fixed point. Each orbit of α∈On\alpha\in O_n is convex in the ordered set XnX_n.

Proof. Suppose that i,j∈Xni,j\in X_n are distinct members of some cycle of a component of α\alpha, so that j=iαrj=i\alpha^r, i=jαsi=j\alpha^s for some positive integers rr and ss. Suppose that i<iαi<i\alpha. We then obtain an increasing sequence i,iα,iα2,…,iαr=j,iαr+1,…,iαr+si,i\alpha,i\alpha^2,\ldots,i\alpha^r=j,i\alpha^{r+1},\ldots,i\alpha^{r+s}. But iαr+s=jαs=ii\alpha^{r+s}=j\alpha^s=i, giving equality throughout, and yielding the contradiction that i=ji=j. The same contradiction results if i>iαi>i\alpha, so that all cycles of the digraph of α∈On\alpha\in O_n are trivial.

Next let CC be an orbit of α∈On\alpha\in O_n with (unique) fixed point pp say, and let cc and dd be the respective minimum and maximum members of CC. Let r,sr,s be the respective least non-negative integers such that cαr=dαs=pc\alpha^r=d\alpha^s=p. Then

c<cα<cα2<⋯<cαr=p=dαs<dαs−1<⋯<dα<d.c<c\alpha<c\alpha^2<\cdots<c\alpha^r=p=d\alpha^s<d\alpha^{s-1}<\cdots<d\alpha<d.

Let k∈Xnk \in X_n lie between cc and dd. Then either cαm≤k≤cαm+1c\alpha^m \le k \le c\alpha^{m+1} for some 0≤m≤r−10 \le m \le r-1, or dαm≥k≥dαm+1d\alpha^m \ge k \ge d\alpha^{m+1} for some 0≤m≤s−10 \le m \le s-1. In the first case we obtain

p=cαr=cαm+r≤kαr≤cαm+1+r=p,p=c\alpha^r=c\alpha^{m+r}\le k\alpha^r\le c\alpha^{m+1+r}=p,

which gives kαr=pk\alpha^r=p, so that k∈Ck \in C. A similar argument and conclusion applies in the alternative case, and so we conclude that C={k∈Xn:c≤k≤d}C=\{k \in X_n:c\le k\le d\}, as required. □

Remark. It follows from Proposition 1.5 that the digraph of any α∈On\alpha\in O_n is a forest of rooted, labelled trees (each vertex is labelled by a member of XnX_n, 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 SS of TnT_n to ensure that SS is aperiodic or combinatorial, meaning that all the subgroups of SS are trivial. This is also equivalent to Green’s H\mathcal{H} relation being trivial.

The semigroup of order-preserving mappings

Let Sr={m1,m2,…,mr}S_r=\{m_1,m_2,\ldots,m_r\} with 1≤m1<m2<⋯<mr≤n1\le m_1<m_2<\cdots<m_r\le n. An order-preserving mapping α:Sr→Xn\alpha:S_r\to X_n is determined by the choice of p1,p2,…,prp_1,p_2,\ldots,p_r such that 1≤p1≤p2≤⋯≤pr≤n1\le p_1\le p_2\le\cdots\le p_r\le n, where miα=pim_i\alpha=p_i (i=1,2,…,ri=1,2,\ldots,r). We can then represent α\alpha as a sequence of rr A’s and nn B’s, consisting of p1−1p_1-1 B’s followed by an A; p2−p1p_2-p_1 B’s followed by an A; …\ldots; pr−pr−1p_r-p_{r-1} B’s followed by an A; and finally n−pr+1n-p_r+1 B’s.

For example, if n=6n=6 and Sr={1,2,4,6}S_r=\{1,2,4,6\} then the map

(12461335)\begin{pmatrix}1&2&4&6\\1&3&3&5\end{pmatrix}

is associated with the sequence ABBAABBABBABBAABBABB. Any such sequence is determined by the choice of the rr places among the r+n−1r+n-1 available for the positioning of the A’s. Hence we conclude that the number of order-preserving maps from SrS_r into XnX_n is C(r+n−1,r)=C(r+n−1,n−1)C(r+n-1,r)=C(r+n-1,n-1).

Let Yn(α)Y_n(\alpha) stand for the random variable, the value of which is the rank of α\alpha (that is, ∣im⁡α∣|\operatorname{im}\alpha| where α\alpha is a randomly selected member of OnO_n).

Lemma 2.1. E(Yn)=n2/(2n−1),σYn=(n−1)/2⋅n/(2n−1)\mathop{\mathrm{E}}(Y_n)=n^2/(2n-1),\qquad\sigma_{Y_n}=\sqrt{(n-1)/2}\cdot n/(2n-1).

Proof. We first show that the number of order-preserving mappings α:Sr→Xn\alpha:S_r\to X_n such that rank⁡α=k\operatorname{rank}\alpha=k is given by C(n,k)⋅C(r−1,k−1)C(n,k)\cdot C(r-1,k-1) (1≤k≤r1\le k\le r): the first factor counts the choices for im⁡α={i1,i2,…,ik}\operatorname{im}\alpha=\{i_1,i_2,\ldots,i_k\} say, while the second counts the choices for the set Pα={p1,p2,…,pk}P_\alpha=\{p_1,p_2,\ldots,p_k\}, where pjp_j is the greatest member of SrS_r such that pjα=ijp_j\alpha=i_j (1≤j≤k1\le j\le k). (Note that pkp_k must equal mrm_r, and thus pj<mrp_j<m_r for all j<kj<k.) Since α\alpha is determined by the choice of the pair (im⁡α,Pα)(\operatorname{im}\alpha,P_\alpha) and different pairs determine different mappings, the assertion is established.

Now take α∈On\alpha\in O_n with rank α=r\alpha=r, while β\beta is a randomly chosen member of OnO_n. Denote the random variable with value rank⁡αβ\operatorname{rank}\alpha\beta by Yn,rY_{n,r}. From the foregoing we obtain

Pr⁡(Yn,r=k)=C(n,k)C(r−1,k−1)C(r+n−1,n−1).(1)\Pr(Y_{n,r}=k)=\frac{C(n,k)C(r-1,k-1)}{C(r+n-1,n-1)}. \tag*{(1)}

(Taking r=nr=n thus gives the distribution of YnY_n.) Hence

E(Yn,r)=(C(r+n−1,n−1))−1∑k=1rkC(n,k)C(r−1,k−1)=nC(r+n−1,n−1)∑k=0r−1C(n−1,k)C(r−1,k).\mathbb{E}(Y_{n,r})=\left(C(r+n-1,n-1)\right)^{-1}\sum_{k=1}^{r}kC(n,k)C(r-1,k-1) =\frac{n}{C(r+n-1,n-1)}\sum_{k=0}^{r-1}C(n-1,k)C(r-1,k).

By Result 1.1(i) this equals

nC(r+n−1,n−1)⋅C(r+n−2,n−1)=nrn+r−1.(2)\frac{n}{C(r+n-1,n-1)}\cdot C(r+n-2,n-1)=\frac{nr}{n+r-1}. \tag*{(2)}

If one now takes r=nr=n, (2.3) yields the stated result for E(Yn)=E(Yn,n)\mathbb{E}(Y_n)=\mathbb{E}(Y_{n,n}). Again by using (2.2) one obtains

E(Yn,r(Yn,r−1))=(C(r+n−1,n−1))−1∑k=2rk(k−1)C(n,k)C(r−1,k−1)=n(r−1)C(r+n−1,n−1)∑k=1r−1C(n−1,k)C(r−2,k−1).\mathbb{E}\left(Y_{n,r}(Y_{n,r}-1)\right)=\left(C(r+n-1,n-1)\right)^{-1}\sum_{k=2}^{r}k(k-1)C(n,k)C(r-1,k-1) =\frac{n(r-1)}{C(r+n-1,n-1)}\sum_{k=1}^{r-1}C(n-1,k)C(r-2,k-1).

We re-write this using the identity

C(r−2,k−1)=C(r−1,k)−C(r−2,k).C(r-2,k-1)=C(r-1,k)-C(r-2,k).

We obtain, using Result 1.1(i),

E(Yn,r(Yn,r−1))=n(r−1)C(r+n−1,n−1)(∑k=1r−1C(n−1,k)C(r−1,k)−∑k=1r−1C(n−1,k)C(r−2,k))=n(r−1)(C(n+r−2,r−1)−1−(C(n+r−3,r−2)−1))C(r+n−1,n−1)=n(n−1)r(r−1)(n+r−1)(n+r−2).\begin{aligned} \mathbb{E}\left(Y_{n,r}(Y_{n,r}-1)\right) &=\frac{n(r-1)}{C(r+n-1,n-1)} \left(\sum_{k=1}^{r-1}C(n-1,k)C(r-1,k)\right.\\ &\qquad\left.-\sum_{k=1}^{r-1}C(n-1,k)C(r-2,k)\right)\\ &=\frac{n(r-1)\left(C(n+r-2,r-1)-1-\left(C(n+r-3,r-2)-1\right)\right)} {C(r+n-1,n-1)}\\ &=\frac{n(n-1)r(r-1)}{(n+r-1)(n+r-2)}. \end{aligned}

Then from the general fact that σX2=E(X(X−1))−E(X)(E(X)−1)\sigma_X^2=\mathbb{E}(X(X-1))-\mathbb{E}(X)(\mathbb{E}(X)-1) we obtain

Var⁡(Yn,r)=n(n−1)r(r−1)(n+r−1)2(n+r−2).(3)\operatorname{Var}(Y_{n,r})=\frac{n(n-1)r(r-1)}{(n+r-1)^2(n+r-2)}. \tag*{(3)}

and in particular Var⁡(Yn,r)<n\operatorname{Var}(Y_{n,r})<n for all values of r=1,2,…,nr=1,2,\ldots,n. The value of the standard deviation of YnY_n is obtained by putting r=nr=n and taking square roots, thus completing the proof. □

Theorem 2.5. Let ZkZ_k be the random variable with value n−1rank⁡(α1α2⋯αk)n^{-1}\operatorname{rank}(\alpha_1\alpha_2\cdots\alpha_k), where α1,α2,…,αk\alpha_1,\alpha_2,\ldots,\alpha_k are randomly selected members of On\mathcal{O}_n. Then

Mk=lim⁡n→∞E(Zk)=1/(1+k)for all k≥1.M_k=\lim_{n\to\infty}\mathbb{E}(Z_k)=1/(1+k)\quad\text{for all }k\ge1.

Remark. If we replace On\mathcal{O}_n by Tn\mathcal{T}_n in this result then we obtain Mk∼2/kM_k\sim2/k: see [6].

Proof. We prove by induction on kk both the stated value for MkM_k and that σZk→0\sigma_{Z_k} \to0 as n→∞n \to\infty; that this is true for k=1k=1 follows from Lemma 2.1. Assume that our claim holds for some arbitrary value k−1≥1k-1 \ge1 and let δ,ϵ>0\delta,\epsilon> 0 be given. From Chebyshev’s Inequality, for any positive number RR we have

Pr⁡(∣Zk−1−μk−1∣≥RσZk−1)≤1R2,where μk−1=E(Zk−1).\Pr\left(\lvert Z_{k-1}-\mu_{k-1}\rvert\ge R\sigma_{Z_{k-1}}\right) \le\frac{1}{R^2}, \qquad\text{where } \mu_{k-1}=\mathbb{E}(Z_{k-1}).

Choose RR so that 1/R2<ϵ1/R^2 < \epsilon. Then choose NN sufficiently large so that RσZk−1<δ/2R\sigma_{Z_{k-1}} < \delta/2 and ∣μk−1−Mk−1∣<δ/2\lvert\mu_{k-1}-M_{k-1}\rvert< \delta/2 for all n≥Nn \ge N. Thus, for all n≥Nn \ge N, ∣Zk−1−Mk−1∣≥δ\lvert Z_{k-1}-M_{k-1}\rvert\ge\delta implies that ∣Zk−1−μk−1∣+∣μk−1−Mk−1∣≥δ\lvert Z_{k-1}-\mu_{k-1}\rvert+\lvert\mu_{k-1}-M_{k-1}\rvert\ge\delta, and hence ∣Zk−1−μk−1∣≥δ/2\lvert Z_{k-1}-\mu_{k-1}\rvert\ge\delta/2. Therefore

Pr⁡(∣Zk−1−Mk−1∣≥δ)≤Pr⁡(∣Zk−1−μk−1∣≥δ/2)<ϵ\Pr\left(\lvert Z_{k-1}-M_{k-1}\rvert\ge\delta\right) \le\Pr\left(\lvert Z_{k-1}-\mu_{k-1}\rvert\ge\delta/2\right) < \epsilon

for all n≥Nn \ge N. We conclude that Pr⁡(∣Zk−1−Mk−1∣<δ)≥1−ϵ\Pr(\lvert Z_{k-1}-M_{k-1}\rvert< \delta) \ge1-\epsilon for all sufficiently large values of nn. Now, by (2),

E(Zk∣Zk−1=r/n)=rn+r−1=r/n1+r/n−1/n,\mathbb{E}(Z_k\mid Z_{k-1}=r/n)=\frac{r}{n+r-1}=\frac{r/n}{1+r/n-1/n},

and this is increasing in rr. Hence

E(Zk)=∑r=1nPr⁡(Zk−1=r/n)E(Zk∣Zk−1=r/n)≥∑r/n≥Mk−1−δPr⁡(Zk−1=r/n)E(Zk∣Zk−1=Mk−1−δ).(4)\begin{aligned} \mathbb{E}(Z_k)=\sum_{r=1}^{n}\Pr(Z_{k-1}=r/n)\mathbb{E}(Z_k\mid Z_{k-1}=r/n) \\ &\ge\sum_{r/n\ge M_{k-1}-\delta}\Pr(Z_{k-1}=r/n)\mathbb{E}(Z_k\mid Z_{k-1}=M_{k-1}-\delta). \tag*{(4)} \end{aligned}

so that

E(Zk)≥n(1−ϵ)(1/k−δ)n+n(1/k−δ)−1→(1−ϵ)(1/k−δ)1+1/k−δ=(1−ϵ)(1−kδ)1+k−kδas n→∞,(5)\mathbb{E}(Z_k)\ge\frac{n(1-\epsilon)(1/k-\delta)}{n+n(1/k-\delta)-1}\to\frac{(1-\epsilon)(1/k-\delta)}{1+1/k-\delta}=\frac{(1-\epsilon)(1-k\delta)}{1+k-k\delta}\quad\text{as }n\to\infty, \tag*{(5)}

which approaches 1/(1+k)1/(1+k) as δ,ϵ→0\delta,\epsilon\to0. Similarly, splitting the sum in (4) into two sums corresponding to r/n≤Mk−1+δr/n\le M_{k-1}+\delta and r/n>Mk−1+δr/n>M_{k-1}+\delta, and taking appropriate bounds yields

E(Zk)≤n(1/k+δ)n+n(1/k+δ)−1+ϵ⋅1→1+kδ1+k+kδ+ϵ(6)\mathbb{E}(Z_k)\le\frac{n(1/k+\delta)}{n+n(1/k+\delta)-1}+\epsilon\cdot1\to\frac{1+k\delta}{1+k+k\delta}+\epsilon \tag*{(6)}

which also approaches 1/(1+k)1/(1+k) as δ,ϵ→0\delta,\epsilon\to0 and (5) and (6) together yield that Mk=1/(1+k)M_k=1/(1+k). We complete the proof by verifying inductively that σZk→0\sigma_{Z_k}\to0 as n→∞n\to\infty.

Write Wk=nZkW_k=nZ_k, pi=Pr⁡(Wk=i)p_i=\Pr(W_k=i), pij=Pr⁡(Wk=i∣Wk−1=j)p_{ij}=\Pr(W_k=i\mid W_{k-1}=j), qj=Pr⁡(Wk−1=j)q_j=\Pr(W_{k-1}=j), and μj=E(Wk∣Wk−1=j)\mu_j=\mathbb{E}(W_k\mid W_{k-1}=j) for 1≤i,j≤n1\le i,j\le n. For the moment let aa be arbitrary and consider

∑i=1npi(i−a)2=∑j=1n(∑i=1npijqj)(i−a)2=∑j=1nqj(∑i=1npij(i−a)2).\sum_{i=1}^{n}p_i(i-a)^2=\sum_{j=1}^{n}\left(\sum_{i=1}^{n}p_{ij}q_j\right)(i-a)^2=\sum_{j=1}^{n}q_j\left(\sum_{i=1}^{n}p_{ij}(i-a)^2\right).

Write i−ai-a as i−μj+μj−ai-\mu_j+\mu_j-a and expand to obtain

∑j=1nqj(∑i=1npij(i−μj)2+2∑i=1npij(i−μj)(μj−a)+∑i=1npij(a−μj)2).(7)\sum_{j=1}^{n}q_j\left(\sum_{i=1}^{n}p_{ij}(i-\mu_j)^2+2\sum_{i=1}^{n}p_{ij}(i-\mu_j)(\mu_j-a)+\sum_{i=1}^{n}p_{ij}(a-\mu_j)^2\right). \tag*{(7)}

Now ∑i=1npij(i−μj)2=σYn,j2=O(n)\sum_{i=1}^{n}p_{ij}(i-\mu_j)^2=\sigma^2_{Y_{n,j}}=O(n) by (3). Also ∑i=1npij(i−μj)\sum_{i=1}^{n}p_{ij}(i-\mu_j) is identically zero, so that the sum of the first two terms in (7) is O(n)O(n). The remaining term equals

∑j=1n(qj(a−μj)2∑i=1npij)=∑j=1nqj(a−μj)2.(8)\sum_{j=1}^{n}\left(q_j(a-\mu_j)^2\sum_{i=1}^{n}p_{ij}\right)=\sum_{j=1}^{n}q_j(a-\mu_j)^2. \tag*{(8)}

By Chebyshev’s Inequality, for any positive value of RR,

Pr⁡(∣Wk−1−μk−1∣≥RσWk−1)≤1R2.\Pr\left(\lvert W_{k-1}-\mu_{k-1}\rvert\ge R\sigma_{W_{k-1}}\right)\le\frac{1}{R^2}.

Let ϵ>0\epsilon>0 be arbitrary, and take RR such that 1/R2<ϵ1/R^2<\epsilon. Since RσWk−1=o(n)R\sigma_{W_{k-1}}=o(n), it follows that there exist intervals InI_n of length o(n)o(n) such that the probability that Wk−1W_{k-1} lies outside InI_n is less than ϵ\epsilon. Take i=i(n)i=i(n) to be a fixed member of In∩XnI_n\cap X_n, and put a=E(Wk∣Wk−1=i)a=\mathbb{E}(W_k\mid W_{k-1}=i). Now recall that

E(Wk∣Wk−1=r)=rnr+n−1=f(r) say,∣f′(r)∣=n(n−1)(n+r−1)2<1for all r≥1.\mathbb{E}(W_k\mid W_{k-1}=r)=\frac{rn}{r+n-1}=f(r)\text{ say},\qquad\lvert f'(r)\rvert=\frac{n(n-1)}{(n+r-1)^2}<1\quad\text{for all }r\ge1.

Hence ∣a−E(Wk∣Wk−1=j)∣≤∣i−j∣=o(n)\lvert a-\mathbb{E}(W_k\mid W_{k-1}=j)\rvert\le\lvert i-j\rvert=o(n) for all j∈In∩Xnj\in I_n\cap X_n. Therefore the summation Σ\Sigma of (8) is such that

Σ=∑j∈InPr⁡(Wk−1=j)(a−E(Wk∣Wk−1=j))2+∑j∉InPr⁡(Wk−1=j)(a−E(Wk∣Wk−1=j))2≤o(n2)+ϵ⋅n2.\begin{aligned} \Sigma={}&\sum_{j\in I_n}\Pr(W_{k-1}=j)\left(a-\mathbb{E}(W_k\mid W_{k-1}=j)\right)^2\\ &+\sum_{j\notin I_n}\Pr(W_{k-1}=j)\left(a-\mathbb{E}(W_k\mid W_{k-1}=j)\right)^2\\ &\le o(n^2)+\epsilon\cdot n^2. \end{aligned}

Therefore we obtain that

σWk2≤∑i=1npi(i−a)2≤O(n)+o(n2)+ϵ⋅n2.\sigma^2_{W_k}\le\sum_{i=1}^{n}p_i(i-a)^2\le O(n)+o(n^2)+\epsilon\cdot n^2.

and hence that σZk2≤o(1)+ϵ\sigma^2_{Z_k}\le o(1)+\epsilon, and since ϵ\epsilon was arbitrary, it follows that σZk2=o(1)\sigma^2_{Z_k}=o(1), whence σZk=o(1)\sigma_{Z_k}=o(1), as required. □

Let Zn(α)Z_n(\alpha) now denote the random variable the value of which is the number of fixed points of a randomly selected α∈On\alpha\in O_n. By Proposition 1.5, Zn(α)Z_n(\alpha) also equals the component number of the digraph of α\alpha, and also the number of cycle points.

The number of mappings α∈On\alpha\in O_n with kα=kk\alpha=k for all k∈Xnk\in X_n is the product of the number of order-preserving mappings from Xk−1X_{k-1} to XkX_k and the number of such maps from Xn−kX_{n-k} to Xn−k+1X_{n-k+1}. By the remark preceding the proof of Lemma 2.1 the number of order-preserving maps from a set of order rr to a set of order nn is C(r+n−1,n−1)C(r+n-1,n-1), whence we conclude that

Pr⁡(kα=k)=C(2k−2,k−1)C(2n−2k,n−k)C(2n−1,n−1).\Pr(k\alpha=k)=\frac{C(2k-2,k-1)C(2n-2k,n-k)}{C(2n-1,n-1)}.

Hence

E(Zn)=∑k=1nPr⁡(kα=k)=C(2n−1,n−1)−1∑k=1nC(2k−2,k−1)C(2n−2k,n−k)=C(2n−1,n−1)−1∑k=0mC(2k,k)C(2m−2k,m−k),\begin{aligned} \mathbb{E}(Z_n)=\sum_{k=1}^{n}\Pr(k\alpha=k) \\ &=C(2n-1,n-1)^{-1}\sum_{k=1}^{n}C(2k-2,k-1)C(2n-2k,n-k) \\ &=C(2n-1,n-1)^{-1}\sum_{k=0}^{m}C(2k,k)C(2m-2k,m-k), \end{aligned}

where m=n−1m=n-1. From Result 1.1(ii) one now obtains the first statement in the next result.

Theorem 2.11. E(Zn)=4n−1/C(2n−1,n−1)\mathbb{E}(Z_n)=4^{n-1}/C(2n-1,n-1). Moreover (E(Zn)−nπ/2)→0(\mathbb{E}(Z_n)-\sqrt{n\pi/2})\to0 as n→∞n\to\infty.

Proof. To verify that the mean is of order nπ/2\sqrt{n\pi}/2 one readily shows that

2(E(Zn))2n=(2⋅4⋅6⋯(2n−2))2⋅2n(1⋅3⋅5⋯(2n−1))2\frac{2(\mathbb{E}(Z_n))^2}{n}=\frac{(2\cdot4\cdot6\cdots(2n-2))^2\cdot2n}{(1\cdot3\cdot5\cdots(2n-1))^2}

This is the product of Wallis which approaches π/2\pi/2, from which we infer that E(Zn)∼nπ/2\mathbb{E}(Z_n)\sim\sqrt{n\pi}/2. In the course of the proof of the Wallis limit it is established that

(2⋅4⋅6⋯2n)2(1⋅3⋅5⋯(2n−1))2(2n+1)≤π2≤(2⋅4⋅6⋯2n)2(1⋅3⋅5⋯(2n−1))22n\frac{(2\cdot4\cdot6\cdots2n)^2}{(1\cdot3\cdot5\cdots(2n-1))^2(2n+1)}\leq\frac{\pi}{2}\leq\frac{(2\cdot4\cdot6\cdots2n)^2}{(1\cdot3\cdot5\cdots(2n-1))^2 2n}

from which we obtain that

4E2(Zn)2n+1≤π2≤4E2(Zn)2n.\frac{4\mathbb{E}^2(Z_n)}{2n+1}\leq\frac{\pi}{2}\leq\frac{4\mathbb{E}^2(Z_n)}{2n}.

This yields

0≤4E2(Zn)−nπ≤4E2(Zn)/(2n+1).0\leq4\mathbb{E}^2(Z_n)-n\pi\leq4\mathbb{E}^2(Z_n)/(2n+1).

We deduce from above that the ratio on the right approaches π/2\pi/2, and thus

4E2(Zn)−nπ=O(1),4\mathbb{E}^2(Z_n)-n\pi=O(1),

from which it follows that E(Zn)−nπ/2→0\mathbb{E}(Z_n)-\sqrt{n\pi}/2\to0. □

Remarks. The closest analogue of this result for TnT_n concerns the random variable Xn(α)X_n(\alpha) (α∈Tn\alpha\in T_n), the value of which is the order of the stable range of α\alpha (which corresponds to the number of cycle points of the digraph of α\alpha). It is shown in [9] that

(nπ/2−E(Xn))→13.(\sqrt{n\pi}/2-\mathbb{E}(X_n))\to\frac{1}{3}.

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 ene^n. By contrast, the component number of α∈Tn\alpha\in T_n has a mean that only increases logarithmically with nn. It is shown in [9] that if Cn(α)C_n(\alpha) denotes the number of components of a randomly selected α∈Tn\alpha\in T_n then

E(Cn)−12log⁡n→12(γ+log⁡2)\mathbb{E}(C_n)-\frac{1}{2}\log n\to\frac{1}{2}(\gamma+\log2)

where γ\gamma 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 Yn(α)Y_n(\alpha) (the rank of a random α∈On\alpha\in O_n) satisfies

(E(Yn)−n/2)↓14.(\mathbb{E}(Y_n)-n/2)\downarrow\frac{1}{4}.

The corresponding result for Rn(α)R_n(\alpha), the rank of a random α∈Tn\alpha\in T_n, is noted in [9]:

E(Rn)−n(1−e−1)→e−1/2.\mathbb{E}(R_n)-n(1-e^{-1})\to e^{-1}/2.

Katz [12] considered the problem of finding the probability of ‘indecomposability’ of a randomly selected α∈Tn\alpha\in T_n, by which was meant the probability that α\alpha has only one component. He proved that this probability is of order π/2n\sqrt{\pi/2n}. We shall now solve the corresponding problem for OnO_n. The ‘ballot’ argument involved also furnishes us with the value of ∣Cn∣|C_n|.

Recall from the first section the natural one-to-one correspondence between α∈On\alpha\in O_n and a ballot in which candidate AA polls nn votes while candidate BB polls n−1n-1 votes. Observe that i∈Xni\in X_n is a fixed point of α∈On\alpha\in O_n if and only if in the count of the corresponding ballot the iith AA appears between the (i−1)(i-1)th and the iith BB. In terms of the count, this corresponds to a tie after 2i−22i-2 votes, with AA polling the next vote. Now to say that α∈On\alpha\in O_n is indecomposable means exactly that α\alpha has a unique fixed point, which, formulated in terms of the corresponding ballot count, means precisely that AA never surrenders the lead once he has taken it (i.e. once AA is strictly ahead in the count, he stays strictly ahead).

We consider a more general ballot in which AA polls n+rn+r votes while his opponent BB polls nn votes (r≥1r \ge1), and we seek the probability that AA never relinquishes the lead once he has gained it. Let Y1Y_1 denote the set of ballots of this type, let Y2Y_2 denote the set of ballots in which AA never trails at any point in the count, and let Y=Y1∪Y2Y=Y_1\cup Y_2. Consider α∈Y\alpha\in Y, and let (p,0)(p,0) be the final point on the lattice path of α\alpha where the count is tied. Let α′\alpha' be the count of the lattice path which results from reflection of that portion of the path of α\alpha from (0,0)(0,0) to (p,0)(p,0) in the xx-axis. Then α′∈Y\alpha'\in Y and we observe that the mapping α′ ⁣:Y→Y\alpha'\colon Y\to Y defines a bijection between Y1Y_1 and Y2Y_2 with (α′)′=α(\alpha')'=\alpha. In fact, α′\alpha' defines a bijection between Y1∖Y2Y_1\setminus Y_2 and Y2∖Y1Y_2\setminus Y_1 as Y1∩Y2Y_1\cap Y_2 consists precisely of all those counts where AA leads throughout, which coincides with the set of fixed points of the mapping α′\alpha'.

We next find ∣Y2∣|Y_2| (=∣Y1∣=|Y_1|) by calculating the order of the complementary set of counts, which consists of all those counts during which AA trails BB at some point. The number of paths that correspond to counts where AA falls behind at some point equals the number of lattice paths from (0,0)(0,0) to (2n+r,r)(2n+r,r) which touch or cross the line y=−1y=-1. By the Reflection Principle (Result 1.3) this equals the number of lattice paths from (−2,0)(-2,0) to (2n+r,r)(2n+r,r), which is C(2n+r,n−1)C(2n+r,n-1); the n−1n-1 corresponds to the n−1n-1 places where the path dips, leaving n+r+1n+r+1 rises. Hence the probability that AA trails BB at some time during the count is C(2n+r,n−1)/C(2n+r,n)=n/(n+r+1)C(2n+r,n-1)/C(2n+r,n)=n/(n+r+1). Hence the probability of the complementary event that AA never trails is 1−n/(n+r+1)=(r+1)/(n+r+1)1-n/(n+r+1)=(r+1)/(n+r+1), and this equals the probability that AA never loses his lead once he has gained it. By taking r=1r=1 and replacing nn by n−1n-1 we obtain our required result.

Theorem 2.12. The probability that α∈On\alpha\in O_n is indecomposable is 2/(n+1)2/(n+1).

The semigroup of all decreasing and order-preserving mappings

We saw in the preceding section that a mapping α∈On\alpha\in O_n is indecomposable if and only if in the corresponding ballot count the winning candidate AA never relinquishes his lead once he has gained it, and that this collection of counts is in bijection with the set of counts where AA never trails his opponent. We now ask what type of mapping this latter set of counts represents. Candidate AA never trails in the count if and only if the iith vote for AA appears before the iith vote for BB for i=1,2,…,ni=1,2,\ldots,n; in other words, the number of votes for AA preceding the iith for BB in the sequence is always greater than or equal to ii. In the corresponding mapping, since each i∈Xni\in X_n is mapped to the number of the next BB following the iith AA in the sequence, this condition is equivalent to iα≤ii\alpha\le i for all i∈Xni\in X_n. Therefore the collection of mappings corresponding to the set of counts in which the winning candidate never trails is CnC_n, the semigroup of order-preserving and decreasing mappings, and ∣Cn∣|C_n| equals the cardinality of the set of all indecomposable mappings in OnO_n. This yields our next result.

Theorem 3.1. ∣Cn∣=Cn|C_n|=C_n, the nnth Catalan number.

Proof. From the preceding argument, together with Theorem 2.12 and Result 1.2, we have

∣Cn∣=∣{α∈On:α indecomposable}∣=2n+1(2n−1n−1)=1n+1(2nn),|C_n|=\left|\{\alpha\in O_n:\alpha\text{ indecomposable}\}\right|=\frac{2}{n+1}\binom{2n-1}{n-1}=\frac{1}{n+1}\binom{2n}{n},

which is the nnth Catalan number. □\square

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 AA never relinquishes his lead once he has gained it, the dual count has the property that AA never relinquishes his eventual winning lead once he has taken it. In our case, since the winning margin for AA is one, the characteristic conditions of both types of count are identical, so that the set of indecomposable mappings of On\mathcal{O}_n is self-dual under this correspondence. On the other hand, the dual of the condition that AA never trails in the count is that AA’s lead never exceeds his eventually winning margin, which in our case is tantamount to saying that AA’s lead never exceeds one. This is to say that the number of the next BB to follow the iith vote for AA in the count is at least ii, or in terms of the corresponding mapping α\alpha, iα≥ii\alpha\ge i for all i∈Xni \in X_n. Hence the dual to CnC_n under this correspondence is the isomorphic semigroup of all increasing and order-preserving mappings on XnX_n.

There are natural bijections between CnC_n and other standard collections of order CnC_n which thus yield alternative proofs of Theorem 3.1. We give the specific connection between CnC_n and the set of all binary trees on nn source nodes. In this context it is more natural to take the base set XnX_n to be {0,1,2,…,n−1}\{0,1,2,\ldots,n-1\}.

By a binary tree we shall mean a complete binary tree where every node uu is either a source node, meaning that there are exactly two arcs from uu leading to its two sons, or that uu 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 nn source nodes has 2n+12n+1 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.

A binary tree with seven source nodes

Figure 2. A binary tree with seven source nodes.

Given a binary tree BB on nn source nodes (and so with n+1n+1 leaf nodes) we associate a mapping α∈Cn\alpha\in C_n by the rule that i↦ti \mapsto t, where tt leaf nodes precede the iith source node in the ordering of the nodes of BB. To see that α∈Cn\alpha\in C_n observe that our rule certainly defines an order-preserving map on XnX_n, and since the final source node precedes its two sons in the ordering of the nodes, the maximum possible value of (n−1)α(n-1)\alpha is n+1−2=n−1n+1-2=n-1. We can then prove by induction on nn that α\alpha also has the decreasing property: remove the two sons of the final source node from BB to give a binary tree B′B' on n−1n-1 source nodes, which, by induction, we may assume is associated with a member of Cn−1C_{n-1} by the above rule. Indeed, the mapping α′\alpha' associated with B′B' is just the restriction of the mapping α\alpha to Xn−1X_{n-1}, and so, by the inductive hypothesis, we have that α∣Xn−1\alpha|_{X_{n-1}} is decreasing, and we have already observed that (n−1)α≤n−1(n-1)\alpha\le n-1, allowing us to conclude that α∈Cn\alpha\in C_n. The mapping α∈C7\alpha\in C_7 associated with our binary tree above has its ordered list of images of the members of X7X_7 the tuple (0,0,1,1,3,3,6)(0,0,1,1,3,3,6).

Conversely, we can associate with any α∈Cn\alpha\in C_n a binary tree BB on nn source nodes using the inverse of the foregoing procedure. Suppose inductively that we have associated with α′=α∣Xn−1\alpha'=\alpha|X_{n-1} a binary tree B′B' on n−1n-1 source nodes in such a way that B′B' is associated with α′\alpha' by the procedure of the preceding paragraph. Let kk denote (n−1)α(n-1)\alpha. The tree B′B' has nn leaf nodes. Take the (k+1)(k+1)th leaf node (with k+1≤nk+1\leq n), and replace it by a source node to form the binary tree BB. By construction, the mapping associated with BB is α\alpha, as required.

The number of indecomposable α∈Cn\alpha\in C_n is easily obtained through our ballot correspondence. In terms of the corresponding count,

  1. α∈Cn\alpha\in C_n if and only if AA never trails BB in the count,

  2. α\alpha is indecomposable if and only if AA never relinquishes the lead once gained.

The conjunction of this pair of conditions is equivalent to the single constraint that AA 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 r/(2n+r)r/(2n+r). Again, upon putting r=1r=1 and replacing nn by n−1n-1 we see that the proportion of such mappings in CnC_n is

12n−1(2n−1n−1)=Cn−1.\frac{1}{2n-1}\binom{2n-1}{n-1}=C_{n-1}.

This yields

Proposition 3.2. The proportion of indecomposable mappings in CnC_n is

Cn−1/Cn=(n+1)/(2(2n−1))↓14as n→∞.C_{n-1}/C_n=(n+1)/(2(2n-1))\downarrow\frac{1}{4}\quad\text{as }n\to\infty.

It is interesting here that the probability decreases to 14\frac{1}{4}, and not to 00, as is the case with OnO_n and TnT_n. This suggests the existence of a limiting distribution for Zn(α)Z_n(\alpha), where Zn(α)Z_n(\alpha) denotes the component number of a randomly chosen α∈Cn\alpha\in C_n. 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 CnC_n into nn disjoint sets K1,K2,…,KnK_1,K_2,\ldots,K_n, where α∈Kk\alpha\in K_k if kk is the greatest integer such that kα=kk\alpha=k. Note that α∈K1\alpha\in K_1 if and only if 11 is the unique fixed point of α\alpha, which is to say that α\alpha is indecomposable. Then

∣Cn∣=∑k=1n∣Kk∣.|C_n|=\sum_{k=1}^{n}|K_k|.

Now ∣Kk∣=∣Ck−1∣∣{α∈Cn−k+1:α indecomposable}∣=Ck−1Cn−k|K_k|=|C_{k-1}||\{\alpha\in C_{n-k+1}:\alpha\text{ indecomposable}\}|=C_{k-1}C_{n-k}, since, in general, the number of indecomposable mappings in CnC_n is Cn−1C_{n-1}. Hence

∣Cn∣=∑k=1nCk−1Cn−k.|C_n|=\sum_{k=1}^{n}C_{k-1}C_{n-k}.

We can use this result to show that the expected number of components of a random α∈Cn\alpha\in C_n is a monotonic function of nn increasing to a limit of 33. This contrasts with Theorem 2.11 which shows that the mean component number in OnO_n is of order n\sqrt{n}.

Proposition 3.3. E(Zn)=3n/(n+2)\mathbb{E}(Z_n)=3n/(n+2) where Zn(α)Z_n(\alpha) is the component number of a random α∈Cn\alpha\in C_n.

Proof. We have

E(Zn)=∑k=1nPr⁡(kα=k)=Cn−1∑k=1nCk−1Cn+1−k=Cn−1(∑k=1n+1Ck−1Cn+1−k−CnC0)=(Cn+1−Cn)/Cn=2(2n+1)n+2−1=3nn+2↑3.\begin{aligned} \mathbb{E}(Z_n)=\sum_{k=1}^{n}\Pr(k\alpha=k)=C_n^{-1}\sum_{k=1}^{n}C_{k-1}C_{n+1-k} \\ &=C_n^{-1}\left(\sum_{k=1}^{n+1}C_{k-1}C_{n+1-k}-C_nC_0\right)=(C_{n+1}-C_n)/C_n \\ &=\frac{2(2n+1)}{n+2}-1=\frac{3n}{n+2}\uparrow3. \end{aligned}

Let N(n,k)=∣{α∈Cn:α has exactly k fixed points}∣N(n,k)=|\{\alpha\in C_n:\alpha\text{ has exactly }k\text{ fixed points}\}|.

Lemma 3.4.

N(n,k)=k2n−k(2n−kn),for k=1,2,…,n.N(n,k)=\frac{k}{2n-k}\binom{2n-k}{n},\qquad\text{for }k=1,2,\ldots,n.

Proof. Using Proposition 3.2 we have

N(n,1)=∣{α∈Cn:α indecomposable}∣=Cn−1=(1/n)C(2n−2,n−1)=(1/(2n−1))C(2n−1,n),\begin{aligned} N(n,1)=|\{\alpha\in C_n:\alpha\text{ indecomposable}\}|=C_{n-1} \\ &=(1/n)C(2n-2,n-1)=(1/(2n-1))C(2n-1,n), \end{aligned}

as asserted. Using the argument of the proof of Result 1.4, we focus attention on the final fixed point of a mapping in CnC_n and conclude that

N(n,2)=∑k=1n−1N(k,1)N(n−k,1)=∑k=1n−1Ck−1Cn−k−1=∑k=1n−1Ck−1C(n−1)−k=Cn−1\begin{aligned} N(n,2)=\sum_{k=1}^{n-1}N(k,1)N(n-k,1)=\sum_{k=1}^{n-1}C_{k-1}C_{n-k-1} \\ &=\sum_{k=1}^{n-1}C_{k-1}C_{(n-1)-k}=C_{n-1} \end{aligned}

by Result 1.4, and Cn−1=(2/(2n−2))C(2n−2,n)C_{n-1}=(2/(2n-2))C(2n-2,n), as required.

We next establish the recurrence

N(n,k+1)=N(n,k)−N(n−1,k−1)for k=1,2,…,n−1.(9)N(n,k+1)=N(n,k)-N(n-1,k-1)\qquad\text{for }k=1,2,\ldots,n-1. \tag*{(9)}

The above calculation shows that (9) is valid for k=1k=1 (as N(n,0)=0N(n,0)=0). Take k≥2k\ge2. By considering the final fixed point tt of α∈Cn\alpha\in C_n with exactly k+1k+1 fixed points we see that

N(n,k+1)=∑t=k+1nN(t−1,k)N(n−t+1,1).(10)N(n,k+1)=\sum_{t=k+1}^{n}N(t-1,k)N(n-t+1,1). \tag*{(10)}

By considering the penultimate fixed point tt we also have

N(n,k+1)=∑t=kn−1N(t−1,k−1)N(n−t+1,2).(11)N(n,k+1)=\sum_{t=k}^{n-1}N(t-1,k-1)N(n-t+1,2). \tag*{(11)}

But we know that N(n−t+1,2)=N(n−t+1,1)N(n-t+1,2)=N(n-t+1,1), and so, by substituting accordingly in (11), we obtain

N(n,k+1)=∑t=knN(t−1,k−1)N(n−t+1,1)−N(n−1,k−1)N(1,1).N(n,k+1)=\sum_{t=k}^{n}N(t-1,k-1)N(n-t+1,1)-N(n-1,k-1)N(1,1).

Therefore N(n,k+1)=N(n,k)−N(n−1,k−1)N(n,k+1)=N(n,k)-N(n-1,k-1), as asserted.

It is now a routine matter, using a double induction on nn and kk, to verify that the solution to our recurrence is given by

N(n,k)=k2n−kC(2n−k,n)N(n,k)=\frac{k}{2n-k}C(2n-k,n)

for k=1,2,…,nk=1,2,\ldots,n.

Theorem 3.8. The probability distribution for the random variable Zn(α)Z_n(\alpha), the component number of a random α∈Cn\alpha\in C_n, is given by

Pr⁡(Zn=k)=p(n,k)=k(n+1)(n−1)(n−2)⋯(n−k+1)2(2n−1)(2n−2)⋯(2n−k)(12)\Pr(Z_n=k)=p(n,k)=\frac{k(n+1)(n-1)(n-2)\cdots(n-k+1)}{2(2n-1)(2n-2)\cdots(2n-k)} \tag*{(12)}

for k=1,2,…,nk=1,2,\ldots,n.

As nn increases, ZnZ_n approaches in distribution and in moments the random variable ZZ, where pk=Pr⁡(Z=k)=k/2k+1p_k=\Pr(Z=k)=k/2^{k+1} for k=1,2,…k=1,2,\ldots. In particular, the limiting values of the mean and variance are 3 and 2 respectively. Furthermore, for n>1n>1, the probability sequence is bi-modal, with modes k=1k=1 and k=2k=2, and is strictly monotonically decreasing for k>2k>2, features shared with the limiting distribution ZZ.

Proof. Except for the statement about moments, this is now immediate: from Theorem 3.1 and Lemma 3.4 we obtain

p(n,k)=N(n,k)Cn=k2n−kC(2n−k,n)/(1n+1C(2n,n)),p(n,k)=\frac{N(n,k)}{C_n}=\frac{k}{2n-k}C(2n-k,n)\mathbin{/}\left(\frac{1}{n+1}C(2n,n)\right),

which simplifies to yield the expression (3.9). That lim⁡n→∞p(n,k)=k/2k+1\lim_{n\to\infty}p(n,k)=k/2^{k+1} follows on dividing each of the last kk terms in the numerator and denominator by nn, so that ZnZ_n approaches ZZ in distribution. From (3.9) we deduce the recurrence

p(n,k+1)=p(n,k)⋅(k+1)(n−k)k(2n−k−1)(13)p(n,k+1)=p(n,k)\cdot\frac{(k+1)(n-k)}{k(2n-k-1)} \tag*{(13)}

for k=1,2,…,n−1k=1,2,\ldots,n-1 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 n>2n>2 then p(n,k)>pkp(n,k)>p_k for k=1,2,3k=1,2,3 and p(n,k)<pkp(n,k)<p_k for k≥4k\geq4.

Proof. Direct calculation using (3.9) allows one to verify the assertions of the Lemma for k=1,2,3k=1,2,3 and 4. It remains only to observe that if p(n,k)<pkp(n,k)<p_k for some kk, then (3.10) yields

p(n,k+1)<pk+12(n−k)2n−k−1,p(n,k+1)<p_{k+1}\frac{2(n-k)}{2n-k-1},

from which we infer that p(n,k+1)<pk+1p(n,k+1)<p_{k+1}. The result now follows by induction on kk.

To show convergence in moments, first observe that E(Zt)\mathbb{E}(Z^t) certainly exists for t=1,2,…t=1,2,\ldots (indeed the values of E(Zt)\mathbb{E}(Z^t) are integers, and can be calculated recursively). Let tt be a positive integer, and let ϵ>0\epsilon>0 be given. Choose N≥3N\geq3 such that

∑k=N+1∞ktpk<ϵ/3.\sum_{k=N+1}^{\infty} k^t p_k<\epsilon/3.

Then, for any positive integer $n,

∣E(Zt)−E(Znt)∣≤∣∑k=1Nkt(pk−p(n,k))∣+∑k=N+1∞kt(pk−p(n,k))≤∣∑k=1Nkt(pk−p(n,k))∣+∑k=N+1∞ktpk+∑k=N+1∞ktp(n,k).\begin{aligned} \left|\mathbb{E}(Z^t)-\mathbb{E}(Z_n^t)\right| \leq \left|\sum_{k=1}^{N} k^t\bigl(p_k-p(n,k)\bigr)\right| + \sum_{k=N+1}^{\infty} k^t\bigl(p_k-p(n,k)\bigr) \\ &\leq \left|\sum_{k=1}^{N} k^t\bigl(p_k-p(n,k)\bigr)\right| + \sum_{k=N+1}^{\infty} k^t p_k + \sum_{k=N+1}^{\infty} k^t p(n,k). \end{aligned}

Since ZnZ_n approaches ZZ in distribution, it follows that for sufficiently large nn the first term is less than ϵ/3\epsilon/3; the same is true of the second term, and of the third which is bounded by the second. Hence, for all nn sufficiently large, ∣E(Zt)−E(Znt)∣<ϵ\lvert\mathbb{E}(Z^t)-\mathbb{E}(Z_n^t)\rvert<\epsilon, and so ZnZ_n approaches ZZ in moments also. □

Remark. Using the fact that p(n,k)<pkp(n,k)<p_k for all kk sufficiently large, it can be shown that E(Znt)<E(Zt)\mathbb{E}(Z_n^t)<\mathbb{E}(Z^t) for all positive integers nn and tt.

The probability distribution for the component number of a random α∈On\alpha\in\mathcal{O}_n can be calculated explicitly in a similar fashion. Let us now write Zn(α)Z_n(\alpha) for the component number of a randomly chosen α∈On\alpha\in\mathcal{O}_n, and let N(n,k)N(n,k) be the cardinality of {α∈On:α has exactly k components}\{\alpha\in\mathcal{O}_n:\alpha\text{ has exactly }k\text{ components}\}.

Theorem 3.12. Let p(n,k)=Pr⁡(Zn=k)p(n,k)=\operatorname{Pr}(Z_n=k), where ZnZ_n is the component number of a random α∈On\alpha\in\mathcal{O}_n. Then

p(n,k)=2k(n−1)(n−2)⋯(n−k+1)(n+1)(n+2)⋯(n+k)for k=1,2,…,n.(14)p(n,k)=\frac{2k(n-1)(n-2)\cdots(n-k+1)}{(n+1)(n+2)\cdots(n+k)}\qquad\text{for }k=1,2,\ldots,n. \tag*{(14)}

The distribution of ZnZ_n has a unique mode at ⌊12(1+2n−1)⌋\left\lfloor\frac{1}{2}\left(\sqrt{1+2n}-1\right)\right\rfloor, the greatest integer not exceeding 12(1+2n−1)\frac{1}{2}\left(\sqrt{1+2n}-1\right), unless 1+2n1+2n is a perfect square, in which case ⌊12(1+2n+1)⌋\left\lfloor\frac{1}{2}\left(\sqrt{1+2n}+1\right)\right\rfloor is another mode. The distribution decreases monotonically on either side of the mode(s) with the minimum occurring at k=nk=n. Furthermore, p(n,k)∼2k/np(n,k)\sim2k/n as n→∞n\to\infty.

Proof. Assertion (3.13) for k=1k=1 is Theorem 2.12; in this case N(n,1)=CnN(n,1)=C_n. In order to establish (3.13) for k>1k>1 it is enough, by Result 1.2, to verify that

N(n,k)=k(2n)!(n−1)(n−2)⋯(n−k+1)n!(n+k)!for k=1,2,…,n.(15)N(n,k)=\frac{k(2n)!(n-1)(n-2)\cdots(n-k+1)}{n!(n+k)!}\qquad\text{for }k=1,2,\ldots,n. \tag*{(15)}

We do this by proving the analogue of Lemma 3.4.

Lemma 3.15. N(n,k+1)=N(n+1,k)−2N(n,k)−N(n,k−1)N(n,k+1)=N(n+1,k)-2N(n,k)-N(n,k-1) for k=1,2,…,n−1k=1,2,\ldots,n-1.

Proof. Let α\alpha be a typical member of On\mathcal{O}_n with exactly two components, and thus two fixed points, p<qp<q, say. Bearing in mind the convexity of the orbits of α\alpha (Proposition 1.5), and letting tt be the maximum of the orbit of pp, we see that

N(n,2)=∑t=1n−1N(t,1)N(n−t,1)=∑t=1n−1CtCn−t=∑t=2nCt−1Cn+1−t.N(n,2)=\sum_{t=1}^{n-1}N(t,1)N(n-t,1)=\sum_{t=1}^{n-1}C_tC_{n-t}=\sum_{t=2}^{n}C_{t-1}C_{n+1-t}.

Applying Result 1.4 then yields that

N(n,2)=Cn+1−C0Cn−CnC0=Cn+1−2Cn.N(n,2)=C_{n+1}-C_0C_n-C_nC_0=C_{n+1}-2C_n.

In other words, N(n,2)=N(n+1,1)−2N(n,1)N(n,2)=N(n+1,1)-2N(n,1), in agreement with the statement of our lemma.

Next, for k≥2k\geq2, by considering the final, and then the penultimate fixed point of a mapping from On\mathcal{O}_n with exactly k+1k+1 fixed points, we obtain the expressions

N(n,k+1)=∑t=kn−1N(t,k)N(n−t,1),(16)N(n,k+1)=\sum_{t=k}^{n-1}N(t,k)N(n-t,1), \tag*{(16)}
N(n,k+1)=∑t=k−1n−2N(t,k−1)N(n−t,2).(17)N(n,k+1)=\sum_{t=k-1}^{n-2}N(t,k-1)N(n-t,2). \tag*{(17)}

Replacing N(n−t,2)N(n-t,2) by N(n−t+1,1)−2N(n−t,1)N(n-t+1,1)-2N(n-t,1) in (17) yields that

N(n,k+1)=∑t=k−1n−2N(t,k−1)N(n−t+1,1)−2∑t=k−1n−2N(t,k−1)N(n−t,1).N(n,k+1)=\sum_{t=k-1}^{n-2}N(t,k-1)N(n-t+1,1)-2\sum_{t=k-1}^{n-2}N(t,k-1)N(n-t,1).

From (16) we see that the first term can be written as

N(n+1,k)−N(n−1,k−1)N(2,1)−N(n,k−1)N(1,1);N(n+1,k)-N(n-1,k-1)N(2,1)-N(n,k-1)N(1,1);

while the summation in the second term equals

N(n,k)−N(n−1,k−1)N(1,1).N(n,k)-N(n-1,k-1)N(1,1).

Combining these expressions yields

N(n,k+1)=N(n+1,k)−2N(n,k)−N(n,k−1)N(n,k+1)=N(n+1,k)-2N(n,k)-N(n,k-1)

as required. □

A routine calculation now shows that the expression for N(n,k)N(n,k) given in (15) is correct, and thus (14) is also.

From (14) comes the recurrence relation

p(n,k+1)=p(n,k)k+1kn−kn+k+1.(18)p(n,k+1)=p(n,k)\frac{k+1}{k}\frac{n-k}{n+k+1}. \tag*{(18)}

From (18) it follows that

p(n,k+1)>p(n,k)if and only ifk<12(1+2n−1)(19)p(n,k+1)>p(n,k)\quad\text{if and only if}\quad k<\frac{1}{2}\left(\sqrt{1+2n}-1\right) \tag*{(19)}

with equality occurring in both sides simultaneously. Using [x][x] to denote the greatest integer not exceeding a real number xx, we see that if 12(1+2n−1)\frac{1}{2}(\sqrt{1+2n}-1) is not an integer then ZnZ_n has a unique mode at [12(1+2n−1)]\left[\frac{1}{2}(\sqrt{1+2n}-1)\right], while otherwise ZnZ_n is bi-modal with modes [12(1+2n±1)]\left[\frac{1}{2}(\sqrt{1+2n}\pm1)\right]. That the distribution of ZnZ_n falls away monotonically on either side of the mode(s) follows from (19), and that the minimum value of p(n,k)p(n,k) occurs at k=nk=n follows by comparing p(n,1)=2/(n+1)p(n,1)=2/(n+1) with p(n,n)=1/(2n−1n−1)p(n,n)=1/\binom{2n-1}{n-1}. Finally, from (14),

p(n,k)=2kn⋅n(n−1)⋯(n−k+1)(n+1)(n+2)⋯(n+k)p(n,k)=\frac{2k}{n}\cdot\frac{n(n-1)\cdots(n-k+1)}{(n+1)(n+2)\cdots(n+k)}

and since the bracketed term approaches 11 for large nn, it follows that p(n,k)∼2k/np(n,k)\sim2k/n as n→∞n\to\infty. □

In [11], the cardinality of E(On)E(O_n), the set of idempotents of OnO_n, was shown to be F2nF_{2n}, the 2n2nth Fibonacci number. This was achieved by solving a certain recurrence relation. Determining the order of E(Cn)E(C_n) is, however, a simple matter, for any α∈E(Cn)\alpha\in E(C_n) is determined by im⁡α\operatorname{im}\alpha, the image of α\alpha. To see this, first recall that α∈Tn\alpha\in T_n is an idempotent if and only if im⁡α\operatorname{im}\alpha and the set of fixed points of α\alpha coincide. If we further suppose that α∈E(Cn)\alpha\in E(C_n) then, for any i∈Xni\in X_n, iα≤ii\alpha\le i, iαi\alpha is a fixed point of α\alpha, and since α\alpha preserves order, iαi\alpha must be the greatest fixed point less than or equal to ii. Hence an idempotent of CnC_n is determined by its image and thus ∣E(Cn)∣=∣{im⁡α:α∈Cn}∣|E(C_n)|=|\{\operatorname{im}\alpha:\alpha\in C_n\}|. Now the subsets of XnX_n which occur as images of mappings α∈Cn\alpha\in C_n are exactly the subsets of XnX_n that contain 11. This yields the first statement in our final result.

Theorem 3.19. ∣E(Cn)∣=2n−1|E(C_n)|=2^{n-1}. Furthermore, R=∣E(Cn)∣/∣Cn∣∼πn(n+1)/2n+1R=|E(C_n)|/|C_n|\sim\sqrt{\pi n}(n+1)/2^{n+1}.

Proof. We have R=2n−1/CnR = 2^{n-1}/C_n, from which one obtains 4n+1R2/(2n(n+1)2)=Wn4^{n+1}R^2/(2n(n+1)^2) = W_n, where WnW_n is the Wallis product as in the proof of Theorem 2.11. Hence we deduce that 2n+1R/(nπ(n+1))→12^{n+1}R/(\sqrt{n\pi}(n+1)) \to1 as n→∞n \to\infty, as required. □

Remark. For an investigation of the number of idempotents of finite full transformation semigroups see [4] and [5].

References

  1. [1]W. Feller. An Introduction to Probability Theory and its Applications, 3rd edn. vol. 1 (Wiley, 1968).
  2. [2]G. U. Garba. Nilpotents in semigroups of partial one-to-one order-preserving mappings. Semigroup Forum 41 (1991), 1–15.
  3. [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. [4]B. Harris. A note on the number of idempotents in symmetric semigroups. J. Combin. Theory Ser. A 3 (1967), 1234–1235.DOI
  5. [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. [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. [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. [8]P. M. Higgins. Techniques of Semigroup Theory (Oxford University Press, 1992).DOI
  9. [9]P. M. Higgins and E. J. Williams. Random functions on a finite set. Ars Combin. 26A (1988), 93–102.
  10. [10]P. Hilton and J. Pedersen. Catalan numbers, their generalization, and their uses. Math. Intelligencer 13 (1991), 64–75.DOI
  11. [11]J. M. Howie. Products of idempotents in certain semigroups of transformations. Proc. Roy. Soc. Edinburgh Sect. A 17 (1971), 223–236.DOI
  12. [12]L. Katz. Probability of indecomposability of a random mapping function. Ann. Math. Statist. 26 (1955), 512–517.DOI
  13. [13]M. D. Kruskal. The expected number of components under a random mapping function. Amer. Math. Monthly 61 (1954), 392–397.DOI
  14. [14]J. E. Pin. Varieties of Formal Languages (Plenum Press, 1986).DOI

Paper details

vlnc:W_hpqudyh7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents