1、1,組合數(shù)學(xué),第十三講,區(qū)組設(shè)計(jì),2,第十三講: 內(nèi)容提要,Kirkman 15女生問(wèn)題 區(qū)組設(shè)計(jì)概論 平衡不完全的區(qū)組設(shè)計(jì) 阿達(dá)瑪(Hadamard)矩陣,3,區(qū)組設(shè)計(jì)理論是組合數(shù)學(xué)的一個(gè)重要分支. 它主要研究某一有限集合的滿足一定條件的子集族的存在性問(wèn)題, 構(gòu)造問(wèn)題. 歷史上是先有一些著名的區(qū)組設(shè)計(jì)的例子, 然后才有區(qū)組設(shè)計(jì)的一般理論. 例如Euler 36軍官問(wèn)題, 正交拉丁方問(wèn)題, 都是這方面例子.,1. 引 言,4,另一個(gè)很著名例子是Kirkman 15女生問(wèn)題. 這些問(wèn)題的研究在一定程度上推動(dòng)了組合設(shè)計(jì)理論的發(fā)展. 這些問(wèn)題的原始形式雖然僅僅表現(xiàn)為趣味數(shù)學(xué)問(wèn)題, 但是對(duì)這些問(wèn)題不斷

2、深入研究, 不僅發(fā)展了組合設(shè)計(jì)理論, 而且發(fā)現(xiàn)了越來(lái)越廣泛的應(yīng)用. 設(shè)計(jì)理論在實(shí)驗(yàn)設(shè)計(jì), 競(jìng)賽安排及數(shù)字通訊等許多領(lǐng)域中均具有重要應(yīng)用.,5,1847年Kirkman提出了下面這樣一個(gè)有趣的組合數(shù)學(xué)問(wèn)題：有一個(gè)女教師, 每天要帶領(lǐng)一個(gè)班的15名女生去散步. 問(wèn)能否設(shè)計(jì)一種連續(xù)一周的散步方案, 使得每天散步的時(shí)候, 15名女生都能分成5組, 每組由3名女生組成, 而且在7天里每一個(gè)女生和其他女生都要在同一組中出現(xiàn)一次而且只出現(xiàn)一次?,2. Kirkman 15女生問(wèn)題,6,簡(jiǎn)單分析一下, 要求解這個(gè)問(wèn)題就是要找到滿足下面條件的三元子集組: (1) 需要構(gòu)造由15名女生組成的集合的75=35個(gè)三元

3、子集族, 使得每?jī)蓚€(gè)女生在三元組里正好出現(xiàn)一次. (2) 由于在每天的散步中, 每個(gè)女生出現(xiàn)而且只能出現(xiàn)在一個(gè)三元組中. 所以, 必須能將35個(gè)三元組分成7部分, 每部分有5個(gè)三元組. 每一個(gè)女生正好在每部分出現(xiàn)一次, 即在一個(gè)三元組出現(xiàn).,7,1850人們得到了這個(gè)問(wèn)題的解: 星期一: 1,2,3, 4,8,12, 5,10,15, 6,11,13, 7,9,14; 星期二: 1,4,5, 2,8,10, 3,13,14, 6,9,15, 7,11,12; 星期三: 1,6,7, 2,9,11, 3,12,15, 4,10,14, 5,8,13; 星期四: 1,8,9, 2,12,14, 3

4、,5,6, 4,11,15, 7,10,13;,8,星期五: 1,10,11, 2,13,15, 3,4,7, 5,9,12, 6,8,14; 星期六: 1,12,13, 2,4,6, 3,9,10, 5,11,14, 7,8,15; 星期日: 1,14,15, 2,5,7, 3,8,11, 4,9,13, 6,10,12. 這就是典型的區(qū)組設(shè)計(jì)問(wèn)題, 尋找滿足某種條件的區(qū)組設(shè)計(jì)方案的存在性.,9,設(shè)X是一個(gè)有限集合, 則稱X的子集族B=B1,B2,Bb為X的一個(gè)區(qū)組設(shè)計(jì), 記作D=(X,B). X稱為此設(shè)計(jì)的基集, 而子集族B中諸子集Bi(i=1,2,b)則稱為此設(shè)計(jì)的區(qū)組. 基集X中元素的

5、個(gè)數(shù)|X|稱為設(shè)計(jì)的階. 對(duì)于i=1,2,b, 區(qū)組Bi的元素個(gè)數(shù)|Bi|又稱為該區(qū)組的長(zhǎng)度.,3. 區(qū)組設(shè)計(jì)概論,10,對(duì)于xX, B中含有x的區(qū)組的個(gè)數(shù)稱為元素x的重復(fù)數(shù), 記為r(x). 對(duì)于x, yX, xy, B中的包含子集x,y的區(qū)組的個(gè)數(shù)稱為元素x和y的相遇數(shù), 記為(x,y). 需要指出的是, 區(qū)組族B中的區(qū)組是可以重復(fù)的, 因此這是一個(gè)族, 而不是一個(gè)集. 一般族都允許重復(fù), 集合不允許重復(fù).,11,區(qū)組設(shè)計(jì)可用一個(gè)所謂的關(guān)聯(lián)矩陣來(lái)描述. 設(shè)X=x1,x2,xv, B=B1,B2,Bb, 其關(guān)聯(lián)矩陣定義為一個(gè)vb階矩陣 A=(aij)vb, i=1,2,v; j=1,2,b,

6、 其中,12,容易看出: 第i行出現(xiàn)1的個(gè)數(shù)=r(xi), 是xi的重復(fù)數(shù), 第j列出現(xiàn)1的個(gè)數(shù)是第j個(gè)區(qū)組Bj的長(zhǎng)度(容量). 第j列可以看作是Bj的特征函數(shù). 那么r(xi,xj)=? 第i行與第j行的內(nèi)積. 顯然, 關(guān)聯(lián)矩陣行列的交換相當(dāng)于基集元素次序和區(qū)組次序的改變,本質(zhì)上表示同樣的區(qū)組設(shè)計(jì).,13,這些概念似乎很復(fù)雜, 其實(shí)并不復(fù)雜. Kirkman 15女生設(shè)計(jì)的具體參數(shù): (i) 設(shè)計(jì)的階數(shù)=15 (ii) 每個(gè)區(qū)組長(zhǎng)度=3 (iii) 任意一個(gè)元素的重復(fù)數(shù)=7 (iv) 任意兩個(gè)元素相遇數(shù)=1 區(qū)組總數(shù)35 其實(shí)這些參數(shù)并不是獨(dú)立的, 一些可 以由另外一些算出來(lái).,14,(Ba

7、lanced Incomplete Block Design, BIBD) 定義1 設(shè)X=x1,x2,xv, B1,B2,Bb是X的b個(gè)k-子集，如果滿足: (1) X中每個(gè)元素的重復(fù)數(shù)都是r; (2) X中每?jī)蓚€(gè)不同的元素x, y的相遇數(shù)都是D(x,y)=； (3) kv, 則稱B=B1,B2,Bb是有參數(shù)(b,v,r,k,)的平衡不完全區(qū)組設(shè)計(jì), 簡(jiǎn)稱BIBD(b,v,r,k,).,4. 平衡不完全區(qū)組設(shè)計(jì)(BIBD),15,例 X=x1,x2,x9，則一個(gè)BIBD(12,9,4,3,1)設(shè)計(jì)為,16,關(guān)聯(lián)矩陣為,17,為了排除平凡情況, 總假設(shè)k1, 從而0. 定理1 設(shè)k1, D=(X

8、,B)是一個(gè)BIBD(b,v,r,k,)，則有 (1) X中所有元素的重復(fù)度都等于,(2) B中所含的區(qū)組總數(shù),18,定理：一個(gè)vb的0，1矩陣A=(aij)是某個(gè)BIBD (b,v,r,k,)的關(guān)聯(lián)矩陣當(dāng)且僅當(dāng)下述條件成立： (1) A的每一列之和為k； (2) AAT=(r-)Iv+Jv 其中Iv為v階單位矩陣，Jv為所有元素為1的v階 矩陣。,證明: (必要性),19,(充分性) 令,則 由(1)知 |Bj|=k， 由(2)知，每個(gè)xi恰好在r個(gè)Bj里， 而每一對(duì)(xp, xq)(pq)恰好出現(xiàn)在個(gè)Bj中， 所以 B1,B2,Bb是一個(gè)BIBD(b,v,r,k,) 且A是它的關(guān)聯(lián)矩陣,2

9、0,定理2 如果存在BIBD(b,v,r,k,), 其中k1, 則必然有 (v-1)0(mod (k-1), (I) v(v-1)0(mod k). (II) 在BIBD的研究中, 存在性問(wèn)題是最根本的問(wèn)題. 剛才定理中給出了存在BIBD(b,v,r,k,)的必要條件, 但是這些條件并不是充分的. 1967年M. Hall提出了如下的猜想.,21,設(shè)計(jì)存在性猜想: 給定正整數(shù)k, , 對(duì)于滿足上述定理中條件(I), (II)的正整數(shù)v, 除去有限個(gè)例外, 一定存在BIBD(b,v,r,k,). Wilson在1975年證明了下面的漸近存在性定理, 從而證明了這個(gè)猜想. 漸近存在性定理: 給定正

10、整數(shù)k與, 存在常數(shù)v0=v0(k, ), 使得當(dāng)vv0時(shí), 只要v滿足上述定理中的條件(I), (II), 則一定存在BIBD(b,v,r,k,).,22,對(duì)于設(shè)計(jì)而言, 怎樣的一組參數(shù)存在相應(yīng)的BIBD是最重要的問(wèn)題. 并不是滿足這些必要條件就一定存在那樣的BIBD. 可以證明不存在BIBD(8,16,3,6,1)及BIBD(14,21,4,6,1). 下面是Fisher給出的另外一個(gè)存在BIBD(b,v,r,k,)的必要條件. 定理3 如果存在BIBD(b,v,r,k,), 1kv, 則區(qū)組總數(shù)bv, 或者等價(jià)地有(v-1) k(k-1).,23,對(duì)稱BIBD(記為SBIBD),定義：如

11、果在BIBD(b,v,r,k,)中有b=v，則稱它 為對(duì)稱的均衡不完全區(qū)組設(shè)計(jì)。,顯然，當(dāng)b=v時(shí)，k=r，所以，把對(duì)稱的均衡不完全區(qū)組設(shè)計(jì)簡(jiǎn)記為SBIBD(v,k,).,例 X=1,2,3,4,5,6,7，則SBIBD(7,3,1)為,B1=1,3,7,B2=1,2,4,B3=2,3,5,B4=3,4,6,B5=4,5,7,B6=1,5,6,B7=2,6,7,24,定理 若A是SBIBD(v, k, )的關(guān)聯(lián)矩陣，則有 (1) AAT=(k- )Iv+ Jv=ATA; (2) AJv=kJv=JvA； (3) 如果v是偶數(shù)，則k-是完全平方數(shù)。,定理 SBIBD的任意兩組都正好有個(gè)共同的 元

12、素。,25,區(qū)組設(shè)計(jì)的構(gòu)成,定理 設(shè)B1,B2,Bb是集合X=x1,x2,xv上 的BIBD(b,v,r,k,)，令Bi=X-Bi, i=1,2,v，則 B1,B2,Bb是集合X上的BIBD(b,v,r,k,), 其中r=b-r,k=v-k, =b-2r+.,定理 設(shè)B1,B2,Bv是集合X=x1,x2,xv上 的SBIBD(v,k,)，令Bi=Bi-Bv, i=1,2,v-1，則 B1,B2,Bv-1是集合X-Bv上的 BIBD(v-1, v-k, k, k- , ).,26,BIBD(b,v,r,3,)稱為Steiner三元系. 根據(jù)BIBD存在的必要條件, 得到三元系存在必要條件是: 3

13、b=rv, 2r=(v-1) 或改寫(xiě)為: r = (v-1)/2, b=v(v-1)/6 r和b是整數(shù), 故 v(v-1)0(mod 6), (v-1)0( mod 2) =1時(shí)又稱為Kirkman三元系, 即(v,3,1)-設(shè)計(jì).,27,阿達(dá)瑪矩陣在區(qū)組設(shè)計(jì)和編碼理論等方面都有很大用處, 它對(duì)于形成對(duì)稱的BIBD有著重要的作用，而對(duì)稱的BIBD又關(guān)系到一般的BIBD的形成. 所謂n階的阿達(dá)瑪矩陣Hn指的是以1或-1作為元素并滿足 HnHnT=nIn 的nn方陣.,5. Hadamard矩陣,28,定理5 n2,Hn是阿達(dá)瑪矩陣的必要條件是n0(mod 4). Hadamard矩陣猜想: 對(duì)于任意正整數(shù)t, 都存在4t階的Hadamard矩陣. 這個(gè)猜想的討論是Hadamard矩陣?yán)碚摰囊粋€(gè)中心問(wèn)題. 但到現(xiàn)在這個(gè)猜想還沒(méi)有獲得證明, 也沒(méi)有獲得反例. 目前對(duì)n=4t400的情況, 都確定了n階H-矩陣的存在性.,29,經(jīng)常稱一個(gè)(4t-1, 2t-1, t-1)-SBIBD