PDF《应用组合数学》

2 2

2 2

2 2

2 2

4 4

4 4

2 2

2 2

1 2

2 1

1 2

2 1

1 4

2 2

1 4

4 1

2 2

2 2

2 2 )] ( ) (

2 ) (

3 ) (

2 ) [(

8 1 ] [

8 1 ) ( bry y br ry b y r y b r b ry by y r br y b r b y r b y r b y r b y r b y r b y r b w w w w w w w w w w S inv + + + + + + + + + + + + + + = + + + + + + + + + + + + + = + + + + + + + = 令w(1)=w(2)=b,w(3)=r,w(4)=y,根据一般形式的Polya 定理, 可知能做成2种项链.实际上不需要完全展开inv(S) 例题4 [例4]用六种颜色给立方体的六个面着色,每面颜色不同,并 且当一个着色的立方体经转动可得到另一个时,就认为二 者相同.问有多少种着色方案?

30 24 6! 6! ) ( ) (

24 ] ) (

8 ) (

6 ) ( ) (

3 ) ( ) (

6 ) [(

24 ]

8 6

3 6 [ ) (

6 5

4 3

2 1

6 6

5 4

3 2

1 6

6 5

4 3

2 1

6 5

4 3

2 1

2 3

6 3

5 3

4 3

3 3

2 3

1 3

2 6

2 5

2 4

2 3

2 2

2 1

2 2

6 2

5 2

4 2

3 2

2 2

1 2

6 5

4 3

2 1

4 6

4 5

4 4

4 3

4 2

4 1

2 6

5 4

3 2

1 6

6 5

4 3

2 1

2 3

3 2

2 2

2 1

1 4

2 1

6 1 = + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + = + + + + = 是 ,故不同的着色方案数 的系数为 后 展开 多项式公式, 的展开式中出现.根据 的系数,它只能在 问题是要求 解: x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x w w w w w w w S inv 图的计数 问题:求具有n个顶点和m条边不同构图的数目? [例5] 求4个顶点3条边的不同构图的数目. 4个顶点的图 [例6] 多项式G4(x)给出了4个顶点m条边的图的数目: G4(x)=1+x+2x2+3x3+2x4+x5+x6 解:1)对完全图Kn的C(n,2)条边着黑白两色,权重 分别为x和1,这样一个着色方案得到一个黑边图. 2)只有顶点的所有置换能够得到同构的图,因此 要从顶点的置换群Sn诱导出边的置换群的子群.3) S4的置换分为5类24个,对每一类进行考察.4)运 用一般形式的Pólya定理求解. 4个顶点的图(续) 24G4(x)= 1(1+x)6 14203040?

162030405060 +6(1+x)2(1+x2)2 12213040?

122230405060 +3(1+x)2(1+x2)2 10223040?

122230405060 +8 (1+x3)2 12203140?

102032405060 +6(1+x2)(1+x4) 10203041?

102130415060 n个顶点的图 种情况. 分 诱导出的边的置换 由 同类型的置换. 个和 ! ! ! ! 中有 则 的类型是 假设顶点置换

4 p g g

2 1

2 1 g

2 1

2 1

3 2

1 n n c c c n c c c n c c c n S n L L L 情况1 若边e的两个顶点都在g的同一个x-轮换之中,x是一个奇 数,x=2k+1,则e出现在p的一个x-轮换里,且由g的这个 x-轮换诱导出k个p的x-轮换.证明这个结论时要注意到g 的x个元素形成 条边. 例如对于g的5-轮换(1,2,3,4,5)来说,边12被p的5-轮换 (12,23,34,45,15)所置换.g的这5个元素形成10条边,p包 含两个5-轮换,另一个是(13,24,35,14,25). L

5 3

1 2

5 1

3 0

1 1

1 2 c c c kc x w w w x w k x x ,可得乘积 因此,对于所有的奇数 . ,包括一个因子 对于每个奇数 ≥ + = )

1 2k ( k

2 ) 2k )(

1 2k ( + = + 情况2 若边e的两个顶点都在g的同一个x-轮换之中,x是一个偶 数,x=2k,则e或者出现在p的一个x-轮换里,或者出现在 p的一个k-轮换里,且由g的这个x-轮换诱导出k-1个p的x- 轮换和1个p的k-轮换.证明这个结论时要注意到p的k-轮 换包含所有形式是vivi+k的边. 例如对于g的6-轮换(1,2,3,4,5,6)来说,边12被p的6-轮换 (12,23,34,45,56,16)所置换,边14被p的3-轮换(14,25,36) 所置换. g的这6个元素形成15条边,p包含两个6-轮换和 一个3-轮换,另一个6轮换是(13,24,35,46,15,26). L