Burnside定理在组合计数问题中的应用.pdfVIP

维普资讯 第 28卷第3期 黄 冈 师 范 学 院 学 报 Vo1．28No．3 2008年 6月 JournalofHuanggangNormalUniversity Jun．2008 Burnside定理在组合计数 问题 中的应用 董 金 辉 (黄冈师范学院 数学与信息科学学院，湖北 黄州 438000) 摘要 针对一类组合计数方面的实际问题，利用二面体群、正多面体的对称性群等群的相关知 识给 出确切 的数学描述，并运用Burnside轨道计数定理有效地加 以解决，突破 了用枚举法解 决此类 问题 的局 限性． 关键词 组合计数；二面体群 ；置换 ；Burnside定理 中图分类号 O152．8 文献标识码 B 文章编号 1003—8078(2008)03—0013—02 M SC2000 20A 15 Theapplication ofBurnsidetheorem tocombinatorialenumeration DoNG Jin—hui (CollegeofMathematicsandInformationScience，HuanggangNormalUniversity，Huangzhou438000，Hubei，China) Abstract Objective：Togiveamethodforthespecialcombinatorialenumerationproblem．Methods： Totranslatethecombinatorialenumerationissueintogroupissuebythegrouptheory，especiallythe Burnsidetheorem．ResultsConclusion：Thegivenmethodisefficientandthere’Snobettermethodat present． Keywords combinatorialenumeration；dihedralgroup；permutation；Burnsidetheorem 组合计数 问题是数学分支 中一个重要且困难 的问题，其 中的某些计数问题，如项链 问题(用 n颗带 颜色的珠子，做成有m颗珠子的项链 ，可以做 出多少不同类型的项链?)、正多面体顶点着色问题 (用 种颜色对正多面体 的顶点进行着色 ，有多少种不同的着色方法?)，它们有一个共 同点，那就是在乘法原 理中两类不同的结果 ，由于实物本身的对称性 ，经过旋转或翻转可以完全重合 ，即本质上是一样的，而我 们要计数的恰恰是考虑本质上不相同的种类．这两类问题在情况简单时可以采用枚举法解决，在情况复 杂时枚举法当然不适用 了，此时采用群论的知识可 以有效地得到解决． 1基本概念 定义 1．1 若 次置换 的标准轮换分解式是 由 个 1一轮换 ， 个 2一轮换 ，…， 个 一轮换组 成 ，则称 是一个 1-2z… ～型置换． 定义 1．2 设群 G作用于集合 上，g∈G，，∈M，若 g()一 ，则称 是g的一个不动点．g在 M 上的不动点作成的集合记为Fix(g)． 收稿 日期 ：2008—03—02． 作者简介 ：董金辉 ，男．湖北黄冈人 ，助教，主要从事代数应用研究． 基金项 目：黄 冈师范学院青年科学基金重点项 目(No．2006．4．o6CQ70) 维普资讯 ·14· 黄 冈 师 范 学 院 学 报 第 28卷 Burnside引理 设有 限群群 G作用于有 限集合 上 ．则 在 G作用下的轨道数 目为 N = ∑]Fix(g)}，其中和式是对每一个群