波利亞計數定理 目录 波利亚计数定理 波利亚计数定理的母函数形式 示例 波利亚计数定理与伯恩赛德引理的比较 参考文献 导航菜单

组合数学


组合数学伯恩赛德引理John Howard Redfield群循环指标






目录





  • 1 波利亚计数定理


  • 2 波利亚计数定理的母函数形式


  • 3 示例

    • 3.1 示例1


    • 3.2 示例2

      • 3.2.1 问题描述：


      • 3.2.2 问题解答：




  • 4 波利亚计数定理与伯恩赛德引理的比较


  • 5 参考文献




波利亚计数定理


波利亚计数定理（英语：Pólya enumeration theorem，简称PET）用来研究不同着色方案的计数问题，它是组合数学中的一个重要的计数公式，是伯恩赛德引理的一般化，由乔治·波利亚在1937年的论文[1]中提出并被广泛应用，该结果首先由John Howard Redfield在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换群G，用t种颜色着色的不同方案数为：


l=1|G|∑g∈Gtc(ag)displaystyle l=frac 1sum _gin Gt^c(a_g)

其中 G=a1,a2,...,ag,c(ak)displaystyle G=a_1,a_2,...,a_g,c(a_k) 为置换akdisplaystyle a_k的循环指标（Cycle index）数目。



波利亚计数定理的母函数形式


设对n个对象用m种颜色：b1,b2,⋯,bmdisplaystyle b_1,b_2,cdots ,b_m着色。设


mc(pi)=(b1+b2+⋯+bm)c1(pi)(b12+b22+⋯+bm2)c2(pi)⋯(b1n+b2n+⋯+bmn)cn(pi)displaystyle m^c(p_i)=(b_1+b_2+cdots +b_m)^c_1(p_i)(b_1^2+b_2^2+cdots +b_m^2)^c_2(p_i)cdots (b_1^n+b_2^n+cdots +b_m^n)^c_n(p_i)，其中cj(pi)displaystyle c_j(p_i)表示置换群中第i个置换循环长度为j的个数。


设Sk=(b1k+b2k+⋯+bmk),k=1,2⋯,ndisplaystyle S_k=(b_1^k+b_2^k+cdots +b_m^k),k=1,2cdots ,n，则波利亚计数定理的母函数形式为：


P(G)=1∣G∣∑j=1gΠk=1nSkck(pj)displaystyle P(G)=frac 1mid Gmid sum _j=1^gPi _k=1^nS_k^c_k(p_j)


波利亚计数定理只是给出计数，但没有给出相应的方案，而母函数形式的波利亚计数定理可以给出相应的方案。



示例



示例1


使用两种颜色对正方体的六个面的面染色，不同的染色方案数有：


124(26+6×23+3×24+6×23+8×22) =10displaystyle frac 124left(2^6+6times 2^3+3times 2^4+6times 2^3+8times 2^2right) =10


示例2



问题描述：


甲烷CH4的4个键任意用H(氢),Cl(氯),CH3(甲基), C2H5(乙基) 连接，有多少种方案？ 



问题解答：


甲烷的结构为正四面体，设四面体的四个顶点分别为A、B、C、D，将正四面体的转动群按转动轴分类情况如下：


  1. 不动旋转：A、B、C、D共有一个(1)4循环；

  2. 以顶点与对对面的中心连线为轴，逆时针旋转±120。存在如下置换所对应的旋转：置换(BCD)与置换(BDC)、置换(ACD)与置换(ADC)、置换(ABD)与置换(ADB)，(ABC)及(ACB)，共计8个(1)1(3)1循环。

  3. 以正四面体的3对对边之中点联线为旋转轴旋转180度，(AB)(CD)，(AC)(BD)，(AD)(BC),共有3个(2)2循环

根据波利亚计数定理可得:


112(44+8×42+3×42) =36displaystyle frac 112left(4^4+8times 4^2+3times 4^2right) =36



波利亚计数定理与伯恩赛德引理的比较


  • 波利亚计数定理中的群G是作用在n个对象上的置换群。

  • 伯恩赛德引理中的群G是对这n个对象染色后的方案集合上的置换群。

  • 两个群之间存在一定的联系，群G的元素，相应的在染色方案上也诱导出一个属于G的置换。


参考文献



  1. ^ G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 1937, 68 (1): 145–254. doi:10.1007/BF02546665


-

Popular posts from this blog

名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠－名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局编编

Image
東螺溪清水溪加走寮溪阿里山溪東埔蚋溪獅尾堀清水溪清水溝溪水里溪陳有蘭溪郡坑溪十八重溪那馬嘎班溪松柏坑溪卓棍溪瓠瓢坑溪益則坑溪玉崙溪丹大溪郡大溪巒大溪卡社溪栗栖溪萬大溪萬大北溪萬大南溪霧社溪塔羅灣溪馬赫坡溪萬大發電廠大觀發電廠日月潭第一發電所明潭發電廠...
Read more

Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

Image
Is a conference paper whose proceedings will be published in IEEE Xplore counted as a publication? Prove that NP is closed under karp reduction? Is it important to consider tone, melody, and musical form while writing a song? How is it possible to have an ability score that is less than 3? Can I make popcorn with any corn? Mathematical cryptic clues tikz: show 0 at the axis origin Minkowski space can i play a electric guitar through a bass amp? Why not use SQL instead of GraphQL? How can I prevent hyper evolved versions of regular creatures from wiping out their cousins? How old can references or sources in a thesis be? Do VLANs within a subnet need to have their own subnet for router on a stick? How to add double frame in tcolorbox? How much RAM could one put in a typical 80386 setup? "You are your self first supporter", a more proper way to say it How is the claim "I am in New York only if I am in America" the same as "If I am ...
Read more

Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar

Image
Is the Mordenkainen's Sword spell underpowered? Escaping $ in listings environment Short story about astronauts fertilizing soil with their own bodies No invitation for tourist visa but I want to visit Do regular languages belong to Space(1)? Can I take recommendation from someone I met at a conference? How to name indistinguishable henchmen in a screenplay? Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted? How can I prevent/balance waiting and turtling as a response to cooldown mechanics Can I feed enough spin up electron to a black hole to affect it's angular momentum? Why does BitLocker not use RSA? Is my guitar’s action too high? Does GDPR cover the collection of data by websites that crawl the web and resell user data Trying to enter the Fox's den How to achieve cat-like agility? "Destructive power" carried by a B-52? Should man-made satellites feature an intelligent inverted "cow c...
Read more