组合数学第五章

1第五章区组设计与编码1.拉丁方与正交拉丁方拉丁方：由1，2，…，n构成n×n方阵nnija)(，如果每行每列中1，2，…，n各出现一次，则称此方阵为拉丁方。如：12212n1233122312131323213n正交换丁方：设nnijnnijaAaA)2(2)1(1是两个n×n的拉丁方，如果矩阵nnijijaa)2()1(,中2n个数偶)2()1(,ijijaa互不相同，nji,,2,1,，则称1A和2A正交，或称1A和2A是互相正交的拉丁方。如：123312231,21313232121AA由于)1,2()2,1()3,3()3,1()1,3()2,2()2,3()3,2()1,1(中元素两两不同，故21AA36名军官问题：ija表示军官的军衔为i，军官所在的团为j，66),(ji要求第一个数字构成拉丁方，第二个数字也构成拉丁方，并且正交。定理：两两相互正交的n阶拉丁方的个数不超过n-1个pf：设kAAA,,,21是两两相互正交的n阶拉丁方，往证1nk。设naaa21是1，2，…，n的一个全排列，,,,2,1,)(klaAnnlijl对1A作如下置换2naaan2121，得一方阵nnijaA)1(1，则1A与kAA,2正交。事实上，如果1A不与2A正交，则nnijijaa)2()1(,中至少有一对数偶出现次数超过1次，设该对数偶为),(mlaa，则),(mal在)2()1(,ijijaa中至少出现2次，与21,AA正交矛盾，由此不妨设kAAA,,,21的第一行均为),,2,1(n，任取,1kml则方阵nnmijijaa)()1(,的第一行均是),,(),2,1(),1,1((rn从而1不能出现在kAAA,,,21的第2行第1列元素，故这些元素只能取2，3，…,n中一个，而且取法不能相同，故nk。2.域与有限域域：),(,:)1(,VVVVVAbel群baba),(（2）),(:***VVVVAbel群abba),(}0/{*VV（3）分配律成立acabcba)(cabaacb)(则称),,(V为域例：Q，R，C，QbabiaiQ,|)(二元域}1,0{2F，p元域}1,,2,1,0{pFp有限域：元素个数有限的域叫做有限域比如：},,2,1,0{pFp模p的剩余类域，取)(xf是][xFp中n次不可约多项式，则3pinnpqFaxaxaaxfxFF110))((][}{110pinnFaaaa为npq元域如：,1)(},1,0{22xxxfF则)(xf在][2xF中不可约，},|{))((][2101024FaaxaaxfxFF}1,,1,0{xx4F中元素的加法与乘法取模)(xf的运算11)1(2xxxxxx可以证明：有限域中元素的个数必为素数的方幂。定理：ppn,为素数，3,1n，则存在n-1个互相正交的n阶拉丁方。Pf：取n阶有限域},,,{110npnFF，其中1,010n令1,,2,1)(nkaAnnkijk其中.1,,2,1,0,)(njiajikkij则121,,,kAAA是正交拉丁方。kA是拉丁方否则kA中必存在某行（列）有两个元素相同，不妨设情形1：)()(kihkijaa则kikjik，,hjhj情形2：)()(kijkhjaajikjhk，ikhk，ihhiiA与)(jiAj相互正交4否则存在gA与hA不相互正交，即存在)()()()(hfkgfkhijgijaaaa则kjfi,部分非素数幂的正文拉丁方的构造设kAAA,,,21是一组1n阶正文拉丁方，kBBB,,,21是另一组2n阶的正文拉丁方，构造一组k个21nn阶矩阵如下：BraBraBraBraBraBraBraBaBaCrmnrmrmrnrrrnrrrrr)()()()(2)(22)21)(1)(12)(11112111kr,,2,1则kCCC,,,21是正文拉丁方如：32113221323131212321AA2431134242133124432134122143123421BB则)43()33()23()13()33()43()13()23()23()13()43()33()13()23()33()43(),3(1B)23()43()33()13()13()33()43()23()43()23()13()33()33()13()23()43(),3(2B53.均衡不完全的区组设计（BIBD）定义：设bvBBBxxxX,,,},,,,{2121是X的非空子集如果满足：（1）vkkBBBb21（2）X中每一个元素在bBBB,,,21中恰出现r次，（3）X中任一对元素在bBBB,,,21中正好同时出现次，则称{bBBB,,,21}为均衡不完全区组设律（BIBD）),,,,(krvb例},,,,,,,,,{987654321xxxxxxxxxX一个（12，9，4，31）设计如下：},,{3211xxxB，},,,{5442xxxB},,,{9873xxxB},,{7414xxxB},,{8525xxxB，},,{9636xxxB，},,{9517xxxB，},,{7628xxxB},,{8439xxxB,},,{86110xxxB，},,{94211xxxB，},,{75312xxxB定理：),,,,(krvb－设计必满足（1）vrbk（2）)1()1(vkr对于一个),,,,(krvb－设计，构造如下矩阵1B2B…bBbvvbvvbbvbbbbbbbbbxxxA21222211121121区组矩阵其中jijiijBxBxb01则（1）JIrAAT)(其中I为单位阵，J为全1矩阵（2）vb，如果vb，则称BIBD为对称的，这时rk例：},,,,,,{7654321xxxxxxxX6},,{4211xxxB，},,{5322xxxB，},,{6433xxxB，},,{7544xxxB，},,{1655xxxB，},,{2766xxxB，},,{3177xxxB。则（7，7，3，3，1）－对称设计对称BIBD的性质对称BIBD中任意两组都正好有个共同元素只须证kkAAT事实上AAAAAAAAAATTT)()(11AJIkA))(1JAAIk1)(kkkJIk)(如果vBBB,,,21是关于},,,{21vxxxX的对称BIBD，任取,iB则iviiiiiiBBBBBBBBBB\,\,\,\,\111是关于iBX\的BIBD。iviiiiiiBBBBBBBBBB,,,,,1121是关于iB的BIBD4.Hadamard矩阵定义：设,)(nnijnhH其中,11orhij如果nTnnnIHH则称nH为n阶Hadamard矩阵。例：1111111111111111,1111),1(421HHH7性质如果2n，并且nH为Hadamard矩阵，则4mod0n如果nnnijnmmmijmaHaH)()(,是Hadamard矩阵，则nnijmnHaH)(是m阶的Hadamad矩阵如果nH是Hadamard矩阵，则nnnnHHHH也是Hadamad矩阵规范Hadamard矩阵nH对称BIBD14,12,1nnn