组合数学常用内容——Polya定理+Burnside引理

2024-04-08 00:58

本文主要是介绍组合数学常用内容——Polya定理+Burnside引理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Burnside引理

设G是N{1,2,.....,n}上的置换群,G在N上可引出不同的等价类(在置换群中有置换的都等价),其不同的等价类的个数为LL=1/|G|*(c1(a1)+...c1(ai)...+c1(ag))c1表示置换ai作用过后不变的方案数,也就是置换中循环节长度是1的循环个数(N中的元素是组合方案的序号不是自然数!此置换群是关于所有着色图像(所有可能的情况)集合N的置换)Burnside应用关键:如何构造置换群(图形上来说一般为根据中心点,对称轴进行旋转和翻转)缺陷:置换是作用在所有方案上的,如果颜色数量过多,方案随之剧增,Burnside无能为力;

Polya定理

设G是n个对象的一个置换群(此置换群是关于所有被着色对象集合的置换),用m种颜色对这n个对象进行着色,则不同的染色方案数为ll=1/|G|*(m^c(a1)+...m^c(ai)+...m^c(an)) c表示ai置换的循环节数量当着色方案有具体限制条件时一般用Burnside引理而不用Polya定理

Polya定理的母函数形式

设N是n个对象的集合,G是N上的置换群,G={P1,P2,...,Pg},用m种颜色b1,b2,...bm对n个对象进行着色设Ck(P)为置换P中k循环,令Sk=b1^k+b2^k+...+bm^k,k=1,2,...n(Sk为每种颜色允许出现k次),则具体着色方案数的多项式为:P=1/|G|*∑(Pi∈G)(S1^c1(Pi)*S2^c2(Pi)*...*Sn^cn(Pi))展开并合并同类项之后,b1^i1*b2^i2*...*bm^im前的系数即为具体着色方案数。

常用多面体的置换群

正四面体(顶点数:4,棱数:6)

1、以顶点为目标的转动群:以顶点—面心为轴:(1)1  (3)1  8个置换群;以棱中—棱中为轴:(2)2  3个置换群;不动:(1)4  1个置换群;2、以棱为目标的转动群:以顶点—面心为轴:(3)2  8个置换群;以棱中—棱中为轴:(1)2  (2)2  3个置换群;不动:(1)6  1个置换群;3、以面为目标的转动群:以顶点—面心为轴:(1)1  (3)1  8个置换群;以棱中—棱中为轴:(2)2  3个置换群;不动:(1)4 1个置换群;

正六面体(顶点数:8,棱数:12)

1、以顶点为目标的转动群:以顶点—顶点为轴:(1)2  (3)2  8个置换群;以棱中—棱中为轴:(2)4  6个置换群;以面心—面心为轴:(4)2  6个置换群;(2)4  3个置换群;不动:(1)8  1个置换群;2、以棱为目标的转动群:以顶点—顶点为轴:(3)4  8个置换群;以棱中—棱中为轴:(1)2  (2)5  6个置换群;以面心—面心为轴:(4)3  6个置换群;(2)6  3个置换群;不动:(1)12  1个置换群;3、以面为目标的转动群:以顶点—顶点为轴:(3)2  8个置换群;以棱中—棱中为轴:(2)3  6个置换群;以面心—面心为轴:(1)2  (4)1  6个置换群;(1)2  (2)2  3个置换群;不动:(1)6  1个置换群;

正八面体(顶点数:6,棱数:12)

1、以顶点为目标的转动群:以顶点—

这篇关于组合数学常用内容——Polya定理+Burnside引理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/884157

相关文章

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Java如何将文件内容转换为MD5哈希值

《Java如何将文件内容转换为MD5哈希值》:本文主要介绍Java如何将文件内容转换为MD5哈希值的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java文件内容转换为MD5哈希值一个完整的Java示例代码代码解释注意事项总结Java文件内容转换为MD5

Spring Boot 常用注解整理(最全收藏版)

《SpringBoot常用注解整理(最全收藏版)》本文系统整理了常用的Spring/SpringBoot注解,按照功能分类进行介绍,每个注解都会涵盖其含义、提供来源、应用场景以及代码示例,帮助开发... 目录Spring & Spring Boot 常用注解整理一、Spring Boot 核心注解二、Spr

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

Java中的内部类和常用类用法解读

《Java中的内部类和常用类用法解读》:本文主要介绍Java中的内部类和常用类用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录内部类和常用类内部类成员内部类静态内部类局部内部类匿名内部类常用类Object类包装类String类StringBuffer和Stri

MySQL连接池(Pool)常用方法详解

《MySQL连接池(Pool)常用方法详解》本文详细介绍了MySQL连接池的常用方法,包括创建连接池、核心方法连接对象的方法、连接池管理方法以及事务处理,同时,还提供了最佳实践和性能提示,帮助开发者构... 目录mysql 连接池 (Pool) 常用方法详解1. 创建连接池2. 核心方法2.1 pool.q

Spring Boot 常用注解详解与使用最佳实践建议

《SpringBoot常用注解详解与使用最佳实践建议》:本文主要介绍SpringBoot常用注解详解与使用最佳实践建议,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录一、核心启动注解1. @SpringBootApplication2. @EnableAutoConfi

SQL常用操作精华之复制表、跨库查询、删除重复数据

《SQL常用操作精华之复制表、跨库查询、删除重复数据》:本文主要介绍SQL常用操作精华之复制表、跨库查询、删除重复数据,这些SQL操作涵盖了数据库开发中最常用的技术点,包括表操作、数据查询、数据管... 目录SQL常用操作精华总结表结构与数据操作高级查询技巧SQL常用操作精华总结表结构与数据操作复制表结

全解析CSS Grid 的 auto-fill 和 auto-fit 内容自适应

《全解析CSSGrid的auto-fill和auto-fit内容自适应》:本文主要介绍了全解析CSSGrid的auto-fill和auto-fit内容自适应的相关资料,详细内容请阅读本文,希望能对你有所帮助... css  Grid 的 auto-fill 和 auto-fit/* 父元素 */.gri