压缩变换半群的一些组合性质

On Combinatorial Property of Compressive Transformation Semigroup

设Tn是有限集Xn={1,2,…,n}上的变换半群。任取α∈Tn,若对任意的x、y∈Xn,有|xα-yα|≤|x-y|,则称α是Tn的压缩元。令CTn={α|α是Tn的压缩元},容易验证CTn是Tn的子半群,称该半群为压缩变换半群。主要研究了CTn的组合性质,证明了|CTn|=n·3n-1-2∑n-1j=1LN1j.3n-1-j;LN1n=3LN1n-1-LNn-1(1,1),n≥3;LN(1,1)n=2LN(1,1)n-1+LN(1,321)n,n≥5。

Let be transformation semigroup on finite set Xn={1,2,…,n}.For all α∈Tn,we shall call α is compressive element of Tn if｜xα-yα｜≤｜x-y｜ for all x,y in Xn.Let CTn be a set that consists of the compressive element of Tn.Then CTn is a subsemigroup of Tn,we call CTn as compressive semigroup.It is shown that ｜CTn｜=n·3n-1-2∑n-1j=1LN1j·3n-1-j;LN1n=3LN1n-1-LNn-1（1,1）,n≥3;LN（1,1）n=2LN（1,1）n-1＋LN（1,321）n,n≥5.