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)?请给出计算
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
。
6-6 验证下列函数对于运算
是一个群:
,
,
,
,
,
。
(解)首先,按所定义的乘法计算乘积:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
其次,由上述运算结果知诸
满足群的定义
(1) 封闭性:显然已经成立;
(2) 结合律:也可以逐个验证成立,例如
=
(3) 单位元:可以看出单位元是
,因为
,故对任一函数
都有
,
(4) 逆元素:列
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
如下
,
,
,
,
,
因此,由群的定义知这6个函数构成一个不可交换群。
6-7 一张卡片分成4×2个方格,每格用红蓝两色涂染,可有多少种
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
?
(解)如图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种颜色的宝石可供选择,问可以有多少种
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
?
(解)设正五角星的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