组合数学第七章.ppt

* 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 四边形只允许垂直翻转，对四个顶点涂红、蓝两色。 垂直翻转对应的置换为G={(1)(2)(3)(4),(12)(34)} (1)(2)(3)(4):24=16 (12)(34) : 22=4 L=(16+4)/2=10 1 4 2 3 * 计算机科学与技术学院 * Pólya定理的生成函数形式 四边形只允许垂直翻转，对四个顶点涂红、蓝两色。 垂直翻转对应的置换为G={(1)(2)(3)(4),(12)(34)} 给每个括号一种涂色 (1)(2)(3)(4):(r+b)4 (12)(34) : (r2+b2)2 P=((r+b)4+ (r2+b2)2)/2 r=b=1时，Pólya定理的生成函数就变为Pólya定理的计数形式 1 4 2 3 * 计算机科学与技术学院 * Pólya定理的生成函数形式 四边形只允许垂直翻转，对四个顶点涂红、蓝两色。 垂直翻转对应的置换为G={(1)(2)(3)(4),(14)(23)} (1)(2)(3)(4):(r+b)4 (14)(23) : (r2+b2)2 P=((r+b)4+ (r2+b2)2)/2 r=b=1时，Pólya定理的生成函数就变为Pólya定理的计数形式 与置换格式有关，但与置换无关 1 4 2 3 * 计算机科学与技术学院 * 置换的格式与共轭类 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 设b=g=1 恰有2个顶点涂成红色的方案数 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 设r=b=g=1 3种颜色所有涂色的方案数 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 5 O * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 1 2 3 4 5 O * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * Pólya定理的生成函数形式 * 计算机科学与技术学院 * 作业 pp112, 4.16 pp191, 7.3 * 计算机科学与技术学院 * 例7.4.2 用红，黄，蓝三色对等边三角形的顶点染色(例7.3.8)，共有多少种不同方案(翻转和旋转）？ 1 2 3 Pólya定理 * 计算机科学与技术学院 * 2 1 B C A 3 1）旋转对称关系 （转0°） （转120°） （转240°） 2）翻转对称关系 （绕3C） （绕2B） （绕1A） * 计算机科学与技术学院 * 解：设针对的 置换群为 所求不等价的方案数为： b y b y r y y b y r y r r y b r r r y y y r b r b b b b r b Pólya定理 2 1 B C A 3 * 计算机科学与技术学院 * 解：设针对的 旋转置换群为 所求不等价的方案数为： （只有旋转） b y b y r y y b y r y r r y b r r r y y y r b r b b b b r b Pólya定理 2 1 B C A 3 * 计算机科学与技术学院 * Pólya定理 只允许旋转的情况多一种涂色方案，因为图7.3.4中方案a22和a23经过旋转可以变成同一种涂色