组合结果的研究是变换半群理论中一个有趣的课题，对于变换半群结构的研究有着重要意义.关于各类变换半群组合数的研究，参看文献[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_i1)|=1且|f(A_i2)|=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时，