chap1組合數(shù)學(xué)

1、組合數(shù)學(xué),2011.11,教材與參考書,教材: R. A. Brualdi, 《組合數(shù)學(xué)》, 機械工業(yè)出版社(中譯第4版)參考:盧開澄, 《組合數(shù)學(xué)》(第4版),清華大學(xué)出版社,課程特點,研究內(nèi)容：離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化。技巧的應(yīng)用來自于經(jīng)驗的積累，所以解決的組合數(shù)學(xué)問題越多，那么能夠解決下一個組合數(shù)學(xué)問題的可能性就越大。結(jié)合數(shù)論思考問題,課程內(nèi)容簡介,鴿巢原理 (例 Ramsey定理) 排列組合 容斥原理

2、 (例 Euler函數(shù)) 遞推關(guān)系與生成函數(shù) 二分圖匹配 組合設(shè)計 Polya計數(shù)定理 (例: 圓排列),例:棋盤的完美覆蓋,m×n棋盤: m行n列方格, b-牌:1行b個的方格條m×n棋盤被b-牌的一個完美覆蓋是b-牌在棋盤上的一個排列, 滿足:(1) 每個格子恰好只被一張牌覆蓋;(2) 每條b-牌覆蓋b個方格.,定理: m×n棋盤有b-牌的完美覆蓋?b|m或b|n.,3?4

3、棋盤6?6棋盤有4-牌的完美覆蓋嗎?,有2-牌的完美覆蓋.,棋盤覆蓋及其變化,6?6棋盤用1,2,3,4如圖填數(shù)，4牌在任何位置都覆蓋1,2,3,4，去掉成組的1234, 多余1124。所以6?6棋盤不能用4牌完美覆蓋。,完美覆蓋,變化: 帶禁止方格, 用多米諾牌(2-牌)覆蓋,轉(zhuǎn)化為二分圖, 應(yīng)用二分圖匹配算法. 2?n棋盤用2-牌覆蓋有多少種方案? 3?2n棋盤用2-牌覆蓋有多少種方案?,例:Nim取子游戲,設(shè)有k?1堆硬幣

4、,各堆分別含有n1,n2,…,nk枚硬幣.游戲規(guī)則:(1)兩游戲人交替取子;(2)每人在一次取子時只能取一堆中的硬幣, 取至少一枚,至多全堆硬幣;(3)所有堆都變成空堆時, 游戲結(jié)束, 最后取子的人獲勝.例1. (100, 389)例2. (7, 8, 15),游戲人I有必勝策略,游戲人II有必勝策略,平衡態(tài),設(shè)有游戲(n1,n2,…,nk), 且各數(shù)的二進制展開是 ni=aisai(s-1

5、)…ai1, i=1,2,…,k若 a11+a21+…+ak1 (各數(shù)第1位之和), … a1s+a2s+…+aks (各數(shù)第s位之和)都是偶數(shù), 則稱游戲處于平衡態(tài).,(7,8,15): (100,389): (7,12,13):,平衡態(tài),非平衡態(tài),非平衡態(tài),平衡態(tài)與非平衡態(tài)的轉(zhuǎn)化,(7,8,15):平衡態(tài)(100,389):非平衡態(tài)

6、(7,8,13):非平衡態(tài),游戲終止時是平衡態(tài) 平衡態(tài)不能經(jīng)一次取子達到平衡態(tài) 非平衡態(tài)可經(jīng)一次取子達到平衡態(tài)(?),取子目標(biāo)分析,堆1: 1 0 0 目標(biāo): 0 1 0,堆2: 1 0 1 目標(biāo): 0 1 1,堆3: 1 0 0 0 目標(biāo): 1 1 1 0,堆4: 1 1 1 1 目標(biāo): 1 0 0 1,命題: 可從某堆取幣到平衡態(tài) 當(dāng)且僅當(dāng) 其最大非平衡位是1. (比較習(xí)題1.33

7、),結(jié)論,游戲終止時是平衡態(tài) 平衡態(tài)不能經(jīng)一次取子達到平衡態(tài) 非平衡態(tài)可經(jīng)一次取子達到平衡態(tài)定理: 若游戲非平衡, 則游戲人I有必勝策略; 若游戲平衡, 則游戲人II有必勝策略.,拉丁方,定義: 若A是由n個元素構(gòu)成的n階方陣, 其中每個元素在每行每列各出現(xiàn)一次, 則稱A是拉丁方.設(shè)A=(aij), 每個元素每行(列)只出現(xiàn)一次:

8、 aij=aik ? j=k ( aji=aki ? j=k ),36名軍官問題,(18世紀)36軍官問題: 6個地區(qū), 6種軍銜各一名.將這36名軍官排成6×6方陣, 使得 1)每行每列都有任一地區(qū)的軍官; 2)每行每列都有任一軍銜的軍官.i :軍銜, j :地區(qū), 軍官對應(yīng)數(shù)偶(i, j), i, j?[0,5]問題等價于構(gòu)造數(shù)偶(i,j)排成的6階方陣, 使得 1) 數(shù)偶第一個數(shù)字構(gòu)成拉丁

9、方; 2) 數(shù)偶第二個數(shù)字構(gòu)成拉丁方; 3) 每個數(shù)偶只出現(xiàn)一次.,正交拉丁方,定義:設(shè)A=(aij)n×n,B=(bij)n×n是兩個n×n拉丁方. 令C=((aij, bij))n×n,若C的n2對數(shù)偶互不相同, 則稱A與B正交.36軍官問題等價于構(gòu)造兩個正交的6階拉丁方.例: 3階正交拉丁方,正交拉丁方的實際意義,正交的拉丁方的一個應(yīng)用

10、: 藥物配合試驗三種治發(fā)燒藥和三種治感冒藥, 對三位病人試驗,要求三天內(nèi)每人都服這幾種藥, 比較配合療效.這時就可用上面討論過的3階正交拉丁方.,行:人, 列:天(i,j): i,發(fā)燒藥 j, 感冒藥,Euler的猜測,令N(n)為兩兩正交的n階拉丁方的最大個數(shù). N(1)=2, N(2)=1, N(3)=2定理1: 若n>1,則N(n)?n-1.定理2: 若n=pa, p

11、是素數(shù),a>0, 則N(n)=n-1.定理3: 若n是奇數(shù), 則N(n)?2.定理4: 若N(m)?2,N(n)?2, 則N(mn)?2.(自學(xué))推論: 若n?2且n?4k+2, k?0, 則N(n)?2.(?)Euler(1707~1783)猜測: 對任意n=4k+2, k?0, N(n)=1.,Euler猜測的解決,1900年 Tarry(法) 驗證了N(6)=1.1959年 Park