PDF《应用组合数学》

第12讲Pólya定理 张坤龙 zhangkl@tju.

edu.cn 应用组合数学 目录 ? 特殊形式的Pólya定理 ? 一般形式的Pólya定理 ? 图的计数 特殊形式的Pólya定理 [定理1] 设G是n个对象的一个置换群,用m种颜色涂染这n个对 象,则不同的染色方案数为 其中G={g1, g2, …, g|G|},c(g)表示置换g中轮换的个数. 证明:对象集D ={1,2,…,n},颜色集R={1,2,…,m},着色集S有mn个元素.D上的置换群G诱导出S上的一个置换群P,|P|=|G|. 为了应用Burnside引理,要求出P中的每个置换包含的1-轮换 个数. 假设g诱导出p,如果给g的每一个轮换着相同的颜色,那么 这个着色在p中将保持不动.例如g=(1

2 3)(4

5 6)(7),着色 红1,红2,红3,蓝4,蓝5,蓝6,绿7 在p中将保持不动.因此p中1-轮换的个数是mc(g). ] [ | |

1 ) ( ) ( ) ( | |

2 1 G g c g c g c m m m G l + + + = L 例题1 [例1] 一正方形均分成4格,用两种颜色着色,能得到多少种 不同的图像?如果一个图像旋转后与另一个图象吻合,则 两个图象算相同的. 解:运动群G={g1, g2, g3, g4} g1=(1)(2)(3)(4) c(g1)=4 g2=(1

2 3 4) c(g2)=1 g3=(1 3)(2 4) c(g3)=2 g4=(1

4 3 2) c(g4)=1 根据Pólya定理

2 1

3 4

6 ]

2 2

2 2 [

4 1

1 2

1 4 = + + + = l 例题2 [例2] 求用三种颜色对一个等边三角形顶点着色的方法数.如 果一种着色可由另一种着色旋转产生,或者如果一种着色 是另一种着色的翻转,则认为两种着色是相同的. 解:运动群G正好是S3 g1=(1)(2)(3) c(g1)=3 g2=(1

2 3) c(g2)=1 g3=(1

3 2) c(g3)=1 g4=(1)(2 3) c(g4)=2 g5=(2)(1 3) c(g5)=2 g6=(3)(1 2) c(g6)=2

10 ]

3 3

3 2

3 [

6 1

2 1

3 = ? + ? + = l

2 3

1 2

3 1

132030 102031

112130 一般形式的Pólya定理 [定理2] 用m种颜色涂染n个对象,设G是着色的一个置 换群,则所有G导出的轨道的清单为 cs( gr)表示置换gr中s-轮换的个数. n n n n g c n g c g c g c n g c g c g c n g c g c m w w w w m w w w w m w w w w w w w w w w w w w G G n G G n n ) ( )

2 ( )

1 ( , , ) ( )

2 ( )

1 ( ), ( )

2 ( )

1 ( ] [ | |

1 2

2 2

2 1 ) ( ) (

2 ) (

1 ) ( ) (

2 ) (

1 ) ( ) (

2 ) (

1 | | | |

2 | |

1 2

2 2

2 1

1 1

2 1

1 + + + = + + + = + + + = + + + L L L L L L L L 其中 证明:根据Burnside引理的权重形式,所有G导出的轨道权重 的总和为 其中w'

(g)是g保持不动的着色的权重和.设g的轮换是D1, D2, …, Dk,则g保持不动的着色的权重和为 w'

(g)的展开式中每一项具有形式 ws的个数恰好是s-轮换的数目,即cs(g) )] ( '

) ( '

) ( '

[ | |

1 | |

2 1 G g w g w g w G + + + L ] ) ( )

2 ( )

1 ( [ ] ) ( )

2 ( )

1 ( [ ] ) ( )

2 ( )

1 ( [ ) ( '

| | | | | | | | | | | | | | | | | |

2 2

2 1

1 1 k k k D D D D D D D D D m w w w m w w w m w w w g w + + + * * + + + * + + + = L L L L s s s s m w w w w ) ( )

2 ( )

1 ( + + + = L 例题3 [例3] 用4颗珠子(两颗蓝色、一颗红色和一颗黄色) 能做成多少种项链? 解:g1=(1)(2)(3)(4) =14203040 g2=(1

2 3 4) =10203041 g3=(1 3)(2 4) =10223040 g4=(1

4 3 2) =10203041 g5=(1)(2 4)(3) =12213040 g6=(1 3)(2)(4) =12213040 g7=(1 2)(3 4) =10223040 g8=(1 4)(2 3) =10223040

1 4

3 2

21 ]

3 2

3 3

3 2

3 [

8 1 ]

3 3

3 3

3 3

3 3 [

8 1

3 2

1 4

2 2

3 3

1 2

1 4 = ? + ? + ? + = + + + + + + + = l 根据特殊形式的Pólya定理

2 2

2 2

2 2

2 2

2 3

3 3

3 3

3 4

4 4