[科普中國]-德布萊英定理

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

基本介紹若兩置換群A和B分別作用于兩有限集X={x1，x2，…，xn}和Y={y1，y2，…ym}，則可定義冪群BA={(α，β)|α∈A，β∈B}對函數(shù)集YX={f|f：X→Y}的作用為(α，β)f(x)=β(f(αx))。若有(α，β)f=f′，則稱f，f′是等價的，記為f~f′，~為一等價關系。于是，YX被分為若干等價類之并，這些等價類稱為函數(shù)式樣或函數(shù)軌道，德布萊英定理斷言：函數(shù)式樣的個數(shù)等于1

式中群A的循環(huán)指標為

其中β的型為。

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

設Y為可數(shù)集，Y至少含2元，定義權函數(shù)w：Y→R，R?N0，N0為非負整數(shù)集；又定義函數(shù)f的權

設k∈R，Y的子集Yk={y|y∈Y，w(y)=k}，且|Yk|是有限的，|Yk|=Ck。若B(Yi)={β(y)|β∈B，y∈Yi}，則函數(shù)集YX被冪群BA作用所分出的各個式樣中的函數(shù)有等權的充分必要條件是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個，則式樣依權展開的生成函數(shù)為

于是

式中Z(A;s1，s2，…，sn)為A的循環(huán)指標，

βi的型為。

本詞條內(nèi)容貢獻者為:

王海俠 - 副教授 - 南京理工大學