组合数学(西安电子科技大学(第二版))课后习题6.doc

《组合数学(西安电子科技大学(第二版))课后习题6.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题六习题六（Polya定理）1．一张卡片分成个方格，每格用红蓝两色涂染，可有多少种方法？12345678解：如图所示将卡片的八个格进行编号，则对应集合，用红蓝两色涂染，卡片只能旋转，不能翻转，则可得S上的置换群，其中，，，现在用两种颜色进行涂染，则不同的涂染方案有：（种）¨若卡片还能翻转，但同一个格子对应的正反面要求同色，则除了上述两个置换外，还有沿着横、竖两个对称轴翻转的置换，从而可知不同的染色方案有：（种）¨若同一个格子对应的正反面不要求同色，且卡片既能旋转，又能翻转，则相应的置换为：，，其中是卡片的背面分别依序与对应的格子。那么，此时的染色方案有

2、（种）2．一根木棍等分成n段，用m种颜色涂染，问有多少种染法？当和时各有多少种方法？12……解：如图给木棍的每段依次编号为，则对应集合，用m中颜色进行涂染，当n为偶数时，可得S上的置换群，其中，，（木棍只能翻转）第13页（共13页）习题六用m种颜色进行涂染，则不同的染色方案有：；当n为奇数时，可得S上的置换群，其中，则不同的染色方案有：。综上所述，不同的染色方案有：。当时，不同的染色方案有：当时，不同的染色方案有：3．正五角星的五个顶点各镶嵌一个宝石，若有m种颜色的宝石可供选择，问可以有多少种方案？解：该问题即：用m种颜色给正五边形的五个d顶点染色，有多

3、少种方案。如图所示的正五边形，可绕其中心O旋转，以及过，，…，等5条轴翻转，从而得到置换群Q所含的置换如下：，，，，，，，，，，根据Polya定理，不同的染色方案有：4．有一个正方形木筐，用漆刷4边。现有三种不同颜色的漆，可有多少种不同的涂法？解：如图所示正方形，用三种颜色对正方形的四条边进行涂染。正方形可绕其中心逆时针旋转第13页（共13页）习题六，及关于两条对角线和中线进行翻转，于是可得到置换群Q所包含的置换如下：，，，，，，，根据Polya定理，不同方案有：（种）5．一个圆分成6个相同的扇形，分别涂以三色之一，可有多少种涂法？解：如图所示，用三个颜

4、色对圆的六个扇形进行涂染，圆可以绕其圆心逆时针旋转，于是可以得到置换群Q所包含的置换如下：，，，，，，根据Polya定理，则不同的染色方案有：（种）6．两个变量的布尔函数的全体关于变量下标可以进行置换时，其等价类的个数为多少？写出其布尔表达式。解：设2个输入变量为：，其变换群为：，，，设的状态集合为，则对应于集合的置换必得S的某个置换，由此可以得到S的置换群Q为：，求不同布尔函数的问题，就相当于求服从群Q的变换的4个顶点用2种颜色（相当于布尔函数的0、1状态）进行染色的方案数。由Polya定理可知，其等价类的个数为：（个）。下表给出了由两个变量定义的16

5、个布尔函数，其中的等价类可划分如下（同一括号中的两个函数等价）：，，，，，，，，，，，自变量x01y0101函数00000第13页（共13页）习题六x∧y0001x∧0010x0011∧y0100y0101(x∨y)∧(∨)0110x∨y0111∧1000(∨y)∧(x∨)10011010x∨10111100∨y1101∨1110111117．红、蓝、绿三种颜色的珠子，每种充分多，取出4颗摆成一个圆环，可有多少种不同的摆法？解：该问题可等价于从无穷多的珠子中取出四个摆成一个圆环，然后再用三种颜色对珠子进行着色，问有多少种不同的着色方案。如图所示，使之重合

6、的运动有逆时针旋转，及绕四条对称轴翻转，于是可以得到置换群，其中：，，，，第13页（共13页）习题六，，，，根据Polya定理，不同排法有：（种）8．某物质分子由5个A原子和3个B原子组成，8个原子构成一个正立方体，问最多可能有几类分子？解：该问题即：用两种颜色a、b对正立方体的八个顶点进行着色，求5个顶点着a颜色，5个顶点着b颜色的方案数。见P140页例6.4.2图6.4.3。使正立方体重合的关于顶点的置换群Q如下：（1）单位元：，格式为；（2）绕轴（面-面中心连线）旋转的置换分别为：和，格式为，同类置换共有6个；（3）绕轴旋转的置换为：，格式为，同类

7、共有3个；（4）绕轴（棱中－棱中）旋转的置换为：，格式为，同类置换有6个；（5）绕轴（对角线）旋转的置换分别为：和，格式为，同类置换共有8个。则群Q的轮换指标为：，令，代入上式得：其中，的系数为：，即最多可能有3类分子。9．验证下列函数对于运算是一个群：，，，，，解：设，画出其运算表，便可得以下四条。（1）封闭性。对任意的，有；（2）结合性。对任意的，有，函数复合运算本身就满足结合性；（3）单位元。显然对任意的，有，故是么元。第13页（共13页）习题六（4）逆元。，，，，，故的逆元为其自身，互为逆元素。10．用四种颜色涂染正方体的六个面，求其中两个面用色

8、g，两个面用色y，其余一面用b，一面用r的方案数。解：见P147例6.6.4图6