（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式

标签：颜色 Part.10 定理权函数 lya Bruijn 置换群

（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数

写在前面

介绍De Bruijn定理的母函数形式，由此《（组合数学笔记）Pólya计数理论》系列完结。

引入

与Pólya定理的母函数形式的推导类似，首先引入模式清单 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_02$ 的概念，并介绍两个引理。

模式清单

假设：颜色集 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_03$ 上的权函数 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_04$ 在颜色置换群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_05$ 的每条轨道上是常数，即若 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_06$ 是颜色置换群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_07$ 在颜色集 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_08$ 上的一条轨道，则对 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_09$ ，有 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_10$ .

设方案集 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_11$ 关于幂群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_12$ 的模式清单 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_13$ ，并假定轨道集
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_14$
那么有
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_15$

引理1

设 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 为颜色集， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_17$ 是染色对象集， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_18$ 是定义在 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 上的权函数，且 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_18$ 在群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_21$ 的每条轨道上是常数。对于给定的 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_22$ ，令 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_23$ , $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_24$ 表示 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_25$ 的所有不动点的权和，则有
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_26$

引理2

对于 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_27$ , $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_28$ 表示置换 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_25$ 不动点的集合， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_24$ 表示 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_25$ 的所有不动点的权和，则有
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_32$
其中
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_33$
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_34$ 是用 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_35$ 的所有 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_36$ 循环中的颜色循环顺序地染色 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_37$ 的一个 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_38$ 循环中的对象由此得到的所有染色方案的权和，其中 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_39$ .

由上述引理1，2可以得到下面的定理。

母函数型的De Bruijn定理

设 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_40$ 和 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_41$ 分别是 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_42$ 元对象集 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_17$ 和 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_44$ 元颜色集 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 上的置换群， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_18$ 是定义在 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 上的权函数，且 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_18$ 在群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_21$ 的每条轨道上是常数，则
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_50$
其中 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_51$ 是置换群 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_52$ 的循环指数， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_53$ .

定理的特殊情况

（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_54

（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_55

此即在没有任何群的作用下 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_42$ 元集到 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_44$ 元集的所有映射方案的枚举，亦即 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_42$ 个不同的球放入 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_44$ 个不同的盒子且允许空盒的放入方案数的枚举。

例题

将3个白球和1个黑球放入2个方形盒子和1个圆形盒子且允许空盒的模式清单(假定3个白球、2个方形盒子均不可区分)。

分析

令 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_60$ 为对象集， $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_61$ 为颜色集。显然 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_17$ 与 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 上的置换群分别为 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_64$ .即
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_65$
所以
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_66$
定义 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_权函数_16$ 上的权函数为
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_68$
显然满足权函数在 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_21$ 的每一条轨道上是常数。

由定义 $（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_53$ , 得到
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_母函数_71$
由此得到
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_72$
于是根据母函数型的De Bruijn定理，有
$（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式_置换群_73$

标签：颜色,Part.10,定理,权函数,lya,Bruijn,置换群
From： https://blog.51cto.com/u_15366127/5984024

（组合数学笔记）Pólya计数理论_Part.10_Pólya定理的推广——De Bruijn定理的母函数形式

写在前面

引入

模式清单

引理1

引理2

母函数型的De Bruijn定理

定理的特殊情况

例题

分析

相关文章

赞助商

阅读排行