Burnside引理与Polya计数定理的理论与应用
2014-09-04 08:53徐春霞
考试周刊 2014年55期
徐春霞
摘 要： Burnside引理和polya定理是组合数学中具有重要地位的两个定理.本文用Burnside引理和polya定理对一道题得出多种解法.
关键词： Burnside引理 polya定理 轮换指标 循环群
1.引言
Burnside引理主要用于解决下面的问题：设x是有限集，群G作用在X上，如果按照某个给定并的规则，将x中的元素分成若干个G一等价类，也就是将x分成若干个无交轨道的，如何求这些等价类的个数。此类问题在生产和科研中经常碰到.
Polya定理是组合数学中一个十分有力的计数工具.主要用于解决下面的问题：设A是一个有限集，如果按照某个给定的规则G，将A中的元素分成若干G一等价类，如何求这些等价类的个数？这类问题在生产和科学中经常碰到，如图的顶点、边、面的染色和图的计数，等等.Burnside引理能给上述问题一种方法，而Polya定理能给出更一般的解题方法.可以说Polya定理是Burnside引理的推广，但有些问题用Burnside引理解比用Polya定理来得更快.因此相应的计数问题就可以Polya用计数定理解决.
2.主要概念与定理
Burnside引理和Polya定理内容陈述方法有很多种，不同的文献上可能有不同的说法，但基本思想是一致的，本文主要采用邵嘉裕的《组合数学》.下面是本文要用到的定义和定理[1].
定义1：（置换的轮换分解式）有限集A上的任意置换f可表为使A中的文字全部出现的若干个两两无公共文字轮换的乘积，而且这种表示方式除了轮换的次序之外是唯一的.
参考文献：
[1]卢开澄，卢明华.组合数学（第三版）[M].北京：清华大学出版社，2002.7.
[2]李乔.组合数学讲义.北京：高等教育出版社，2008.endprint
摘 要： Burnside引理和polya定理是组合数学中具有重要地位的两个定理.本文用Burnside引理和polya定理对一道题得出多种解法.
关键词： Burnside引理 polya定理 轮换指标 循环群
1.引言
Burnside引理主要用于解决下面的问题：设x是有限集，群G作用在X上，如果按照某个给定并的规则，将x中的元素分成若干个G一等价类，也就是将x分成若干个无交轨道的，如何求这些等价类的个数。此类问题在生产和科研中经常碰到.
Polya定理是组合数学中一个十分有力的计数工具.主要用于解决下面的问题：设A是一个有限集，如果按照某个给定的规则G，将A中的元素分成若干G一等价类，如何求这些等价类的个数？这类问题在生产和科学中经常碰到，如图的顶点、边、面的染色和图的计数，等等.Burnside引理能给上述问题一种方法，而Polya定理能给出更一般的解题方法.可以说Polya定理是Burnside引理的推广，但有些问题用Burnside引理解比用Polya定理来得更快.因此相应的计数问题就可以Polya用计数定理解决.
2.主要概念与定理
Burnside引理和Polya定理内容陈述方法有很多种，不同的文献上可能有不同的说法，但基本思想是一致的，本文主要采用邵嘉裕的《组合数学》.下面是本文要用到的定义和定理[1].
定义1：（置换的轮换分解式）有限集A上的任意置换f可表为使A中的文字全部出现的若干个两两无公共文字轮换的乘积，而且这种表示方式除了轮换的次序之外是唯一的.
参考文献：
[1]卢开澄，卢明华.组合数学（第三版）[M].北京：清华大学出版社，2002.7.
[2]李乔.组合数学讲义.北京：高等教育出版社，2008.endprint
摘 要： Burnside引理和polya定理是组合数学中具有重要地位的两个定理.本文用Burnside引理和polya定理对一道题得出多种解法.
关键词： Burnside引理 polya定理 轮换指标 循环群
1.引言
Burnside引理主要用于解决下面的问题：设x是有限集，群G作用在X上，如果按照某个给定并的规则，将x中的元素分成若干个G一等价类，也就是将x分成若干个无交轨道的，如何求这些等价类的个数。此类问题在生产和科研中经常碰到.
Polya定理是组合数学中一个十分有力的计数工具.主要用于解决下面的问题：设A是一个有限集，如果按照某个给定的规则G，将A中的元素分成若干G一等价类，如何求这些等价类的个数？这类问题在生产和科学中经常碰到，如图的顶点、边、面的染色和图的计数，等等.Burnside引理能给上述问题一种方法，而Polya定理能给出更一般的解题方法.可以说Polya定理是Burnside引理的推广，但有些问题用Burnside引理解比用Polya定理来得更快.因此相应的计数问题就可以Polya用计数定理解决.
2.主要概念与定理
Burnside引理和Polya定理内容陈述方法有很多种，不同的文献上可能有不同的说法，但基本思想是一致的，本文主要采用邵嘉裕的《组合数学》.下面是本文要用到的定义和定理[1].
定义1：（置换的轮换分解式）有限集A上的任意置换f可表为使A中的文字全部出现的若干个两两无公共文字轮换的乘积，而且这种表示方式除了轮换的次序之外是唯一的.
参考文献：
[1]卢开澄，卢明华.组合数学（第三版）[M].北京：清华大学出版社，2002.7.
[2]李乔.组合数学讲义.北京：高等教育出版社，2008.endprint
