08年讲义组合数学姜老师习题6 波利亚定理

10 组合 11 第六章 Pólya(波利亚)定理 习 题 六 6-1 证明下列集合关于所给的运算构成一个群： （1） =，定义 上的运算为整数的加法运算； （2） ={1，2，4，7，8，11，13，14}，其运算为模15的乘法运算。即设a,b∈ ，定义a与b的积为 ab mod 15。 （3） ={1，2，4，8，16，32}，其运算为模21的乘法运算。并证明 是一个循环群，同时给出它的生成元。 6-2 求习题1中群 和 的所有子群。 6-3 证明置换的乘法满足结合律。 6-4 2n个人在玩一种队列变换游戏，其规则是大家先排成一列纵队，并从第一个人开始向后编号为1，2，…，2n。然后让偶数号的人出列，并按照原来的相对顺序重新排到队列的末尾，就认为是完成了一轮队列变换。即经过第一轮队列变换后，这2n个人新的排列方式是 1，3，5，…，(2n－1)，2，4，6，…，2n 问：当n分别为5，6，7，8时，经过多少轮变换，队伍就能恢复到变换之前的排列状态。 6-5 在习题4所规定的队列变换中，将第一轮变换视为一个置换p，那么，p将数k变为了哪个数（1≤k≤2n）？请给出。 6-6 验证下列函数对于运算 是一个群： ， ， ， ， ， 。 （解）首先，按所定义的乘法计算乘积： ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 其次，由上述运算结果知诸 满足群的定义 （1） 封闭性：显然已经成立； （2） 结合律：也可以逐个验证成立，例如 ＝ （3） 单位元：可以看出单位元是 ，因为 ，故对任一函数 都有 ， （4） 逆元素：列如下 ， ， ， ， ， 因此，由群的定义知这6个函数构成一个不可交换群。 6-7 一张卡片分成4×2个方格，每格用红蓝两色涂染，可有多少种方法？ （解）如图6.2.1，给每个方格标上号：1,2,…,8，相应的置换为（设卡片只能旋转，不能翻转） 1 2 3 4 5 6 7 8 图6.2.1 卡片染色 ， 由Pólya定理知，不同的染色方法数为 ＝ 若卡片还能翻转，但同一个格子对应的正反面要求同色，则除了上述两个置换外，还有沿着横、竖两个对称轴翻转的置换 ， 从而可知不同的染色方法数为 ＝ ＝76 若同一个格子对应的正反面不要求同色，且卡片既能旋转，又能翻转，则相应的置换为 ，， ， 其中A，B，…，H是卡片的背面分别依序与1，2，…，8对应的格子。那么，此时的染色方法数为 ＝ ＝16 576 6-8 一根木棍等分成n段，用m种颜色涂染，问有多少种染法？当n＝m＝2和n＝m＝3时各有多少种方法？ （解）如图6.2.2，关于木棒的置换只有两个： 1 2 3 …… n-1 n 图6.2.2 木棒染色 ， 由Pólya定理知，不同的染色方法数为 L＝ 当n＝m＝2时，有L＝ ＝3种不等价的染色方法；当n＝m＝3时，有L＝ ＝18种不等价的方法。 6-9 正五角星的五个顶点各镶嵌一个宝石，若有m种颜色的宝石可供选择，问可以有多少种方案？ （解）设正五角星的5个顶点分别依次为1,2,…,5，因正五角星是可以翻转的，故相应于正五角星的五个顶点的变换有两类，第一类是绕其几何中心的5个平面旋转变换 （即旋转72× 度），第二类是以某个顶点与其几何中心的连线为轴的翻转变换，对应的10个置换是 ， ， ， ， ， ， ， ， 由Pólya定理，不同的镶嵌方案数为 L＝ 6-10 有一个正方形木筐，用漆刷4边。现有三种不同颜色的漆，可有多少种不同的涂法？ （解）将正方形木筐的4条边依次记为1，2，3，4（见图6.2.3），由题意知木筐既可以旋转，又可以翻转。对应的置换为 绕正方形中心逆时针旋转 （ ）的置换 ， ， ， 以1-3、2-4两组对边的中心的连线为轴的翻转 ， 以A-C、B-D两组对角线为轴的翻转 ， A 1 B 4 2 D 3 C 图6.2.3 木筐染色 由Pólya定理知，不同涂法总数为 L＝ ＝21 6-11 一个圆分成6个相同的扇形，分别涂以三色之一，可有多少种涂法？ （解）将6个扇形依次记为1，2，3，4，5，6（见图6.2.4），这些扇形可以分别绕圆心旋转 （ ），从而得置换群Q所含的置换如下： ＝ ， ＝ ， ＝ ， ＝ ， ＝ ， ＝ ， 1 6 2 5 3 4 图6.2.4 扇形染色 故由Pólya定理知不同的涂色方案数为 L＝ ＝130 6-12 两个变量的布尔函数f(x,y)的全体关于变量下标可以进行置换时，其等价类的个数为多少？写出其布尔表达式 。 （解）设等价类的个数为L。如图6.2.8所示，关于两个输入端 ＝ 的变换群记为H＝ ，其中 ， 设 的状态集合为 ＝ ，那么相应于集合 的置换群H，可得S的置换群Q＝ ，其中对应于 的 如下 ： ＝ ＝ ， ＝ x1 f（x1，x2） x2 图6.2.8 两个输入端的布尔装置 即 ＝ ＝ , ＝ ＝ 所以，求不同布尔函数装置的问题，相当于用两种颜色对4个对象{ }进行染色，求不等价的染色方案数。其中 服从群Q的变换，而两种颜色相当于布尔函数的0、1状态。故由Pólya定理知不等价的函数共有 L＝ ＝12 类。也就是说，两个变量的16个布尔函数中，只有12个是不等价的，其余的函数可通过改变输入端的顺序而得到。 表4.2.2给出了由两个变量定义的16个布尔函数，其中的等价类可划分如下（同一括号中的两个函数等价）： ， ， ， ， ， ， ， ， ， ， ， 表4.2.2 具有两个变量的布尔函数 自变量 x 0 1 y 0 1 0 1 函 数 0 0 0 0 0 x∧y 0 0 0 1 x∧ 0 0 1 0 x 0 0 1 1 ∧y 0 1 0 0 y 0 1 0 1 (x∨y) ∧( ∨ ) 0 1 1 0 x∨y 0 1 1 1 ∧ 1 0 0 0 ( ∨y) ∧(x∨ ) 1 0 0 1 1 0 1 0 x∨ 1 0 1 1 1 1 0 0 ∨y 1 1 0 1 ∨ 1 1 1 0 1 1 1 1 1 6-13 红、蓝、绿三种颜色的珠子，每种充分多，取出4颗摆成一个圆环，可有多少种不同的摆法？ （解）问题就是用3种颜色对正方形的4个顶点染色，且正方形可以旋转和翻转，求不等价的染法数目。 6-14 某物质分子由5个A原子和3个B原子组成，8个原子构成一个正立方体，问最多可能有几类分子？ （解）问题相当于用红、蓝两色对正立方体的8个顶点着色，5个顶点染红色、3个顶点染兰色的方案数。 使正立方体重合的关于顶点的运动群Q是(参见图6.2.5)： （1） 单位元(1)(2)(3)(4)(5)(6)(7)(8)，格式为 ； （2） 绕 轴旋转±90o的置换分别为(1234)(5678)和(4321)(8765)，格式为 ，同类的置换共有6个； （3） 绕 轴旋转180 o的置换为(13)(24)(57)(68)，格式为 ，同类的置换有3个； （4） 绕 轴旋转180 o的置换为(17)(26)(35)(48)，格式为 ，同类的置换有6个； 绕 轴旋转±120 o的置换分别为(136)(475)(8)(2)和(631)(574)(2)(8)，格式为 ，同类置换有8个。 图6.2.5 正方体8个顶点的置换 因此，Q的轮换指标为 以 代入，有 其中 的系数为 ＝3 即不同结构的分子只有3种。 6-15 用g,r,b,y四种颜色涂染正方体的六个面，求其中两个面用色g，两个面用色y，其余一面用b，一面用r的方案数。 6-16 对一正六面体的八个顶点，用y和r两种颜色染色，使其中有5个顶点用色y，其余3个顶点用色r，求其方案数。 6-17 由b、r、g三种颜色的5颗珠子镶成的圆环，共有几种不同的方案？ 6-18 一个圆圈上有n个珠子，用n种颜色对这n个珠子着色，要求颜色数目不少于n的方案数？ 6-19 若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案？ 6-20 试说明群S5的不同格式及其个数。 6-21 将一正方形均分为4个格子，用两种颜色对4个格子着色，问能得到多少种不同的图像？其中认为两种颜色互换后使之一致的方案属同一类。 6-22 在正4面体的每个面上都任意引一条高，有多少方案？ 6-23 一幅正方形的肖像与一个立方体的面一样大，6幅相同的肖像贴在立方体的6个面上有多少中贴法？ 6-24 (a)本质上有多少种确实是2个输入端的布尔电路？写出其布尔表达式。 (b)本质上有多少种确实是3个输入端的布尔电路？ 6-25 用8个相同的骰子垛成一个正6面体，有多少方案？ 6-26 正6面体的6个面和8个顶点分别用红、蓝两种颜色的珠子嵌入。试问有多少种不同的方案数？（旋转使之一致的方案看作是相同的）。 _1158647421.unknown _1158676552.unknown _1158681952.unknown _1158686401.unknown _1158688215.unknown _1160074108.unknown _1245816249.unknown _1245816261.unknown _1245816265.unknown _1245816268.unknown _1245816258.unknown _1160076304.unknown _1160076667.unknown _1160076681.unknown _1160076712.unknown _1160076630.unknown _1160074131.unknown _1158688417.unknown _1158688439.unknown _1158688461.unknown _1158688474.unknown _1158688426.unknown _1158688388.unknown _1158688407.unknown _1158688286.unknown _1158688317.unknown _1158688247.unknown _1158687619.unknown _1158687879.unknown _1158688040.unknown _1158687762.unknown _1158686479.unknown _1158686506.unknown _1158686520.unknown _1158686531.unknown _1158686495.unknown _1158686403.unknown _1158686447.unknown _1158686402.unknown _1158684753.unknown _1158686254.unknown _1158686286.unknown _1158686311.unknown _1158686265.unknown _1158684944.unknown _1158685373.unknown _1158684822.unknown _1158682206.unknown _1158683154.unknown _1158683227.unknown _1158683249.unknown _1158683059.unknown _1158682159.unknown _1158682198.unknown _1158682031.unknown _1158681975.unknown _1158682022.unknown _1158678573.unknown _1158679805.unknown _1158681790.unknown _1158681825.unknown _1158681896.unknown _1158679860.unknown _1158681770.unknown _1158679677.unknown _1158679770.unknown _1158678657.unknown _1158676895.unknown _1158677040.unknown _1158678561.unknown _1158676897.unknown _1158676753.unknown _1158676766.unknown _1158676590.unknown _1158649802.unknown _1158651262.unknown _1158676369.unknown _1158676459.unknown _1158676513.unknown _1158676412.unknown _1158673488.unknown _1158673506.unknown _1158651265.unknown _1158650901.unknown _1158651252.unknown _1158651256.unknown _1158651004.unknown _1158649830.unknown _1158649868.unknown _1158650302.unknown _1158649855.unknown _1158649816.unknown _1158648525.unknown _1158649411.unknown _1158649519.unknown _1158649688.unknown _1158649476.unknown _1158648904.unknown _1158649091.unknown _1158649197.unknown _1158649015.unknown _1158648793.unknown _1158647799.unknown _1158648055.unknown _1158648157.unknown _1158647954.unknown _1158647604.unknown _1158647724.unknown _1158647518.unknown _1152123054.unknown _1158646864.unknown _1158647133.unknown _1158647226.unknown _1158647310.unknown _1158647194.unknown _1158646963.unknown _1158647074.unknown _1158646924.unknown _1155792035.unknown _1155793190.unknown _1158645538.unknown _1158645732.unknown _1158645804.unknown _1155793246.unknown _1155793324.unknown _1155793474.unknown _1155793217.unknown _1155792414.unknown _1155793086.unknown _1155793091.unknown _1155793095.unknown _1155792923.unknown _1155792041.unknown _1152132564.unknown _1155791975.unknown _1155791987.unknown _1155791970.unknown _1152123071.unknown _1152132560.unknown _1152132563.unknown _1152132558.unknown _1152132557.unknown _1152123056.unknown _1100845723.unknown _1100848301.unknown _1110809235.unknown _1110809658.unknown _1119083539.unknown _1119083541.unknown _1119083545.unknown _1110809697.unknown _1110809426.unknown _1110809485.unknown _1110809527.unknown _1110809305.unknown _1100848351.unknown _1100848366.unknown _1100848326.unknown _1100848162.unknown _1100848179.unknown _1100848241.unknown _1100848171.unknown _1100847667.unknown _1100848028.unknown _1100846051.unknown _1029248296.unknown _1029248376.unknown _1029248401.unknown _1029248323.unknown _1029248218.unknown _1029248286.unknown _1026854458.unknown _1029248169.unknown _1026854424.unknown