組合數(shù)學(xué)中比較困難的波利亞定理應(yīng)用最大的障礙是不理解

1、組合數(shù)學(xué)中比較困難的波利亞定理應(yīng)用最大的障礙是不理解所要解決的立體形狀的具體信息。下文詳細(xì)列舉了所有常見的形狀和其詳盡的信息。from:/nickms/article/details/6076341正四面體：階12，頂點(diǎn)4個，面4個，棱6條，均為等邊三角形轉(zhuǎn)動群 頂點(diǎn)面棱個數(shù)不動(1)4(1)4(1)61頂點(diǎn)-面心 120度(1)(3)(1)(3)(3)28棱心-棱心 180度(2)2(2)2(1)2(2)23正六面體：階24，頂點(diǎn)8個，面6個，棱12條，均為正方形轉(zhuǎn)動群 頂點(diǎn)面棱個數(shù)不動(1)8(1)6(1)121面心-面心, 90度(4)2(1)2(4

2、)(4)36面心-面心，180度(2)4(1)2(2)2(2)63棱心-棱心，180度(2)4(2)3(1)2(2)56空間對角線120度(3)2(1)2(3)2(3)48正八面體：階24，頂點(diǎn)6個，面8個，棱12條，均為等邊三角形轉(zhuǎn)動群 頂點(diǎn)面棱個數(shù)不動(1)6(1)8(1)121頂點(diǎn)-頂點(diǎn) 90度(1)2(4)(4)2(4)36頂點(diǎn)-頂點(diǎn) 180度(1)2(2)2(2)4(2)63棱心-棱心 180度(2)3(2)4(1)2(2)56面心-面心 120度(3)2(3)2(1)2(3)48正十二面體：階60 ，頂點(diǎn)20個，面12個，棱30條，均為正五邊形轉(zhuǎn)動群 頂點(diǎn)面棱個數(shù)不動(1)20(1

3、)12(1)301面心-面心72,144度(5)4(1)2(5)2(5)6 24棱心-棱心180度(2)10(2)6(1)2(2)1415頂點(diǎn)-頂點(diǎn)120度(1)2(3)6(3)4(3)1020正二十面體：階60 ，頂點(diǎn)12個，面20個，棱30條，均為等邊三角形轉(zhuǎn)動群 頂點(diǎn)面棱個數(shù)不動(1)12(1)20 (1)301頂點(diǎn)-頂點(diǎn)72,144度(1)2(5)2(5)4(5)624棱心-棱心180度(2)6(2)10(1)2(2)1415面心-面心120度(3)4(1)2(3)6(3)1020足球：階60，頂點(diǎn)60個，面32個，棱數(shù)90條，20個正六邊形，12個正五邊形轉(zhuǎn)動群頂點(diǎn)面棱個數(shù)不動(1)

4、60(1)32(1)901五邊形面心-五邊形面心72,144度(5)12(1)2(5)6(5)1824六邊形面心六邊形面心120度(3)20(1)2(3)10(3)3020正六邊形棱中-棱180度（這種棱有30條）(2)30(2)16(1)2(2)4415類足球：階24，頂點(diǎn)24個，面14個，棱數(shù)36條，8個正六邊形，6個正方形(就是那種把正八面體的每個角切掉等大的一塊得出的形狀）轉(zhuǎn)動群頂點(diǎn)面棱個數(shù)不動(1)24(1)14(1)361正方形面心-正方形面心90度(4)6(1)2(4)3(4)96正方形面心-正方形面心180度(2)12(1)2(2)6(2)183六邊形面心六邊形面心120度(3

5、)8(1)2(3)4(3)128正六邊形棱中-棱180度（這種棱有12條）(2)12(2)7(1)2(2)176-我通篇的理論都是專注于如何寫出置換群的表格形式，比如正二十面體的“棱中對棱中翻轉(zhuǎn)”的置換形式是(1)2 (2)14，一共有15個這樣的置換。我認(rèn)為只要能夠輕松寫出任意正多面體的任意一個轉(zhuǎn)法的置換形式，大多數(shù)染色題目基本可以迎刃而解。需要注意的就是火柴問題，情況比染色復(fù)雜，可能需要額外做題，這個暫且不論。from：/share/227521810/4588940865首先，給出一個重要的概念底座。底座，是指把多面體的一個頂點(diǎn)（稱為尖頂）放到視

6、角中心，從上往下俯視看到的第一層輪廓。面數(shù)較小的情況下，底座就是俯視圖的最外圍輪廓，但面數(shù)增多時就不一定了?？傊覀冎挥懻撆c尖頂有邊相連的那個底座。底座是原多面體的一個切面。每個底座都擁有中心的尖頂，以及從這個尖頂連結(jié)到底座各頂點(diǎn)的棱，以及底座的側(cè)邊。下面依次來看底座的形狀：（1）正四面體正四面體的底座就是它自己的一個底面，側(cè)邊就是它自己的三條邊。屬于“底座易見類”多面體。（2）正六面體正六面體的底座是三條虛線的那三個頂點(diǎn)組成的正三角形，它的側(cè)邊實(shí)際上是三個等腰直角三角形。理解這兩點(diǎn)需要一些想象能力。屬于“底座難見類”多面體。（3）正八面體正八面體的底座是圖中的正方形，側(cè)邊是自己的四條邊。屬

7、于“底座易見類”多面體。（4）正十二面體正十二面體由一堆五邊形組成，它的底座實(shí)際上也是一個正三角形，與正六面體不同的是，它的側(cè)邊實(shí)際上是切割五邊形得到的三角形，這個三角形的頂角是120度?？吹竭@一點(diǎn)也需要一些想象能力，它屬于“底座難見類”多面體。（5）正二十面體正二十面體看起來復(fù)雜，其實(shí)底座很容易看出，就是一個正五邊形，并且由一個尖頂連接著各個頂點(diǎn)，像一個宮殿的頂部。底座的側(cè)邊就是正二十面體自己的五個側(cè)面，都是正三角形。它屬于“底座易見類”多面體。本質(zhì)上講，對一個多面體的旋轉(zhuǎn)，就是對它的各個底座的旋轉(zhuǎn)?？梢哉f，只要腦子里能想出底座的形狀，你就可以說“完全”了解了對應(yīng)的那個正多面體，即使你根本無

8、法畫出或想象出那個多面體的整體形狀。為什么這么說呢，因?yàn)檎嗝骟w有一個很好的性質(zhì)，就是對稱性。這個對稱性在我們討論旋轉(zhuǎn)置換的時候，在做題的時候，對應(yīng)的物理意義就是兩個字：“信心”。你永遠(yuǎn)可以堅(jiān)信，當(dāng)這個底座發(fā)生旋轉(zhuǎn)的時候，其他的點(diǎn)、面、棱也在按照相同的規(guī)律進(jìn)行著旋轉(zhuǎn)。老師說過，旋轉(zhuǎn)置換可以按照不同的對稱軸分為四大類情況：不動、點(diǎn)對點(diǎn)、面對面、棱對棱。對底座易見類多面體來說，點(diǎn)對點(diǎn)的旋轉(zhuǎn)最好理解，比如正四面體；對底座難見類多面體來說，面對面的旋轉(zhuǎn)最好理解，如正六面體。下面分別討論點(diǎn)對點(diǎn)、面對面、棱對棱旋轉(zhuǎn)。（1）點(diǎn)對點(diǎn)了解底座之后，對稱軸是點(diǎn)對點(diǎn)的情況就相當(dāng)于在底座上印了一條高，繞著這條高來轉(zhuǎn)。

9、你會突然發(fā)現(xiàn)這想起來變得異常簡單了，是不是？因?yàn)?，點(diǎn)對點(diǎn)旋轉(zhuǎn)有幾種情況，完全取決于底座是幾邊形。如果是奇數(shù)邊形，就直接有n-1種轉(zhuǎn)法，如果是偶數(shù)邊形，需要考慮是90度還是180度，因?yàn)檫@兩種情況下循環(huán)個數(shù)不一樣。接下來的問題是如何寫出具體的形如(1)2 (3)2 之類的置換形式，而且需要針對點(diǎn)染色、面染色、棱染色分別討論。這就是本文的精髓所在了，根據(jù)對稱性，我總結(jié)出一個置換大定理：: 任何情況下，有且僅有對稱軸上的兩個對象是不動的，其它的都動。比如，點(diǎn)對點(diǎn)旋轉(zhuǎn)時，只有兩個不動點(diǎn)；軸對軸旋轉(zhuǎn)時，只有兩個不動軸；面對面旋轉(zhuǎn)時，只有兩個不動面。寫成置換形式就是(1)2。: 在不區(qū)分90度還是180度

10、的情況下，有m種旋轉(zhuǎn)方式時，點(diǎn)染色、面染色、棱染色均可以寫成 (m+1)k的形式。這里的k需要根據(jù)不同多面體的點(diǎn)、面、棱數(shù)決定，只要滿足(m+1)乘以k等于那個數(shù)目即可。因此，對點(diǎn)對點(diǎn)軸旋轉(zhuǎn)，我們可以列表如下：（正四面體實(shí)際上是點(diǎn)對面，單獨(dú)寫 ）旋轉(zhuǎn)方向種類 點(diǎn)染色 面染色 棱染色正六面體： 2 (1)2 (3)2 (3)2 (3)4正十二面體： 2 (1)2 (3)6 (3)4 (3)10正二十面體： 4 (1)2 (5)2 (5)4 (5)6即使是需要區(qū)分90度還是180度的情況，對點(diǎn)染色、面染色、棱染色來說，每個分組的大小也是一樣的：旋轉(zhuǎn)方向種類 點(diǎn)染色 面染色 棱染色正八面體：90度

11、2 (1)2 (4)1 (4)2 (4)3180度 1 (1)2 (2)2 (2)4 (2)6（2）面對面面對面的情況更簡單。當(dāng)點(diǎn)對點(diǎn)的時候，你還得考慮底座是什么樣子，才能知道旋轉(zhuǎn)方向種類m等于幾。而面對面時，你只需要知道多面體的每個面是幾邊形就行了，因?yàn)樵诓恍枰獏^(qū)分90度還是180度的情況下，旋轉(zhuǎn)種類m就等于邊數(shù)減一。（五邊形就是4種，三邊形就是2種，49邊形就是48種）至于多面體長什么樣子，完全沒必要知道，因?yàn)閷ΨQ性給了我們使用“置換大定理”的充分信心。旋轉(zhuǎn)種類 點(diǎn)染色 面染色 棱染色正八面體： 2 (3)2 (1)2 (3)2 (3)4 （面為三角形）正十二面體： 4 (5)4 (1)2

12、 (5)2 (5)6 （面為五邊形）正二十面體： 2 (3)4 (1)2 (3)6 (3)10 （面為三角形）這是不是很簡單啊。即使是需要區(qū)分90度還是180度的情況，對點(diǎn)染色、面染色、棱染色來說，每個分組的大小也是一樣的：旋轉(zhuǎn)方向種類 點(diǎn)染色 面染色 棱染色正六面體：90度 2 (4)2 (1)2 (4)1 (4)3180度 1 (2)4 (1)2 (2)2 (2)6（3）棱對棱棱對棱是最難想象的一種，但在我的理論中是最簡單的一種，因?yàn)楦鶕?jù)對稱性給我們充分信心，棱對棱只有180度這一種情況，因此對所有多面體來說都只有1種旋轉(zhuǎn)方向。根據(jù)置換大定理，所有多面體的棱對棱旋轉(zhuǎn)都可以寫成 (2)x 的

13、形式，只需要根據(jù)棱的數(shù)量更改x就可以了。當(dāng)然，別忘了棱染色時有兩個不動點(diǎn)(1)2。點(diǎn)染色 面染色 棱染色正四面體： (2)2 (2)2 (1)2 (2)2正六面體： (2)4 (2)3 (1)2 (2)5正八面體： (2)3 (2)4 (1)2 (2)5正十二面體：(2)10 (2)6 (1)2 (2)14正二十面體：(2)6 (2)10 (1)2 (2)14是不是已經(jīng)感覺很弱智了？沒錯，這就是對稱性和置換大定理給我們帶來的的強(qiáng)大信心。如果你能夠自己寫出上面的置換形式，這些多面體對你來說就沒啥新意可言了。盡管你可能都畫不出來這個多面體。另外，還有一個小技巧，就是在檢查置換種類總個數(shù)的時候，應(yīng)該

14、等于面數(shù)乘以每個面的邊數(shù)。按照 不動+點(diǎn)點(diǎn)+面面+棱棱 的順序?qū)懗龇N類個數(shù)之和，如下表：正四面體： 1+8+3 = 12種 = 4x3 （三角形）正六面體： 1+8+(6+3)+6 = 24種 = 6x4 （四邊形）正八面體： 1+(6+3)+6+8 = 24種 = 8x3 （三角形）正十二面體：1+20+24+15 = 60種 = 12x5 （五邊形）正二十面體：1+24+15+20= 60種 = 20x3 （三角形）關(guān)于足球：單拉出足球來是因?yàn)樽闱虿粷M足對稱性，它既有12個五邊形又有20個六邊形，比較復(fù)雜。但其實(shí)，它也沒有想象中那么復(fù)雜。先看一下圖像：可以看出，足球在本質(zhì)上是由五邊形組成的

15、，它其實(shí)就是12個不相交的五邊形組成的多面體，六邊形實(shí)際上相當(dāng)于是為了封閉而填充進(jìn)來的面。下面按照置換大定理的思路討論下足球：（1）點(diǎn)對點(diǎn)可以看到，點(diǎn)對點(diǎn)的連線在足球上特別不對稱，因?yàn)榈鬃膫?cè)邊有一個是黑的（五邊形）兩個是白的（六邊形）。這怎么旋轉(zhuǎn)呢？沒法旋轉(zhuǎn)。因此，點(diǎn)對點(diǎn)軸旋轉(zhuǎn)在足球上不存在。（2）面對面這要分每個面是五邊形還是六邊形了。根據(jù)置換大定理，五邊形就是五個一組（m=5-1，5-1+1=5），六邊形似乎就是六個一組（m=6-1，6-1+1=6）。但可惜的是，六邊形中有三條邊在五邊形上，三條邊不在五邊形上，要求置換時必須滿足三條邊內(nèi)部互換。因此就只有兩種旋轉(zhuǎn)方式了，所以m=2，2+1

16、=3個一組。點(diǎn)染色 面染色 棱染色五邊形： (5)12 (1)2 (5)6 (5)18六邊形： (3)20 (1)2 (3)10 (3)30（3）棱對棱棱對棱雖然簡單，但要注意的是只有不在五邊形上的棱才具有對稱性，否則轉(zhuǎn)不了。因此90條棱中，只有90-12x5 = 30條棱可以轉(zhuǎn)，也就是15個棱對棱軸。由于只有180度的旋轉(zhuǎn)，根據(jù)置換大定理，仍然可以寫成(2)x 的形式。點(diǎn)染色 面染色 棱染色足球： (2)30 (2)16 (1)2 (2)44同樣，可以用上面提到的小技巧檢查置換種類總個數(shù)，即應(yīng)該等于面數(shù)乘以每個面的邊數(shù)：1+24+20+15 = 60種 = 12x5 （五邊形）這也說明，足球

17、在本質(zhì)上是由五邊形組成的。from：/pc/pccon.php?id=10001420&nid=286283經(jīng)常會有這樣的題目，問有30根紅火柴，30根綠火柴，30根蘭火柴（火柴是有方向性的，一頭是易燃物質(zhì)，一頭不是）搭一個足球，詢問有多少種搭法。直接把這種題套用polya定理是比較別扭的。那么怎么才能理解這類題的本質(zhì)呢？這要從burnside引理說起。一般來講，burnside引理的形式是（x+x+x+x）/|g|，其中|g|為轉(zhuǎn)動群的階數(shù)。而每一個x，則對應(yīng)某在一種置換中，置換前和置換后完全重合的不同方案的個數(shù)。這句話很拗口，但請注意兩點(diǎn)，第一是“

18、置換前和置換后必須重合”，第二是“能夠表現(xiàn)出這樣特征的不同方案的數(shù)目”。用循環(huán)轉(zhuǎn)動群來表示的話就是，對于每一個置換都可以得到類似于(n)(nn)(nnnn)(n) 的置換群，burnside引理的x要的是其中有多少個括號，其內(nèi)部只包含一個n。（注意，這里的n表示一種著色方案，而不是方案數(shù)，請仔細(xì)區(qū)分方案和方案數(shù)）。舉個實(shí)例的話，例如對于一個田字格進(jìn)行黑白二著色。對于全黑和全白的著色方案，不管是不動，轉(zhuǎn)90度，180度還是270度都和不轉(zhuǎn)制前重合 。于是它們在每一個旋轉(zhuǎn)里都會被計(jì)數(shù)。而對于那種左上和右下是黑，右上和左下是白的著色方案，只有在180度的時候才與不轉(zhuǎn)之前重合。也只有在180度的旋轉(zhuǎn)中

19、會被計(jì)數(shù)。但是burnside引理的通用做法是遍歷所有的方案，并尋找那些置換前后重合的方案，對其計(jì)數(shù)。但這太沒有效率了，對一個正12面體進(jìn)行3著色，不考慮重復(fù)的話，方案數(shù)達(dá)到了312次方。這是不可能一一遍歷的。實(shí)際上，我們只關(guān)心有多少個這樣的方案，既不想遍歷，也不想知道符合條件的方案是什么樣的。我們只想計(jì)數(shù)而已。這就是polya定理出現(xiàn)的原因。它是針對“對稱多面體”（包括正多面體和足球之類的凸多面體）的著色問題來計(jì)算burnside引理中的每個x是多少的。其形式是cmy,其中c是當(dāng)前旋轉(zhuǎn)有多少個，如果要轉(zhuǎn)正負(fù)90度，并且這樣的軸有4個的話，那么c就是8。m是著色數(shù)。y是循環(huán)群的段數(shù)。如果對一個

20、正方體二著色，面心-面心旋轉(zhuǎn)180度的循環(huán)群是（1）2（2）2的話，那么my就是24。對正多面體著色一大特點(diǎn)是著色沒有方向性，因此旋轉(zhuǎn)前一個面是紅色，而旋轉(zhuǎn)之后這個面還是紅色，就說這個面在置換前后重合。但如果面上是肖像就不一樣了，就算旋轉(zhuǎn)前后一個面都是肖像，還得考慮這個肖像在旋轉(zhuǎn)前后方向是不是一致。只有一致才能說是重合。因此，對于這一類型的題，有如下的步驟：1. 搞清楚要算的多面體有哪些可以旋轉(zhuǎn)的方案2. 對于某一種旋轉(zhuǎn)的方案，是否可能存在旋轉(zhuǎn)前后重合的現(xiàn)象。如果沒有，就不用繼續(xù)了，這一旋轉(zhuǎn)對應(yīng)的x值是0。還原到置換群的表示法，就意味著沒有一個表示循環(huán)的括號里僅僅有一個元素，如(nnnn)(nnnn)(nn)。例如對于有方向的火柴，如果進(jìn)行棱心-棱心180度旋轉(zhuǎn)，就絕對不可能有重合的情況。一個火柴頭轉(zhuǎn)到尾部無論如何也不會重合。同理，對于肖像（非對稱的那種），進(jìn)行面心-面心的旋轉(zhuǎn)，也是不可能重合的。這時方案數(shù)一律為0。3. 如果可能存在重合的方案，就去設(shè)想那種方案。并用排列組合把那個數(shù)算出來。例如，針對足球六邊形面心-面心旋轉(zhuǎn)120度或者240度。如果有30根紅火柴，30根綠火柴，30根蘭火柴的話，必然首先