《教材RABrualdi组合数学机械工业出版社影印版.ppt》由会员分享，可在线阅读，更多相关《教材RABrualdi组合数学机械工业出版社影印版.ppt（29页珍藏版）》请在三一文库上搜索。
1、教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版) 参考:1. 卢开澄, 组合数学,清华大学出版社 2. 吴文虎等, 程序设计中的组合数学, 清华大学出版社 网络教室: 组合数学,组合数学,计算机学院软件所：王贵珍 Tel: 13167532629 Email： Address: 中心教学楼905#,课 程 安 排,课程特点及最后成绩 1. 课程特点：技巧性较强。 2. 成绩评定：作业、程序设计占30，期末为闭卷笔试考试，成绩占70。, 提示： 技巧的应用来自于经验的积累，所以 解决的组合数学问题越多，那么能够解决下 一个组合数学问题的可能性就越大。,组合
2、数学研究的内容,离散结构的存在、计数、分析 和优化。,例:棋盘的完美覆盖,mn棋盘: m行n列方格, b-牌:1行b个的方格条 mn棋盘被b-牌的一个完美覆盖是 b-牌在棋盘上的一个排列, 满足: (1) 每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格.,定理: mn棋盘有b-牌的完美覆盖b|m或b|n.,34棋盘 66棋盘有4-牌的完美覆盖吗?,有2-牌的完美覆盖.,棋盘覆盖及其变化,66棋盘用1,2,3,4如图填数，4牌在任何位置都覆盖1,2,3,4，去掉成组的1234, 多余1124。所以66棋盘不能用4牌完美覆盖。,完美覆盖,变化: 带禁止方格, 用多米诺牌(2-牌)覆盖
3、,例:Nim取子游戏,设有k1堆硬币,各堆分别含有n1,n2,nk枚硬币. 游戏规则: (1)两游戏人交替取子; (2)每人在一轮取子时只能取一堆中的硬币, 取至少一枚,至多全堆硬币; (3)所有堆都变成空堆时, 游戏结束, 最后取子的人获胜. 例1. (100, 389) 例2. (7, 8, 15),游戏人I有必胜策略,游戏人II有必胜策略,平衡态,设有游戏(n1,n2,nk), 且各数的二进制展开是 ni=aisai(s-1)ai1, i=1,2,k 若 a11+a21+ak1 (各数第1位之和), a1s+a2s+aks (各数第s位之和) 都是偶数, 则称游戏处于平衡态.,(7,8,
4、15): (100,389): (7,12,13):,平衡态,非平衡态,非平衡态,平衡态与非平衡态的转化,(7,8,15):平衡态 (100,389):非平衡态 (7,8,13):非平衡态,游戏终止时是平衡态 平衡态不能经一轮取子达到平衡态 非平衡态可经一轮取子达到平衡态(?),结论,定理: 若游戏非平衡, 则游戏人I有必胜策略; 若游戏平衡, 则游戏人II有必胜策略. 定义: 若n1,n2,nk二进展开第i位的和是奇数, 则称第i位是非平衡位. 命题: 设一游戏最大非平衡位是第j位, 则 游戏人I可以从某堆取币使游戏达到平衡态 当且仅当 该堆币数二进展开第j位是1. 注意比较与习题1.33叙
5、述的差别.,拉丁方,定义: 若A是由n个元素构成的n阶方阵, 其中每个元素在每行每列各出现一次, 则称A是拉丁方. 设A=(aij), 每个元素每行(列)只出现一次: aij=aik j=k ( aji=aki j=k ),36名军官问题,(18世纪)36军官问题: 6个地区, 6种军衔各一名. 将这36名军官排成66方阵, 使得 1)每行每列都有任一地区的军官; 2)每行每列都有任一军衔的军官. i :军衔, j :地区, 军官对应数偶(i, j), i, j0,5 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3)
6、每个数偶只出现一次.,正交拉丁方,定义:设A=(aij)nn,B=(bij)nn是两个nn拉丁方. 令C=(aij, bij)nn,若C的n2对数偶互不相同, 则称A与B正交. 36军官问题等价于构造两个正交的6阶拉丁方. 例: 3阶正交拉丁方,正交拉丁方的实际意义,正交的拉丁方的一个应用: 药物配合试验 三种治发烧药和三种治感冒药, 对三位病人试验, 要求三天内每人都服这几种药, 比较配合疗效. 这时就可用上面讨论过的3阶正交拉丁方.,行:人, 列:天 (i,j): i,发烧药 j, 感冒药,Euler的猜测,令N(n)为两两正交的n阶拉丁方的最大个数. N(1)=2, N(2)=1, N(
7、3)=2 定理1: 若n1,则N(n)n-1. 定理2: 若n=pa, p是素数,a0, 则N(n)=n-1. 定理3: 若n是奇数, 则N(n)2. 定理4: 若N(m)2,N(n)2, 则N(mn)2.(自学) 推论: 若n2且n4k+2, k0, 则N(n)2.(?) Euler(17071783)猜测: 对任意n=4k+2, k0, N(n)=1.,Euler猜测的解决,1900年 Tarry(法) 验证了N(6)=1. 1959年 Parker(美) 证明 N(10)2. 1959年 Bose(印), Parker, Shrikhande(印) 证明 N(4k+2)2, 任意k1.,
8、N(n) n-1,定理1: n1, N(n) n-1. 即若A1,A2,Ak是MOLS (两两正交拉丁方), 则必有 kn-1.,置换的定义与表示: 置换: 有限集(例如1,2,n)上的一一对应. 表示: p(1)=a1, p(2)=a2, p(n)=an, 注: a1a2an是1,2,n的一个排列,置换,设 p是1,2,n上一置换, A=(aij)nn是矩阵, aij 1,2,n 定义 p(A)= ( p(aij) )nn , 例:,p(A)性质讨论,若A是拉丁方, p是置换, p(A)是拉丁方吗? p(i)在每行每列只出现一次. 2. 若A是拉丁方, 则A与p(A)是否正交? A与p(A)
9、组成的数偶只有: (i, p(i), i=1,n 3. 若A与B正交, 则p(A)与B是否正交? 由于p是一一映射,所以 ( p(i1), j1)=( p(i2), j2) ( i1, j1)=( i2, j2) p(A)与B不正交 A与B不正交,N(n) n-1的证明,定理: 两两正交的n阶拉丁方不超过n-1个. 证明: 取k个n阶MOLS: A1, A2, , Ak 取置换 pi ,使得pi(Ai)的第一行为1,2,n:,则 p1(A1), pk(Ak)两两正交,且第二行第一个元素 满足: 1) 不等于1; 2) 互不相等. 所以 kn-1.,观察,每行分别左移1,2,3,4格 p阶方阵A
10、1,A2,Ap-1: Ak=(aij(k)pp, k=1,2,p-1. aij(k)=ki+j mod p, i, j0,p-1 定理: 设p为素数, 则N(p)=p-1.,p=4, k=2,p=5,k=1 p=5,k=2 p=5,k=3 p=5,k=4,定理: 设p为素数, 则N(p)=p-1.,证明:Ak=(aij(k)pp, k=1,2,p-1. aij(k)=ki+j mod p, i,j= 0,1,p-1 先证Ak是拉丁方: aij(k) = ait(k)jt mod pj=t aij(k) = asj(k)k(i-s)0 mod pi=s 再证Ag,Ah正交: 若(aij(g),a
11、ij(h)=(ars(g),ars(h) 则 g(i-r)+(j-s)0 mod p, h(i-r)+(j-s)0 mod p 得 (g-h)(i-r)0 mod pi=r j=s 得证. key: ab=0 mod p a=0或b=0mod p. ( p=4? ),定理2: n=pa, p素数,a0 N(n)=n-1,定义: 设集合F对可交换运算+和封闭, 满足 (1) 是群(记其么元为0), (2) 乘法分配律: a(b+c)=ab+ac (3) 是半群, (4) 消去律: ab=0 a=0或b=0. 则称是一个域. F有限:有限域(Galois域GF) 注: (3)+(4)等价于是群.
12、命题: 若n阶有限域存在, 则N(n)=n-1. 定理: p素数,a正, pa阶GF存在. GF的阶是素数幂.,GF的构造方法,以GF(n)记n阶有限域. 对素数p, GF(p)= 对a0, 取a阶多项式xa+c1xa-1+ca, 满足: 各次项系数取值于GF(p) 没有根在GF(p)上 记其任一个根为, 令 F=b0+b1+ba-1a-1 : b0,b1,ba-10,p-1 则GF(pa)=.,举例:阶为22的有限域,p=2，a=2 GF(p)= GF(2)=Z2=, 取a阶多项式为x2+x+1， 令为方程x2+x+1 =0的根, F(pa)=F(4)=b0+b1 |b0,b1 0,1 =0
13、,1, , 1+ 所以是域.,举例:阶为22的有限域,GF(4)=是域. 其中为方程x2+x+1 =0的根,加法表：,0 1 1+,1 1+,0,1+ ,1+ ,0,1,1,0,乘法表：,0 0 0 0,0 0 0,1,1+,1+,1,1+,1,举例:阶为33的有限域,GF(3)=Z3=0,1,2,令为x3+2x+1=0的根,令 F=a + b + c 2 : a,b,cZ3 是27阶有限域. 例: (1+ 22) = + 23= + 2 + 4 = 1. (2 + + 22)(1 + 2)=1.,利用有限域构造MOLS举例,回顾 Ak=(aij(k)nn, aij(k)=ki+j mod p, 设有n阶有限域, 则Ak=(aij(k)nn, k=1,n-1, aij(k)=bkbi+bj , 其中b0=0, i, j0,n-1,作业,第一章P13：2, 4，30, 36. 第十章P387：17, 46. 编程题:nim和nim2 每章都交作业,