A Combinatorial Result for Certain Semigroups of Transformations Preserving an Equivalence Relation

Lei SUN

doi:10.13718/j.cnki.xdzk.2018.08.011

Let \lt inline-formula \gt $\mathscr{T}_X $ \lt /inline-formula \gt be a full transformation semigroup on the nonempty set \lt i \gt X \lt /i \gt , and \lt i \gt E \lt /i \gt be an ( \lt i \gt n \lt /i \gt , \lt i \gt m \lt /i \gt )-type equivalence relation on \lt i \gt X \lt /i \gt . Then $ {\mathscr T_E}\left( X \right) = \left\{ {f \in {\mathscr{T}_X }:\forall x, y \in X, \left( {x, y} \right) \in E \Rightarrow \left( {f\left( x \right), f\left( y \right)} \right) \in E} \right\} $ is a subsemigroup of \lt i \gt T \lt /i \gt \lt sub \gt \lt i \gt X \lt /i \gt \lt /sub \gt . In this paper, we calculate the cardinality of the semigroup \lt i \gt T \lt /i \gt \lt sub \gt \lt i \gt E \lt /i \gt \lt /sub \gt ( \lt i \gt X \lt /i \gt ) and present a formula for the number of its regular elements under the supposition that \lt i \gt n \lt /i \gt =2, \lt i \gt m \lt /i \gt ≥ 2 and \lt i \gt n \lt /i \gt =3, \lt i \gt m \lt /i \gt ≥ 2.

HTML

组合结果的研究是变换半群理论中一个有趣的课题，对于变换半群结构的研究有着重要意义.关于各类变换半群组合数的研究，参看文献[1-8].

设$ \mathscr{T}_X $是非空集合X(|X|≥3)上全变换半群，E是X上的等价关系，X/E是由等价关系E确定的X的分类(其中X/E的每个元素称为一个E-类).文献[9]最早引入了$ \mathscr{T}_X $的子半群

这类半群称为保持等价关系E的变换半群.它是一类重要的变换半群.这是因为当E=X×X或E={(x，x)：x∈X}时，T_E(X)=$ \mathscr{T}_X $.对于这类变换半群，文献[9-13]研究了它的α-同余、正则元、格林等价关系、生成集、秩、自然偏序关系和富足性等.特别地，得到了如下结论：

定理1^[10]   设f∈T_E(X)，则f是T_E(X)的正则元当且仅当对于任意E-类A，存在E-类B，使得A∩f(X)=f(B).

由文献[10]的命题2.4知，当E≠X×X且E≠{(x，x)：x∈X}时，半群T_E(X)是非正则半群.怎么计算半群T_E(X)中正则元的个数?一般情形较为复杂，本文先考虑一种特殊情形：在X={1，2，…，nm}(其中n表示每个E-类中元素的个数，m表示E-类的个数，并且n≥2，m≥2)和特殊的等价关系(2，m)-型和(3，m)-型，即

其中A₁={1，2}，A₂={3，4}，…，A_m={2m-1，2m}，和

其中A₁={1，2，3}，A₂={4，5，6}，…，A_m={3m-2，3m-1，3m}的假设下，给出了T_E(X)的正则元个数的计算公式.

现在给出半群T_E(X)的一个最基本的性质：对于任意f∈T_E(X)和A∈X/E，有f(A)⊆B∈X/E.用R(T_E(X))和(R(T_E(X)))⁺分别表示T_E(X)的正则元和非正则元的集合.

定理2   设E是集合X上的(n，m)-型等价关系，其中n≥2，m≥2，则

证   设f∈T_E(X).分两步进行：

步骤1   像f(A₁)所在E-类的可能性有m个.并且对于A₁中每个元素x，像f(x)的可能性有n个.于是像f(A₁)所有选法为mnⁿ个.

步骤2   取遍所有m个E-类{A₁，A₂，…，A_m}，则|T_E(X)|=(mnⁿ)^m.

下面借助定理1，通过构造T_E(X)的非正则元，计算T_E(X)的正则元的个数.显然，若对于任意E-类A，有|A∩f(X)|=1，则f是T_E(X)的正则元.

引理1   设E是集合X上的(2，m)-型等价关系，其中m≥2，则

证   分两种情形构造T_E(X)的非正则元f，即存在一个E-类A，使对于任意E-类B，有

情形1   m=2.从2个E-类中选取1个E-类的方法有2个.这个E-类不妨设为A={a₁，a₂}.满足|f(A₁)|=|f(A₂)|=1且f(X)={a₁，a₂}的变换有2个.于是A∩f(X)={a₁，a₂}.但是对于E-类A₁，A₂，有：

因此对于情形1有2×2=4个非正则元.

情形2   m≥3.分下述步骤进行.

步骤1   从m个E-类中选取1个E-类的方法有m个.这个E-类不妨设为A={a₁，a₂}.

步骤2   下面有两种可能：

(P1) 所有E-类被变换f作用到A中.满足|f(A₁)|=|f(A₂)|=…=|f(A_m)|=1且f(X)={a₁，a₂}的变换有2^m-2个.

(P2) i(i≥2)个E-类被变换f作用到A中，其它m-i个E-类被变换f作用到X/E-{A}中.满足这种可能的选法有C_mⁱ种.不妨设这i个E-类为A₁，A₂，…，A_i.下面考虑满足：

的变换f的个数.一方面，满足|f(A₁)|=|f(A₂)|…=|f(A_i)|=1且f(A₁∪A₂∪…∪A_i)={a₁，a₂}的选法有(2ⁱ-2)个；另一方面，满足f(A_i+1∪A_i+2∪…∪A_m)⊆X-A的选法有(4(m-1))^m-i个.因此对于这种可能共有$ \sum\limits_{i = 2}^{m - 1} {C_{_m}^{^i}} ({2^i} - 2){(4(m - 1))^{m - i}} $个变换.

满足上述两种可能(P1)和(P2)的变换f有

个.进而在情形2下构造的变换f有$ m\left[ {\sum\limits_{i = 2}^m {C_{_m}^{^i}} ({2^i} - 2){{(4(m - 1))}^{m - i}}} \right]$个.

由此可知A∩f(X)={a₁，a₂}.但是对于任意E-类B∈{A₁，A₂，…，A_m}，有

由定理1知f是T_E(X)的非正则元.

综合情形1和情形2，有

即

根据定理2和引理1，得到本文的主要结论：

定理3   设E是集合X上的(2，m)-型等价关系(其中m≥2)，则

引理2   设E是集合X上的(3，2)-型等价关系，则

证   分两种情形构造T_E(X)的非正则元f，即存在一个E-类A，使得对于任意E-类B，有

情形1   |A∩f(X)|=2.

步骤1   从2个E-类中选取1个E-类的方法有2个，这个E-类不妨设为A.

步骤2   从A中选取2个元素的方法有C₃²=3个，不妨设这2个元素为a₁，a₂.

步骤3   满足|f(A₁)|=|f(A₂)|=1且f(A₁∪A₂)={a₁，a₂}的变换有2个.

由此可知

但是

由定理1知f是T_E(X)的非正则元.因此在情形1下T_E(X)的非正则元的个数为2×3×2=12个.

情形2   |A∩f(X)|=3.

步骤1   从2个E-类中选取1个E-类的方法有2个.这个E-类不妨设为A={a₁，a₂，a₃}.

步骤2   下面有两种可能：

(P1) 满足f(A₁)={a₁}，f(A₂)={a₂，a₃}，或f(A₁)={a₂，a₃}，f(A₂)={a₁}，或f(A₁)={a₂}，f(A₂)={a₁，a₃}，或f(A₁)={a₁，a₃}，f(A₂)={a₂}，或f(A₁)={a₃}，f(A₂)={a₁，a₂}，或f(A₁)={a₁，a₂}，f(A₂)={a₃}的变换有6(2³-2)=36个.

(P2) 满足f(A₁)={a₁，a₂}，f(A₂)={a₁，a₃}，或f(A₁)={a₁，a₃}，f(A₂)={a₁，a₂}，或f(A₁)={a₁，a₂}，f(A₂)={a₂，a₃}，或f(A₁)={a₂，a₃}，f(A₂)={a₁，a₂}，或f(A₁)={a₁，a₃}，f(A₂)={a₂，a₃}，或f(A₁)={a₂，a₃}，f(A₂)={a₁，a₃}的变换有6(2³-2)(2³-2)=216个.

满足上述两种可能(P1)和(P2)的变换有36+216=252个.于是情形2构造的变换f有2×252=504个.

由此可知

但是

从而由定理1知f是T_E(X)的非正则元.

综合情形1和情形2，共有12+504=516个非正则元.

引理3   设E是集合X上的(3，m)-型等价关系(其中m≥3)，则

证   分两种情形构造T_E(X)的非正则元f，即存在一个E-类A，使得对于任意E-类B，有

情形1   |A∩f(X)|=2.

步骤1   从m个E-类中选取1个E-类的方法有m个，这个E-类不妨设为A.

步骤2   从A中选取2个元素的方法有C₃²=3个，不妨设这2个元素为a₁，a₂.

步骤3   下面有两种可能；

(P1) 所有E-类被变换f作用到A中.满足|f(A₁)|=|f(A₂)|=…=|f(A_m)|=1且f(X)={a₁，a₂}的变换有2^m-2个.

(P2) i(i≥2)个E-类被变换f作用到A中，其它m-i个E-类被变换f作用到X/E-{A}中.满足这种可能的选法有C_mⁱ种.不妨设这i个E-类为A₁，A₂，…，A_i.下面考虑满足

的变换f的个数.一方面，满足|f(A₁)|=|f(A₂)|…=|f(A_i)|=1且f(A₁∪A₂∪…∪A_i)={a₁，a₂}的选法有(2ⁱ-2)个；另一方面，满足f(A_i+1∪A_i+2∪…∪A_m)⊆X/E-{A}的选法有(27(m-1))^m-i个.结合这两方面有(2ⁱ-2)(27(m-1))^m-i个变换.因此对于这种可能共有$\sum\limits_{i = 2}^{m - 1} {C_{_m}^{^i}} ({2^i} - 2){(27(m - 1))^{m - i}} $个变换.

满足上述两种可能(P1)和(P2)的变换f有

个.因此对于情形1共有$ 3m\sum\limits_{i = 2}^m {C_{_m}^{^i}} ({2^i} - 2){(27(m - 1))^{m - i}} $个变换.

由此可知

但是对于任意E-类B∈{A₁，A₂，…，A_m}，有A∩f(X)≠f(B).由定理1知f是T_E(X)的非正则元.

情形2   |A∩f(X)|=3.

步骤1   从m个E-类中选取1个E-类的方法有m种，这个E-类不妨设为A={a₁，a₂，a₃}.

步骤2   下面分3种情形：

情形2.1   被f作用到A中的E类A_i(其中i∈{1，2，…，m})满足|f(A_i)|=1.此情形又有两种可能：

(P1) 对于任意i∈{1，2，…，m}，满足f(A_i)⊆A且f(X)={a₁，a₂，a₃}的变换有3^m-3(2^m-2)-3=3^m-3×2^m+3个.

(P2) i(i≥3)个E-类被变换f作用到A中，其它m-i个E-类被变换f作用到X/E-{A}中.满足这种可能的选法有C_mⁱ种.不妨设这i个E-类为A₁，A₂，…，A_i.下面考虑满足：

的变换f的个数.一方面，满足f(A₁∪A₂∪…∪A_i)={a₁，a₂，a₃}的选法有3ⁱ-3×2ⁱ+3个；另一方面，满足f(A_i+1∪A_i+2∪…∪A_m)⊆X/E-{A}的选法有(27(m-1))^m-i个.结合这两方面有(3ⁱ-3×2ⁱ+3)(27(m-1))^m-i个变换.因此对于这种可能共有$ \sum\limits_{i = 3}^{m - 1} {C_{_m}^{^i}} ({3^i} - 3 \times {2^i} + 3){(27(m - 1))^{m - i}} $个变换.

满足上述两种可能(P1)和(P2)的变换f有

个.

由此可知

但是对于任意E-类B∈{A₁，A₂，…，A_m}，有

由定理1知f是T_E(X)的非正则元.

情形2.2   被f作用到A中的E类A_i(其中i∈{1，2，…，m})满足|f(A_i)|=1或|f(A_i)|=2，并且存在i₁，i₂∈{1，2，…，m}，使得|f(A_i₁)|=1且|f(A_i₂)|=2.此情形又有两种可能：

(P3) 对于任意i∈{1，2，…，m}，满足f(A_i)⊆A且f(X)={a₁，a₂，a₃}，此时有$ C_{_3}^{^2}\sum\limits_{i = 1}^{m - 1} {C_{_m}^{^i}} {6^i} \times (2 \times ({2^{m - i}} - 1)) = \sum\limits_{i = 1}^{m - 1} {C_{_m}^{^i}} {6^{i + 1}}({2^{m - i}} - 1) $个.

(P4) i(i≥2)个E-类被变换f作用到A中，其它m-i个E-类被变换f作用到X/E-{A}中.满足这种可能的选法有C_mⁱ种.不妨设这i个E-类为A₁，A₂，…，A_i.下面考虑满足：

的变换f的个数.一方面，满足f(A₁∪A₂∪…∪A_i)={a₁，a₂，a₃}的选法有$ \sum\limits_{j = 1}^{i - 1} {C_{_i}^{^j}} {6^{j + 1}}({2^{i - j}} - 1) $个；另一方面，满足f(A_i+1∪A_i+2∪…∪A_m)⊆X/E-{A}的选法有(27(m-1))^m-i个.结合这两方面有$\left( {\sum\limits_{j = 1}^{i - 1} {C_{_i}^{^j}} {6^{j + 1}}({2^{i - j}} - 1)} \right){(27(m - 1))^{m - i}} $个变换.因此对于这种可能共有$\sum\limits_{i = 2}^{m - 1} {C_{_m}^{^i}} \left( {\sum\limits_{j = 1}^{i - 1} {C_{_i}^{^j}} {6^{j + 1}}({2^{i - j}} - 1)} \right){(27(m - 1))^{m - i}} $个变换.

满足上述两种可能(P3)和(P4)的变换f有

个.

由此可知

但是对于任意E-类B∈{A₁，A₂，…，A_m}，有A∩f(X)≠f(B).由定理1知f是T_E(X)的非正则元.

情形2.3   被f作用到A中的E-类A_i(其中i∈{1，2，…，m})满足|f(A_i)|=2.此情形又有两种可能：

(P5) 对于任意i∈{1，2，…，m}，满足f(A_i)⊆A且f(X)={a₁，a₂，a₃}的变换有3(2^m-2)6^m个.

(P6) i(i≥2)个E-类被变换f作用到A中，其它m-i个E-类被变换f作用到X/E-{A}中.满足这种可能的选法有C_mⁱ种.不妨设这i个E-类为A₁，A₂，…，A_i.下面考虑满足：

的变换f的个数.一方面，满足f(A₁∪A₂∪…∪A_i)={a₁，a₂，a₃}的选法有3(2ⁱ-2)6ⁱ个；另一方面，满足f(A_i+1∪A_i+2∪…∪A_m)⊆X/E-{A}的选法有(27(m-1))^m-i个.结合这两方面有(3(2ⁱ-2)6ⁱ)(27(m-1))^m-i个变换.因此对于这种可能共有$\sum\limits_{i = 2}^{m - 1} {C_{_m}^{^i}} (3({2^i} - 2){6^i}){(27(m - 1))^{m - i}} $个变换.

满足上述两种可能(P5)和(P6)的变换f有

个.

由此可知

但是对于任意E-类B∈{A₁，A₂，…，A_m}，有A∩f(X)≠f(B).由定理1知f是T_E(X)的非正则元.

因此在情形2下T_E(X)的非正则元的个数为

故在两种情形下半群T_E(X)的非正则元的个数为

根据定理2、引理2和引理3，得到本文的另一个主要结论：

定理4   设E是集合X上的(3，m)-型等价关系(其中m≥2)，则下面结论成立：

(ⅰ) 当m=2时，|(R(T_E(X)))|=2 400；

(ⅱ) 当m≥3时，

Reference (13)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	LARADJI A, UMAR A. Combinatorial Results for Semigroups of Order-Preserving Partial Transformations[J]. Journal of Algebra, 2004, 278(1):342-359. doi: 10.1016/j.jalgebra.2003.10.023 CrossRef Google Scholar
[2]	LARADJI A, UMAR A. Combinatorial Results for Semigroups of Order-Preserving Full Transformations[J]. Semigroup Forum, 2006, 72(1):51-62. doi: 10.1007/s00233-005-0553-6 CrossRef Google Scholar
[3]	FERNANDES V H, GRACINDA M S G, JESUS M M. The Cardinal and the Idempotent Number of Various Monoids of Transformations on a Finite Chain[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2011, 34(1):79-85. Google Scholar
[4]	FERNANDES V H, QUINTEIRO T M. The Cardinal of Various Monoids of Transformations That Preserve a Uniform Partition[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2012, 35(4):885-896. Google Scholar
[5]	SUN L. Combinatorial Results for Certain Semigroups of Transformations Preserving Orientation and a Uniform Partition[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2013, 36(1):179-192. Google Scholar
[6]	ZHANG J, LUO Y F. On Certain Order-Preserving Transformation Semigroups[J]. Communications in Algebra, 2017, 45(7):2980-2995. doi: 10.1080/00927872.2016.1233333 CrossRef Google Scholar
[7]	邓伟娜, 裴惠生.一类变换半群中幂等元的中心化子[J].西南大学学报(自然科学版), 2013, 35(2):55-61. Google Scholar
[8]	高荣海, 徐波.核具有连续横截面的保序变换半群的秩[J].西南师范大学学报(自然科学版), 2013, 38(4):18-24. Google Scholar
[9]	PEI H S. Equivalences, α-Semigroups and α-Congruences[J]. Semigroup Forum, 1994, 49(1):49-58. doi: 10.1007/BF02573470 CrossRef Google Scholar
[10]	PEI H S. Regularity and Green's Relations for Semigroups of Transformations That Preserve an Equivalence[J]. Communications in Algebra, 2005, 33(1):109-118. doi: 10.1081/AGB-200040921 CrossRef Google Scholar
[11]	PEI H S. On the Rank of the Semigroup T_E(X)[J]. Semigroup Forum, 2005, 70(1):107-117. doi: 10.1007/s00233-004-0135-z CrossRef Google Scholar
[12]	SUN L, PEI H S, CHENG Z X. Naturally Ordered Transformation Semigroups Preserving an Equivalence[J]. Bulletin of the Australian Mathematical Society, 2008, 78(2):117-128. Google Scholar
[13]	PEI H S, ZHOU H J. Abundant Semigroups of Transformations Preserving an Equivalence Relation[J]. Colloquium Algebra, 2011, 18(1):77-82. doi: 10.1142/S1005386711000034 CrossRef Google Scholar

Message Board

A Combinatorial Result for Certain Semigroups of Transformations Preserving an Equivalence Relation

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors