组合数学-12组合设计

第10章组合设计组合设计，是将集合的元素分成能够满足某些特定性质的子集的排列方法。§1模运算一、模算符比如：（1）27mod5=2若，记为：a=q×n+ramodn=r,（r=0,1,2，…，n-1）（2）36mod12=0（3）-18mod14=10（余数为-4，-4+14=10）（4）-7mod10=3（余数为-7，-7+10=3）整数集Z模n后得到集合Zn={0,1,2,3,…,n-1}钟表计时——模12，星期——模7，角度——模360星期九=星期二18点=6点420度=60度模运算保证了有限集上四则运算的封闭性!二、Zn上的模运算例1在Z15中求7+14：（7+14）mod15=67-11：（7-11）mod15=117*11：（7*11）mod2=1例2在Z2中求7+14：（7+14）mod2=17-11：（7-11）mod2=0+01001110X010011101、模运算的运算法则例3(17+27)mod14=2(123×(-10))mod19=(-1230)mod19=5另法计算:(17mod14)+(27mod14)=(3+13)mod14=2(123mod19)×(-10mod19)=9×9mod19=81mod19=5定理(a±b)modn=(amodn)±(amodn)(a×b)modn=(amodn)×(amodn)例410nmodx=(10modx)n10nmod3=(10mod3)n=110nmod9=(10mod9)n=110nmod5=(10mod5)n=0(n0)56712=5*105+6*104+7*103+1*101+2*10056712mod3==5mod3+6mod3+7mod3+1mod3+2mod3=(5+6+7+1+2)mod3=21mod3=0十进制数被3或9整除，且仅当各位数码之和能被3或9整除。十进制数模3或模9，等于各位数码之和模3或模9。(1723345+2124945)mod3=(25mod3)+(27mod3)=1+0=1(1723345*2124945)mod3=(25mod3)*(27mod3)=1*0=0例5(1723347+2124949)mod5=7mod5+9mod5=1(1723347*2124949)mod5=(7*9)mod5=3模5运算等于个位运算！2、加法逆与减法-a=(n-a)modn，-a称为a的加法逆（负元）。在Z10中：a0123456789-a0987654321做减法等于加负元.若a+b=0modn，则a与b互为加法逆。3乘法逆与除法：b=a-1可能存在，也可能不存在。定理a有乘法逆当且仅当gcd(a,n)=1，即a与n互素。若a×b=1modn，则a与b互为乘法逆。若a-1存在，称其为a的乘法逆（逆元）。做除法等同于乘逆元0没有乘法逆元例6在Z10中，8的乘法逆8-1=？由于gcd(8,10)=2≠1，8没有乘法逆。在Z10中，没有任何数字与8相乘=1!X012345678900000000000112345678924680246839258147460482655050566284795384291例7求Z10中的乘法逆从乘法表中可以看到:1,3,7,9有乘法逆1-1=13-1=77-1=39-1=9其余0,2,4,5,6,8都没有乘法逆。构成三对乘法逆：(1,1)(3,7)(9,9）例8求Z11中的乘法逆由于11是质数，gcd(k,11)=1,所以除0外，1,2,…,10都有乘法逆。利用乘法表，可知有6对乘法逆：(1,1)(2,6)(3,4)(5,9)(7,8)(10,10)三、代数结构定义设G为一非空集合,为定义在G上的二元运算.如果下述条件成立,则称代数系统G,为一个群.(1)运算封闭性:a,bG,abG;(2)结合律:a,b,cG,a(bc)=(ab)c;(3)存在单位元eG:使得对aG,ae=ea=a;(4)aG,存在a的逆元a1G:使得aa1=a1a=e.(5)交换律：a，bG,ab=ba.交换群1、群(group)例9G=Zn,+（模n+)为一个群,且是交换群。单位元为0modna的逆元是–amodn=n-a例10G=Z*n,×（模n×)为一个群,且是交换群。单位元为1modna的逆元是a-1modn例11A={a,b,c,d},G=A,·是交换群。运算表：·abcdaabcdbbcdaccdabddabc单位元:a逆元对:(a,a),(b,d),(c,c)2、环(ring)定义设G为一非空集合,G上定义了两种二元运算+：构成加法交换群：满足封闭性+结合律（+交换律）而且*对+有分配律则称代数系统R=G,+,为一个环（或交换环）。+运算*运算运算封闭性运算封闭性结合律结合律交换律交换律*单位元(零元）逆元（负元）*对+分配律Z10上的（+,*）运算构成交换环R=Z10,+,不能进行“除法”运算3、域(field)定义设G为一非空集合,G上定义了两种二元运算+：构成加法交换群：构成乘法交换群而且*对+有分配律则称代数系统F=G,+,为一个域。+运算*运算运算封闭性运算封闭性结合律结合律交换律交换律零元单位元负元逆元*对+分配律加减乘除畅通无阻！域的例子：1、有理数域2、实数域3、有限域：ZpGalois（伽罗华）指出：有限域的元素个数必为pn。因此，有限域又称伽罗华域，记为GF(pn)例12GF(5)=Z5,在模5下可以定义四则运算。例13GF(2)=Z2,在模2下可以定义四则运算。0+0=0；0+1=1，1+0=1，1+1=0（异或运算）0*0=0；0*1=0，1*0=0，1*1=1（与运算）加法零元：0，-0=0；-1=1乘法单位元：1，1-1=1；0无逆元加法就是减法乘法就是除法例13GF(22)——4元素的有限域不可能是Z4，mod4运算中，2无乘法逆元。GF(22)中的元素记为a+bi，系数a,b∈GF(2)这4个元素为{0,1,i,1+i}其中i是素多项式x2+x+1=0在GF(2)中的根，满足i2+i+1=0,即i2=-(i+1)=i+1)1(12)1(10)1()1(121)1(iiiiiiiiiiiiiiiiiiiiiiii)1(121)1(1)1()1(1222例13GF(22)——4元素的有限域GF(22)的元素可视为GF(2)上关于i的1次多项式，上述运算可以视为多项式的运算。1)1mod()1()1(1)1()1(122222iiiiiiiiiii所以为了保证运算的封闭性，作为关于素多项式i2+i+1=0的模运算。iiiiiiiiii)10)1()1mod()12()1mod()(12222逢i2换为i+1即可例13GF(22)——4元素的有限域＋01i1+i001i1+i1101+iiii1+i011+i1+ii10×01i1+i00000101i1+ii0i1+i11+i01+i1i)1(,11,111-1iiii例14GF(33)——27个元素的有限域GF(33)的元素可视为GF(3)上关于i的2次多项式)3(,,,2GFcbacibia212)12mod(33iiiii逢i3换为i+2即可为了保证运算的封闭性，作为关于3次素多项式i3+2i+1=0的模运算。也可把i视为i3+2i+1=0的根。例14GF(33)——27个元素的有限域)21)(21(22iii逢i3换为i+2即可432242221iiiii)2(4)2(2412iiiii22482441iiiii2221ii)21(2ii134)2(223iiiii互逆。）与所以21(2ii§2区组设计一、一个实用案例：在市场调查中，需要确定消费者对7种牙膏的喜好程度。随机抽取若干试验者，让他们对牙膏作两两对比（配对试验）。应该选取多少试验者？每人使用哪些“牙膏进行配对比较”？（1）抽取n个人，每人使用全部7种牙膏，每人比较21对。（2）抽取7个人，每人使用3种牙膏，每人比较3对。完全区组不完全区组区组：每个人安排的牙膏品种区组：每个试验区安排的样本品种例1：0123456合计B11113B21113B31113B41113B51113B61113B71113合计3333333B1={0,1,3}B2={1,2,4}B3={2,3,5}B4={3,4,6}B5={4,5,0}B6={5,6,1}B7={6,0,2}7种牙膏样本集合X={0,1,2,3,4,5,6}关联矩阵7个区组一、平衡不完全区组设计——BIBD样本集合：X={0,1,2,…,v-1}BalancedIncompleteBlockDesign区组：X的k元素子集称为一个区组Bi区组设计（集类）：B={B1，B2,…,Bb}k=v为完全区组设计，kv为不完全区组设计。若X的每一对元素都在λ个区组中出现，称平衡区组设计，λ称为设计指数。1、BIBD的参数b——区组个数（B的大小）v——样本个数（X的大小）k——区组内样本数（Bi的大小）r——每个样本所属的区组数（样本重复数）λ——每对样本所属的区组数（样本对重复数）2、参数的相互关系(1)b*k=r*v（样本使用次数）(2)(k-1)*r=λ*(v-1)每个样本出现在r区组，共有r*v次每区组含有k个样本，共有b*k次所以b*k=r*v)1()1(2)1(2)1(222222krvrvkbkkbvvbCCbCCkCCkvkkvv得，代入将因此有个配对共个配对，可作个样本，每区组有个配对共次，每对重复个配对，共有(3)λr（配对重复数样本重复数）(4)b≥v,11)1()1(rvkvkrkrv所以由于在不完全区组中可得由,v)*(bvb可知列满秩于关联矩阵由在BIBD的5个参数中，受到两个等式约束，只有三个独立参数。通常设计指数λ为指定的已知数，另外两个需要根据实际需求确定。例2v=16,k=14,b=12,r=3,能否构成BIBD?例3v=9,k=3,b=12,r=4,能否构成BIBD?BIBD,,153*311。故不能构成非整数vkr。故能构成BIBD1,82*411vkr(0,5,7)(2,4,6),(1,3,8),(2,3,7),(1,5,6),4,8),(0,(2,5,8)(1,4,7),(0,3,6),(6,7,8),(3,4,5),2),1,(0,,876543210区组为将样本排成方阵关联矩阵A:12*9000000111000111000111000000100010001100010001100010001010100001100001010001010100100010001010001100001100010A’A:9*9对角线上恰好是r=4其他位置恰好是λ=1对角线占优，可逆例4v=16排成4*4方阵，X={xij|i,j=1,2,3,4}},{ijijxjiB但不含列的元素行与区组6,16,616rbkv，******ijx为了证明这是一个BIBD，还需要证明每个配对(x,y)恰好恰好被测试2次（出现在2个区组中）即证明λ=2。相当于16种牙膏被测试选择16个人作测试每人使用6种牙膏，每种牙膏被6人使用对应的分组中同在两个则在同一行若*),(,),(yxyxyx****yx对应的分组中同在两个则在同一列若*),(,),(yxyxyx**对应的分组中在两个则不同行也不同列若*),(,),(yxyx2所以二、对称平衡不完全区组设计——SBIBDSymmetricBalancedIncompleteBlockDesign1、SBIBD的参数（