Burnside引理和Polya定理

摘要:
由Burnside引理:[|X/G|=frac1{|G|}sum_{ginG}|X^g|]这里阐述记号:(|G|)表示置换群的大小,,即初始状态通过的置换不变构成的集合。若要理解和证明该引理,需要引入轨道稳定子定理。Burnside引理的推导上述定理描述了单个状态不动的置换数的关系,而Burnside引理则描述了单个置换下不动的状态数的关系,我们尝试先建立联系:[sum_{ginG}|X^g|=sum_{ginG}sum_{xinX}[g=x]=sum_{xinX}|G^x|]由轨道稳定子定理:[|G^x|=frac{|G|}{|O^x|}]故:[sum_{xinX}|G^x|=|G|sum_{xinX}frac1{|O^x|}]现在考虑与建立联系。改变枚举方式:[sum_{xinX}frac1{|O^x|}=sum_{xinX/G}sum_{yinO^x}frac1{|O^x|}=sum_{xinX/G}1=|X/G|]整理得[sum_{ginG}|X^g|=|G||X/G|]即证[|X/G|=frac1{|G|}sum_{ginG}|X^g|]Pólya定理该定理是Burnside引理的进一步推导。
一类与对称相关的计数问题

栗子:给一个手镯,上面有 (n) 颗珠子,由线串成环。每种珠子可能有 红、黄、绿、蓝 四种颜色。问本质不同的手镯有多少种。对于两种手镯本质相同,当且仅当一种手镯能通过旋转和翻转变换与另一种手镯重合。

抽象化

对于这类问题,我们规范化定义:设集合 (A) 表示按照顺序编号手镯的每个珠子,(B) 表示四种颜色,(X:A ightarrow B) 表示每个珠子对应一种颜色。对于旋转、翻转等操作,都可以使用置换来描述。所有操作构成的置换构成 置换群(G),称为群是由于其内的元素满足群的定义和特点。显然,(X) 中某些元素可以通过 (G) 中的操作相互转化,这些元素在 (G) 下是 等价的,问题也就是 (X)(G) 下的 等价类个数,记作 (|X/G|)

Burnside引理

[|X/G|=frac1{|G|}sum_{gin G}|X^g| ]

这里阐述记号:(|G|) 表示置换群的大小,(X^g={x|g(x)=x,xin X}),即初始状态通过 (g) 的置换不变构成的集合。

若要理解和证明该引理,需要引入 轨道稳定子定理

轨道稳定子定理

这里考查单个状态 (xin X)(G) 的影响。首先,至少有 (ein G)(即啥也不做的变换),使得 (x) 在变换中保持原样。定义 (G^x={g|g(x)=x,gin G}),表示使 (x) 不改变的置换构成的集合,称 (G^x)(x)稳定子;与之相对,定义 (O^x={g(x)|gin G}),即 (x) 通过变换得到的所有状态构成的集合,这里 (O^x) 称之为 (x)轨道

定理的内容:

[|G|=|G^x||O^x| ]

下面来证明。首先,由群论的相关知识,不难证明 (G^x) 能构成群,故由 拉格朗日定理

[|G|=|G^x|[G:G^x] ]

这里 ([G:G^x]) 表示 (G^x) 不同的 陪集 数目。注意陪集互不相交且大小相等,共同构成了(G)的划分。

现在我们需要证明 (|O^x|=[G:G^x])。不难发现 (|O^x|leq |G|),也就是 有可能 两种置换 (g,hin G) 满足 (g(x)=h(x)),即被对应到轨道中 同一个点,继续推导:

[g(x)=h(x)Rightarrow (g^{-1}circ h)(x)=xRightarrow g^{-1}circ hin G^xRightarrow hin gG^x ]

(gG^x)(G^x) 的陪集。发现 (g(x) eq h'(x)) 得到的是 (h' otin gG^x)。这表明 轨道(O^x)上的每一个不同的点,都会被映射到不同的陪集中。这里则证明了 (O^x)(G:G^x) 满足 单射

显然 (forall gin G)(g) 必然遍布 (G^x) 的所有陪集,并且 (g(x)in O^x)。故所有陪集中,(g(x)) 一定在 (O^x) 中。这里则证明了 (O^x)(G:G^x) 满足 满射

(O^x ightarrow G:G^x) 满足 双射,即证 (|O^x|=[G:G^x])

Burnside 引理的推导

上述定理描述了 单个状态不动的置换数 的关系,而 Burnside引理 则描述了 单个置换下不动的状态数 的关系,我们尝试先建立联系:

[sum_{gin G}|X^g|=sum_{gin G}sum_{xin X}[g(x)=x]=sum_{xin X}|G^x| ]

轨道稳定子定理

[|G^x|=frac{|G|}{|O^x|} ]

故:

[sum_{xin X}|G^x|=|G|sum_{xin X}frac1{|O^x|} ]

现在考虑与 (|X/G|) 建立联系。对于 (xin X/G),是某一个 等价类(的代表),其等价类大小即为 (|O^x|)(即 (x) 能通过变换得到的所有状态)。

改变枚举方式:

[sum_{xin X}frac1{|O^x|}=sum_{xin X/G}sum_{yin O^x}frac1{|O^x|}=sum_{xin X/G}1=|X/G| ]

整理得

[sum_{gin G}|X^g|=|G||X/G| ]

即证

[|X/G|=frac1{|G|}sum_{gin G}|X^g| ]
Pólya 定理

该定理是 Burnside引理 的进一步推导。考虑化简 (|X^g|)。由于 (g) 是一种置换,在这种置换下 (x) 不变的方案数,与 置换分解出来的环的数量 有关。显然一个环中的元素必须全部相等,令 (c(g)) 表示置换 (g) 分解出来的环的数量,则 (|X^g|=|B|^{c(g)}),这里 (B)(X:A ightarrow B) 的像。

所以得到

[|X/G|=frac1{|G|}sum_{gin G}|B|^{c(g)} ]

免责声明:文章转载自《Burnside引理和Polya定理》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇CSS clear both清除浮动总结线程池QueueUserWorkItem下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

多线程多核编码优化思路_转载

程序功能:求从1一直到 APPLE_MAX_VALUE (100000000) 相加累计的和,并赋值给 apple 的a 和b ;求 orange 数据结构中的 a[i]+b[i ] 的和,循环 ORANGE_MAX_VALUE(1000000) 次。 说明: 由于样例程序是从实际应用中抽象出来的模型,所以本文不会进行 test.a=test.b= te...

Football 南邮NOJ网络选拔赛2082

Football 时间限制(普通/Java) : 1000 MS/ 3000 MS          运行内存限制 : 65536 KByte总提交 : 246            测试通过 : 59  题目描述 现在你是一名足球经理,你的队伍将参加“南邮杯”的比赛。然而你拥有预知未来的能力,你可以预见你的队伍接下来进行的n场比赛每场的进球数和失球...

关于sum(int)报错:将expression转化为数据类型int时发生算术溢出错误

在SQL Server 中,某列的数据都在int范围之内,但是使用sum聚集函数求该列和的时候,出现“将expression转化为数据类型int时发生算术溢出错误”。 首先,我们先看看SQL Server 定义的数据类型的长度: bigint   数据类型存储从   -2^63   (-9223372036854775808)   到   2^63-1...

oracle 表空间不足解决办法

Oracle表空间不足,一般有两个原因:   1. 原表空间太小,没有自增长;   2. 表空间已自增长,而且表空间也已足够大 检查原因: 1. 查看表在那个表空间 select tablespace_name,table_name from user_talbes where table_name='test'; 2. 获取用户的默认表空...

SQL中AVG、COUNT、SUM、MAX等聚合函数对NULL值的处理

一、AVG()求平均值注意AVE()忽略NULL值,而不是将其作为“0”参与计算  二、COUNT() 两种用法 1、COUNT(*)对表中行数进行计数不管是否有NULL 2、COUNT(字段名)对特定列有数据的行进行计数忽略NULL值  三、MAX()、MIN()求最大、最小值都忽略NULL  四、SUM()可以对单个列求和,也可以对多个列运算后求和忽略...

【学习】Python进行数据提取的方法总结【转载】

链接:http://www.jb51.net/article/90946.htm 数据提取是分析师日常工作中经常遇到的需求。如某个用户的贷款金额,某个月或季度的利息总收入,某个特定时间段的贷款金额和笔数,大于5000元的贷款数量等等。本篇文章介绍如何通过python按特定的维度或条件对数据进行提取,完成数据提取需求。 准备工作首先是准备工作,导入需要使用...