德布莱英定理

德布莱英定理(de Bruijn's theorem)是波利亚定理的推广，哈拉里(F.Harary)推广了德布莱英定理1。

基本介绍若两置换群A和B分别作用于两有限集X={x1，x2，…，xn}和Y={y1，y2，…ym}，则可定义幂群BA={(α，β)|α∈A，β∈B}对函数集YX={f|f：X→Y}的作用为(α，β)f(x)=β(f(αx))。若有(α，β)f=f′，则称f，f′是等价的，记为f~f′，~为一等价关系。于是，YX被分为若干等价类之并，这些等价类称为函数式样或函数轨道，德布莱英定理断言：函数式样的个数等于1

式中群A的循环指标为

其中β的型为。

德布莱英定理的推广哈拉里(F.Harary)推广了德布莱英定理1。

设Y为可数集，Y至少含2元，定义权函数w：Y→R，R⊂N0，N0为非负整数集；又定义函数f的权

设k∈R，Y的子集Yk={y|y∈Y，w(y)=k}，且|Yk|是有限的，|Yk|=Ck。若B(Yi)={β(y)|β∈B，y∈Yi}，则函数集YX被幂群BA作用所分出的各个式样中的函数有等权的充分必要条件是B(Yi)=Yi，i∈R，若条件B(Yi)=Yi，满足i∈R，则可定义式样F的权为w(F)=w(f)，其中f∈F，记β=βi，式中βi(y)=β(y)，这里y∈Yi，若权为k的式样为Ck个，则式样依权展开的生成函数为

于是

式中Z(A;s1，s2，…，sn)为A的循环指标，

βi的型为。

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学