专题路线

代数与离散结构

先以群、环、域与模建立抽象代数框架,再回到计数、递推、图论与偏序等有限离散结构。

2 个阶段12 章预计 16 小时
学习进度0/12 章完成
0%
开始学习群、子群与循环结构
先修内容

具备数学证明基础,希望系统学习代数结构并连接组合与图论方法的学习者。

学习阶段

阶段自测

  1. 学完 M14 · 群、环、域与 Galois 思想综合复习

    陈述群同态基本定理与 Lagrange 定理,并各举一个例子说明正规子群条件与阶数整除性在结论中为何缺一不可。

  2. 学完 M07 · 组合、图论与离散证明综合复习

    给定一个二部图匹配问题,说明 Hall 条件如何判定完美匹配存在,并给出容斥原理在同一类计数问题中的不同用途。

综合练习

练习完成进度:0/2

难度 3/5

用 Lagrange 定理限制有限群的元素阶

设 G 是 12 阶群,a∈G。列出 a 的可能阶;若 G 为循环群 Z₁₂,分别求元素 8 的阶和 G 中生成元的个数。

查看提示

元素阶等于其生成循环子群的阶,必整除 |G|;Zₙ 中元素 k 的阶为 n/gcd(n,k),生成元与 n 互素。

展开分步解答

由 Lagrange 定理,a 的阶整除 12,故可能值为 1、2、3、4、6、12。在 Z₁₂ 中,ord(8)=12/gcd(12,8)=12/4=3。生成元个数为模 12 简化剩余系的元素数 φ(12)=12(1-1/2)(1-1/3)=4,即 1、5、7、11。

结果核验:直接验证 ord(8):8+8+8=24≡0 (mod 12),而 8 与 16 均不同余 0,阶确为 3;1、5、7、11 恰为全部与 12 互素的剩余类,计数与 φ(12)=4 一致。

难度 3/5

容斥原理推导错排数公式

用容斥原理推导 n 个元素错排(无不动点的置换)数 Dₙ 的显式公式,并计算 D₄ 的值。

查看提示

设 Aᵢ 为固定第 i 个元素的置换集合,错排数等于全部置换数减去 Aᵢ 之并,k 个集合交的大小为 (n-k)!。

展开分步解答

由容斥原理,Dₙ=Σ_{k=0}^{n} (-1)^k C(n,k)(n-k)!=n! Σ_{k=0}^{n} (-1)^k/k!。代入 n=4:D₄=24(1-1+1/2-1/6+1/24)=24·(9/24)=9。

结果核验:直接枚举得 D₂=1、D₃=2,再用递推 Dₙ=(n-1)(Dₙ₋₁+Dₙ₋₂) 计算 D₄=3(2+1)=9,与容斥公式一致;n! 乘以部分和也逼近 n!/e,符合渐近比例。

参考资料