代数教学中的组合方法

Combinatorial Approach in Algebra Teaching

摘要: 代数学是最重要和基础的数学分支之一。有数学专业的高校都开设了《高等代数》和《抽象代数》课程。组合数学是一门技巧性很强的数学学科。在代数课的教学过程中，引入组合的方法不但能开阔学生的眼界，还能让学生体会到数学专业不同课程之间交叉应用的重要性。本文给出了两种运用组合技巧解决代数问题的方法，其一是通过构造图来求排列的逆序数；其二是将霍尔定理运用到子群陪集的理论中。这两种方法不仅可以帮助学生理解和掌握相关知识点，还能够激发学生探索未知的兴趣。

Abstract: Algebra is one of the most important and basic branches of mathematics. Universities with mathematics majors have offered courses of “Advanced Algebra” and “Abstract Algebra”. Combinatorics is a highly skilled mathematics subject. In the teaching of algebra, the introduction of combinatorial method can not only broaden the horizons of students, but also let students realize the importance of cross-application between different courses in mathematics. The paper presents two methods of solving algebraic problems using combinatorial techniques. One is to find the reverse sequence number of the arrangement by constructing a graph. The other is the application of Hall’s Theorem to the study of the theory of subgroup cosets. These two methods can not only help students understand and master relevant knowledges, but also stimulate students’ interest in exploring the un-known.

1. 引言

代数学和组合数学是数学领域中两门重要学科。这两门学科的研究对象和研究方法虽然有各自的特点，但是在很多情况下可以相互渗透，相互影响。一方面，利用属于代数学中的群论可以研究图和超图等组合结构的对称性 [1] ；利用线性代数理论可以研究图的谱 [2] 。另一方面，组合数学里的一些经典理论和方法可用于解决代数学中的一些问题 [3] 。排列的逆序数和子群的陪集分别是《高等代数》和《抽象代数》中重要的知识点，我们将在本文中用组合的方法来研究这两块内容。

文献中关于排列的逆序数和子群的陪集已有很多研究，我们在这里只对与本文内容比较相近的研究做一些简单的综述。

对排列的逆序数进行计算是一个重要问题，这是因为排列的逆序数有很多的应用。在学习线性代数的时候，我们已经知道可以借助于排列的逆序数定义n阶行列式。在文献 [4] 中，王廷明深入探讨了排列的一些性质，并介绍了排列的逆序数在证明一些代数问题时的应用。在文献 [5] 中，赵静等人介绍了排列的逆序数在魔方问题和最优截断切割问题中的应用。关于排列逆序数的计算，除了常用教材中给出的一些常规计算方法外，有很多学者也给出了一些新的计算方法。比如，文献 [6] 给出了关于排列逆序数的若干计算公式；文献 [7] 给出了n阶排列中相同逆序数的排列个数的递推算法；文献 [8] 通过将置换表示成不交轮换的乘积来计算逆序数。我们将在本文中引进逆序图的概念，并给出通过逆序图求排列逆序数的方法。

子群的陪集是群论中一个非常重要的概念，它可以用来刻画子群的正规性，还可以用于构造一些组合结构(这其中最著名的就是陪集图)。文献中关于子群的陪集及其应用的研究有非常多，我们仅对一些比较有代表性的文章进行综述。文献 [9] 研究了子群的单侧陪集和双侧陪集的性质。文献 [10] 给出了子群的陪集和群的同构定理的几何解释。文献 [11] 通过在子群陪集上定义一种运算来研究子群的一些性质。在文献 [12] 中，化小会等人介绍了陪集图的概念，并研究了陪集图的同构与自同构。在文献 [13] 中，王佳利等人借助于陪集图给出了无平方因子阶的本原2-弧传递图的分类与刻画。在本文中，我们考虑两个阶数相同的子群的公共陪集代表系问题，借助于组合数学中的霍尔定理证明了两个阶数相同的群一定有公共的陪集代表系。

本文分五小节，引言部分是我们的第一小节。在第二小节中，我们将介绍组合数学中的一些概念，并引出霍尔定理的陈述。在第三小节，我们给出通过逆序图求排列逆序数的方法。在第四小节，我们用霍尔定理研究子群的陪集，证明两个阶数相同的群有公共的陪集代表系。第五小节介绍在教学实践环节中这两种组合方法的具体运用及其效果。

2. 图的概念与霍尔定理

本文中涉及到的图指的是顶点数有限且没有重边和自环的无向图。首先我们给出图以及与之相关的一些概念。图 $$ 是两个集合组成的有序对，其中V是一个有限的非空集合，称为顶点集，其元素称为顶点，E是由V中的顶点组成的无序对构成的集合，称为边集，其元素称为边。对于 $u,v\in V$ ，如果 $\left\{u,v\right\}\in E$ ，则称u与v相邻。若图Γ的顶点集V可划分为X和Y两个子集(即 $V=X\cup Y$ ， $X\cap Y=\varnothing$ )，且Γ的任意一条边的两个顶点不同时在X中，也不同时在Y中，则称Γ是一个以X和Y为二部划分的二部图。

设M是图Γ的边集的一个子集，若M中的任意两条边没有共同顶点，则称M是Γ的一个匹配，称M的任意一条边的顶点为此匹配所许配的顶点。关于二部图与匹配，有如下著名定理。

霍尔定理 [14] 设Γ是一个二部图，其顶点集的二部划分为X和Y。则Γ中存在把X的顶点皆许配的匹配的充要条件是对 $\forall S\subseteq X$ ，都有 $\left|S\right|\le \left|N\left(S\right)\right|$ 。其中 $N\left(S\right)$ 是图Γ中与S中的某个顶点相邻的顶点的集合。

3. 用构造图的方法求排列的逆序数

由 $1,2,\cdots ,n$ 组成的一个有序数组称为一个n阶排列。在一个排列中，如果一对数的前后位置与大小顺序相反，则称这对数为一个逆序，称一个排列中逆序的总数为这个排列的逆序数。

设 $i_1,i_2,\cdots ,i_n$ 是一个n阶排列。定义图Γ如下：Γ的顶点集为 $1,2,\cdots ,n$ ，两个顶点 $i_k$ 与 $i_l$ ( $k\le l$ )在Γ中相邻的充要条件是 $i_k\ge i_l$ 。则图Γ的边的个数正好等于排列 $i_1,i_2,\cdots ,i_n$ 的逆序数，称这个图为排列 $i_1,i_2,\cdots ,i_n$ 的逆序图。

易见，自然顺序排列 $1,2,\cdots ,n$ 的逆序图是空图(即边集为空集的图)，因此其逆序数为0。倒序排列 $n,n-1,\cdots ,2,1$ 的逆序图是n个顶点的完全图(任意两个不同顶点都相邻的图)，因此其逆序数为 $\frac{n\left(n-1\right)}{2}$ 。下面举一些利用逆序图求排列逆序数的例子。

例1求排列2，1，7，9，8，6，3，5，4和10，1，8，3，6，5，4，7，2，9的逆序数。

解排列2，1，7，9，8，6，3，5，4和10，1，8，3，6，5，4，7，2，9的逆序图分别如下：

这两个逆序图的边数分别是18和23，因此排列2，1，7，9，8，6，3，5，4的逆序数是18，排列10，1，8，3，6，5，4，7，2，9的逆序数是23。

例2如果排列 $i_1,i_2,\cdots ,i_{n-1},i_n$ 的逆序数是m，则排列 $i_n,i_{n-1},\cdots ,i_2,i_1$ 的逆序数是多少？

解 设排列 $i_1,i_2,\cdots ,i_{n-1},i_n$ 的逆序图是Γ。因为 $i_k$ 与 $i_l$ 构成逆序的充要条件是 $i_l$ 与 $i_k$ 不构成逆序，所以排列 $i_n,i_{n-1},\cdots ,i_2,i_1$ 的逆序图是Γ的补图 $\bar{\Gamma }$ (即 $i,j$ 在 $\bar{\Gamma }$ 中相邻当且仅当它们在Γ中不相邻)。注意到Γ和 $\bar{\Gamma }$ 的边数之和是 $\frac{n\left(n-1\right)}{2}$ ，所以排列 $i_1,i_2,\cdots ,i_{n-1},i_n$ 和 $i_n,i_{n-1},\cdots ,i_2,i_1$ 的逆序数之和是 $\frac{n\left(n-1\right)}{2}$ 。因 $i_1,i_2,\cdots ,i_{n-1},i_n$ 的逆序数是m，所以 $i_n,i_{n-1},\cdots ,i_2,i_1$ 的逆序数是 $\frac{n\left(n-1\right)}{2}-m$ 。

众所周知，行列式理论在高等代数中有着基本而重要的作用，而排列的逆序数是在行列式的定义过程不可绕开的一个概念。但是这一概念过于抽象，初学者理解起来比较困难。在讲授逆序数概念时，画出对应的逆序图，不但有利于学生对概念的理解，还可以给学生提供一种更具体和更直观的求逆序数的方法。

4. 用霍尔定理研究子群的陪集

群是代数学中一个重要的概念，是研究一些几何结构或组合结构的对称性的重要工具。设G是一个非空集合，在其上定义一个二元运算“ $\cdot$ ”，满足如下三条公理：

a) 结合律成立，即对 $\forall a,b,c\in G$ ，都有 $\left(a\cdot b\right)\cdot c=a\cdot \left(b\cdot c\right)$ ；

b) 在G中存在单位元e，满足条件：“ $\forall a\in G$ ，都有 $a\cdot e=e\cdot a=a$ ”；

c) 对 $\forall a\in G$ ，存在 $b\in G$ ，使得 $a\cdot b=e$ 。称b为a的逆元，记为 $a^{-1}$ 。

称G对于上述运算构成一个群。简便起见，在实际操做中常常把运算符号“ $\cdot$ ”省去，即用ab记 $a\cdot b$ 。如果G是有限集合，则称G为有限群。如果G为无限集合，则称G为无限群。对于一个群G以及G的子集H，若H关于G中的运算也构成群，则称H为G的一个子群。

设H为群G的一个子群，g是G中的一个元素，T是G的一个子集，称集合 $Hg=\left\{hg|h\in G\right\}$ 为H在G中的一个右陪集，若 $G=\left\{ht|h\in H,t\in T\right\}$ 并且对任意两个不同的 $t,t^{\prime }\in T$ ，都有 $Ht\ne H{t}^{\prime }$ ，则称T为H在G中的一个右陪集代表系。对于两个子群，它们的右陪集代表系有什么样的关系呢？可以用霍尔定理证明如下有趣的定理。

定理1设G是一个有限群，H和K是G的两个子群。若 $\left|H\right|\ge \left|K\right|$ ，则存在G的子集A和B，使得 $A\subseteq B$ ，并且它们分别是H和K在G中的右陪集代表系。特别地，如果 $\left|H\right|=\left|K\right|$ ，则它们有相同的右陪集代表系。

证明用 $G{/}_{\text{R}}H$ 和 $G{/}_{\text{R}}K$ 分别表示H和K在G中的所有右陪集所组成的集合。构造二部图Γ如下：Γ顶点集的二部图划分为 $G{/}_{\text{R}}H$ 和 $G{/}_{\text{R}}K$ ，对任意 $Hx\in G{/}_{\text{R}}H$ 和 $Ky\in G{/}_{\text{R}}K$ ，Hx与Ky相邻的充要条件是 $Hx\cap Ky\ne \varnothing$ 。因为 $\left|H\right|\ge \left|K\right|$ ，所以 $\left|G{/}_{\text{R}}H\right|\le \left|G{/}_{\text{R}}K\right|$ 。取 $G{/}_{\text{R}}H$ 的任意一个子集 $S=\left\{H{x}_1,H{x}_2,\cdots ,H{x}_s\right\}$ ，并用 $N\left(S\right)=\left\{K{y}_1,K{y}_2,\cdots ,K{y}_t\right\}$ 表示Γ中与S中的顶点相邻的顶点的集合。则

$s\left|H\right|={\displaystyle {\sum }_{i=1}^s\left|H{x}_i\right|}\le {\displaystyle {\sum }_{i=1}^t\left|K{y}_i\right|}=t\left|K\right|$ 。

因为 $\left|H\right|\ge \left|K\right|$ ，所以 $s\le t$ ，即 $\left|S\right|\le \left|N\left(S\right)\right|$ 。根据霍尔定理，Γ中存在把 $G{/}_{\text{R}}H$ 中顶点皆许配的匹配。设

$\left\{H{a}_1,K{a}_1\right\},\left\{H{a}_2,K{a}_2\right\},\cdots ,\left\{H{a}_m,K{a}_m\right\}$

是这样的一个匹配，并设 $G{/}_{\text{R}}K$ 中除 $K{a}_1,\cdots ,K{a}_m$ 之外的其他陪集为 $K{b}_1,\cdots ,K{b}_n$ 。令

$A=\left\{a_1,\cdots ,a_m\right\},B=\left\{a_1,\cdots ,a_m,b_1,\cdots ,b_n\right\}$

则 $A\subseteq B$ ，并且它们分别是H和K在G中的右陪集代表系。证毕。

需要强调的是，定理1是作者在讲授近世代数课时想到的。据作者掌握的文献，没有发现在哪里有给出这个定理。

设H为群G的一个子群，g是G中的一个元素，T是G的一个子集，称集合 $gH=\left\{gh|h\in G\right\}$ 为H在G中的一个左陪集，若 $G=\left\{th|t\in T,h\in H\right\}$ 并且对任意两个不同的 $t,t^{\prime }\in T$ ，都有 $tH\ne t^{\prime }H$ ，则称T为H在G中的一个左陪集代表系。在定理1中把右陪集代表系改为左陪集代表系，得到的新命题仍然是真命题，其证明方法和定理1的证明也是一样的，故略去。所以我们有如下定理。

定理2设G是一个有限群，H和K是G的两个子群。若 $\left|H\right|\ge \left|K\right|$ ，则存在G的子集A和B，使得 $A\subseteq B$ ，并且它们分别是H和K在G中的左陪集代表系。特别地，如果 $\left|H\right|=\left|K\right|$ ，则它们有相同的左陪集代表系。

霍尔定理是一个应用性很强的定理。在图论和组合数学教材里，已经展示了这个定理的在日常生活中的各种应用。比如，在分配任务、物流调度等方面的应用。通过定理1的证明，可以看出这一定理在其他数学课程中也有应用。定理1完全可以用纯群论的方法给出证明，但是证明过程会非常复杂。我们通过定理1的证明展示了图论与抽象代数两门课程之间的一个联系。事实上，代数学与图论的深入融合已经发展成为了一个重要的研究领域，也就是代数图论。在讲授抽象代数或图论课的时候，适当地介绍一点这方面的内容，可以开阔学生的视野，激发学生的兴趣，引导学生探索当今数学的前沿问题。

5. 教学实践

用逆序图计算排列逆序数的方法在2021年和2022年的高等代数课堂上各用过一次，授课对象是数学与应用数学专业的大一学生。虽然组合数学或者图论是数学专业高年级才开设的课程，但是图这一概念并不是那么抽象，比较容易理解，还可以在黑板上或PPT中演示。我们的课程设计安排如下：先介绍常规的计算排列的逆序数的方法，并告诉大家中学时常用的数形结合思想也可以用来计算排列的逆序数，这样就调动起了学生的好奇心；接着介绍图的概念，特别地在黑板上画了很多典型的图；然后给出逆序图的概念，并引导学生给出用逆序图求排列逆序数的方法；最后提出了一些问题供学有余力的同学思考。在授课过程中，学生的反应还是比较积极的。并且发现很多同学早已经知道了图这一概念，可能是这部分学生在中小学时参加过奥数培训，已经学过关于图的一些基本知识。在给出逆序图的定义以后，一些反应比较快的学生马上就意识到了逆序数就等于逆序图的边数。整节课还是比较顺利的，增加的用逆序图计算排列逆序数的内容大概只占用了20分钟的时间。课堂的最后提出的问题后来也得到了反馈，一些学习积极的同学在课下还与我进行交流，给出了部分问题的解答。

用霍尔定理研究子群陪集的方法在2022年给研究生开设的有限群论讨论班上用过一次。将来计划在高年级的抽象代数课堂上运用。参与有限群论讨论班的学生都是基础数学专业的学生，大部分同学的研究方向是代数组合，还有几个是同调代数方向的。这些学生都是研究生一年级，他们本科时已经学过组合数学或图论，对图论中的相关概念还是比较熟悉的，对霍尔定理也有印象，但是只有个别同学能够说出霍尔定理的内容。由于是讨论班，师生之间一直在互动。我们首先讨论了子群的陪集、群的正规性等内容。接着很自然地引出问题：两个阶数相同的子群是否一定有相同的陪集代表系。通过分析几个特殊的例子以后，同学们坚信问题的答案是肯定的。然后大家开始讨论如何给出证明，尝试了很多中方法都失败了。这时我引导大家可以考虑用组合的方法去尝试，有些同学开始建议用构造图的办法去处理。这个建议得到了认可，图也成功构造出来了，但是接下来怎么分析呢？在经过认真的思考后，有同学说用霍尔定理应该可以解决，但是大部分同学已经忘了霍尔定理的内容。于是我们又讨论了霍尔定理，并且给出了这个定理的证明。最后我们用霍尔定理证明了想要的结论。这次讨论课是非常成功的，学生们初步体验到了组合数学与代数学之间相互融合的魅力，他们的探索未知的兴趣被激发了出来。

基金项目

重庆市教育委员会科学技术研究项目(KJQN20180512)。