组合数学 教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版)

Slides:



Advertisements
Similar presentations
我们首先引入的计算概率的数学模型, 是在概率论的发展过程中最早出现的研究 对象,通常称为 古典概型.
Advertisements

一、模型与计算公式 二、基本的组合分析公式 三、概率直接计算的例子 第 1.3 节 古典概率 四、抽签与顺序无关 五、二项分布与超几何分布 六、概率的基本性质.
金融一班 王亚飞 王亚飞 王浩浩 王浩浩 吴海玥 吴海玥 我 连云港 的 家 乡 连云港 连云港,位于东经118°24′~119°48′和北纬 34°~35°07′之间,古称郁洲、海州,民国时称 连云市,建国后称新海连市,别称“港城”。东 西长129公里,南北宽约132公里,水域面积 平方公里。连云港市也是我国于1984年.
不知者無罪嗎 ? 【本報台北訊】國內知名大學胡姓研究 生進口豬籠草在網路上販售,涉嫌違反 植物防疫檢疫法,胡姓研究生表示不知 道豬籠草是違禁品並當場認錯道歉 台北地檢署檢察官念他初犯,昨 天處分緩起訴,但命他繳交六萬 元緩起訴處分金作公益。 豬籠草有潛移性線蟲寄生,一旦植物感 染後,輕則枯萎凋零,重則危害農業經.
配备计算机教室、多媒体教室、图书室、卫生室、 实验室、仪器室、音体美劳器材室、心理咨询室、少先 队活动室、教师集体备课室等专用教室。实验室、仪器 室全部按照省标准配备器材,演示实验开设率达 100% 。 学校现有图书 6050 册,生均 40 册。有一个 200 米环形跑 道的运动场地。 学校基本情况.
XX啤酒营销及广告策略.
長得像的圖形 設計者:嘉義縣興中國小 侯雪卿老師 分享者:高雄市中山國小 江民瑜老師 高雄市勝利國小 許嘉凌老師.
课例评析—— 《回乡偶书》和《渔歌子》 评课人:冯琴.
就作文本身而言,题目堪称“眉目”,是作文的“眼睛”,从某种程度上说,它是作文材料和主题的浓缩或概括。
中小学教育网课程推荐网络课程 小学:剑桥少儿英语 小学数学思维训练 初中:初一、初二、初三强化提高班 人大附中同步课程
回归教材、梳理知识、突出能力 ——2015年历史二轮复习思考 李树全 西安市第八十九中学.
施工招标案例分析 (交流材料).
3.1.1 随机事件的概率(一).
聚焦文化竞争力.
文化创新的途径.
7.4 用矩阵初等行变换 解线性方程组 主要内容: 一.矩阵的行初等变换 二.用行初等变换求逆矩阵 三.用矩阵法求线性方程组.
職務法庭與 法官退場機制 行政訴訟及懲戒廳報告
2009—2010学年第一学期 小学品德与社会课程教学监控情况分析 潘诗求 2010年3月
15世纪欧洲人绘制的世界地图.
概其要、析其理 ——议论文事实论据修改 昌平二中 王丽娟
新课程背景下高考数学试题的研究 ---高考的变化趋势
“悦”读,飞越 “考场” 心神飞越 温州中学 郑可菜.
第7课 新航路的开辟 第7课 新航路的开辟.
股票、债券、和保险 投资理财的话题.
确定位置 执教者:刘霞.
湖南师大附中高三政治第二次月考 试题讲评 试题讲评.
06学年度工作意见 2006年8月30日.
初中语文总复习 说明文 阅读专题 西安市第六十七中学 潘敏.
忠孝國小自立午餐老師的叮嚀 教師指導手冊.
电阻 新疆兵团四师76团中学.
外貌和能力哪个更重要.
关于《福建省房屋建筑和市政基础设施工程 标准施工招标文件(2015年版)》的要点介绍
从此,我不在沉默寡言 那一刻 就在这一刻 世上还有爸爸好 我 长 大 了 张绅 4 文苑芬芳
第一章 体育统计的基本知识 主讲教师:王丽艳 徐栋.
常用逻辑用语 第一章 “数学是思维的科学” 逻辑是研究思维形式和规律的科学. 逻辑用语是我们必不可少的工具.
从容行走,优雅为师 江苏省梁丰高级中学 任小文
“08高考化学学业水平(必修科目)测试的命题和教学对策研究”
离散数学 Discrete mathematics
觀察內容: 時間 作息 觀察內容 9:30~9:40 角落分享
屏東縣105年度 友善校園事務與輔導工作- 國中適性輔導工作專業知能研習(初階課程) 桌遊在班級經營與學生輔導 之應用與連結
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
北师大版七年级数学 5.5 应用一元一次方程 ——“希望工程”义演 枣庄市第三十四中学 曹馨.
運輸與空間的交互作用 運輸發展的階段 一、分散的港口 二、侵入路線 三、發展支線 四、初步相互連結 五、完全相互連結 六、高度優越的幹線
导入 21世纪教育网经纬社会思品工作室制作 我们可以通过哪些媒介(途径)获知这些消息?.
穩定是指偏離平衡時能夠回復平衡的特性,控制則是改變飛行狀態的機制。
普及组近5年NOIP试题分析 安徽师大附中 叶国平.
专题研讨课二: 数组在解决复杂问题中的作用
海洋存亡 匹夫有责 ——让我们都来做环保小卫士 XX小学三(3)班.
高考前复习迎考的建议(一).
新课标高考考试大纲解读及备考建议 西安高新一中 郭小平
Chapter 13 數論基礎.
第八章 欧氏空间 8.1 向量的内积 8.2 正交基 8.3 正交变换 8.4 对称变换和对称矩阵.
第二部分 免疫系统与免疫活性分子 第二章 免疫系统 第三章 免疫球蛋白 第二 部分 第五章 细胞因子 第四章 补体系统.
第6章 管理信息系统的系统设计 系统分析阶段,主要解决的是新系统“做什么”的问题。而在系统设计阶段,需要回答的中心问题是“怎么做”,即通过给出新系统物理模型的方式,描述如何实现在系统分析中规定的系统功能。
数学归纳法及其应用举例 安徽师大附中 吴中才.
学习中苦多?乐多? ——高二(1)班主题班会.
离散数学-计数技术 南京大学计算机科学与技术系
概率论 ( Probability) 2016年 2019年4月15日5时31分.
第九章 數論基礎.
1.3 算法案例 第一课时.
第七章  事业单位支出的核算      §第一节  支出概述     §第二节  拨出款项     §第三节  各项支出     §第四节  成本费用.
作业要求: 作业要及时完成,及时提交。 作业(网络作业、期中作业)要计入总分。 学习过程中的问题,可通过网上答疑系统提出。 考试说明:
第三章 行列式 第一节 线性方程组与行列式 第二节 排列 第三节 n阶行列式 第四节 余子式与行列式展开 第五节 克莱姆规则.
介入及追蹤紀錄表 編號: 姓/稱謂: 初次103年 月 日 追蹤 月 日 問題型態 (可複選) □ 1. 覺得西藥都很傷胃
第13课 东汉的兴亡.
繁星推薦系統 楊曉婷 副理 教育的服務 是我們的責任.
單元主題名: 大家都是好朋友 設計者:柯淑惠、林雨欣.
1.2.3 循环语句.
数列求和 Taojizhi 2019/10/13.
第四章 线性方程组 4.1 消元法 4.2 矩阵的秩 线性方程组可解的判别法 4.3 线性方程组的公式解 4.4 结式和判别式.
Presentation transcript:

组合数学 教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版) 参考:1. 卢开澄, 组合数学,清华大学出版社 2. 吴文虎等, 程序设计中的组合数学, 清华大学出版社 网络教室: 组合数学 计算机学院软件所:王贵珍 Tel: 13167532629 Email:gzwang@bit.edu.cn Address: 中心教学楼905#

Motorola Internal Use Only 课 程 安 排 课程特点及最后成绩 1. 课程特点:技巧性较强。 2. 成绩评定:作业、程序设计占30%,期末为闭卷笔试考试,成绩占70%。  提示: 技巧的应用来自于经验的积累,所以 解决的组合数学问题越多,那么能够解决下 一个组合数学问题的可能性就越大。 预达目标: 高—— 中—— 低—— Motorola Internal Use Only

组合数学研究的内容 离散结构的存在、计数、分析 和优化。

例:棋盘的完美覆盖 m×n棋盘: m行n列方格, b-牌:1行b个的方格条 m×n棋盘被b-牌的一个完美覆盖是 (1) 每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格. 34棋盘 66棋盘有4-牌的完美覆盖吗? 有2-牌的完美覆盖. 定理: m×n棋盘有b-牌的完美覆盖b|m或b|n.

棋盘覆盖及其变化 1 2 3 4 66棋盘用1,2,3,4如图填数,4牌在任何位置都覆盖1,2,3,4,去掉成组的1234, 多余1124。所以66棋盘不能用4牌完美覆盖。

完美覆盖 变化: 带禁止方格, 用多米诺牌(2-牌)覆盖 4×4棋盘去掉2格 4×5棋盘去掉4格 用多米诺牌(2-牌)覆盖 用多米诺牌覆盖

例:Nim取子游戏 设有k1堆硬币,各堆分别含有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,15): (100,389): (7,12,13): 平衡态 非平衡态 非平衡态

平衡态与非平衡态的转化 n1 = a1s a1(s-1) … a11 n2 = a2s a2(s-1) … a21 nk = aks ak(s-1) … ak1 … … … … … Label = cs c(s-1) … c1 (7,8,15):平衡态 (100,389):非平衡态 (7,8,13):非平衡态 游戏终止时是平衡态 平衡态不能经一轮取子达到平衡态 非平衡态可经一轮取子达到平衡态(?)

结论 定理: 若游戏非平衡, 则游戏人I有必胜策略; 若游戏平衡, 则游戏人II有必胜策略. 定义: 若n1,n2,…,nk二进展开第i位的和是奇数, 则称第i位是非平衡位. 命题: 设一游戏最大非平衡位是第j位, 则 游戏人I可以从某堆取币使游戏达到平衡态 当且仅当 该堆币数二进展开第j位是1. 注意比较与习题1.33叙述的差别.

拉丁方 定义: 若A是由n个元素构成的n阶方阵, 其中每个元素在每行每列各出现一次, 则称A是拉丁方. 设A=(aij), 每个元素每行(列)只出现一次: aij=aik  j=k ( aji=aki  j=k )

36名军官问题 (18世纪)36军官问题: 6个地区, 6种军衔各一名. 将这36名军官排成6×6方阵, 使得 1)每行每列都有任一地区的军官; 2)每行每列都有任一军衔的军官. i :军衔, j :地区, 军官对应数偶(i, j), i, j[0,5] 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次. 传说普鲁士皇帝菲特烈喜欢阅兵

正交拉丁方 定义:设A=(aij)n×n,B=(bij)n×n是两个n×n拉丁方. 令C=((aij, bij))n×n,若C的n2对数偶互不相同, 则称A与B正交. 36军官问题等价于构造两个正交的6阶拉丁方. 例: 3阶正交拉丁方

正交拉丁方的实际意义 正交的拉丁方的一个应用: 药物配合试验 三种治发烧药和三种治感冒药, 对三位病人试验, 要求三天内每人都服这几种药, 比较配合疗效. 这时就可用上面讨论过的3阶正交拉丁方. 行:人, 列:天 (i,j): i,发烧药 j, 感冒药

Euler的猜测 令N(n)为两两正交的n阶拉丁方的最大个数. N(1)=2, N(2)=1, N(3)=2 定理2: 若n=pa, p是素数,a>0, 则N(n)=n-1. 定理3: 若n是奇数, 则N(n)2. 定理4: 若N(m)2,N(n)2, 则N(mn)2.(自学) 推论: 若n2且n4k+2, k0, 则N(n)2.(?) Euler(1707~1783)猜测: 对任意n=4k+2, k0, N(n)=1. 这4个结论的证明并不需要太复杂的数学知识.

Euler猜测的解决 1900年 Tarry(法) 验证了N(6)=1. 1959年 Parker(美) 证明 N(10)2. 1959年 Bose(印), Parker, Shrikhande(印) 证明 N(4k+2)2, 任意k>1.

N(n)  n-1 定理1: n>1, N(n)  n-1. 即若A1,A2,…,Ak是MOLS (两两正交拉丁方), 则必有 kn-1. 置换的定义与表示: 置换: 有限集(例如{1,2,…,n})上的一一对应. 表示: p(1)=a1, p(2)=a2,…, p(n)=an, 注: a1a2…an是1,2,…,n的一个排列 则以 来表示该置换

置换 设 p是{1,2,…,n}上一置换, A=(aij)nn是矩阵, aij {1,2,…,n} 定义 p(A)= ( p(aij) )nn , 例: 2 3 1

p(A)性质讨论 若A是拉丁方, p是置换, p(A)是拉丁方吗? p(i)在每行每列只出现一次. 2. 若A是拉丁方, 则A与p(A)是否正交? A与p(A)组成的数偶只有: (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) 互不相等. 所以 kn-1.

观察 p=5,k=1 p=5,k=2 p=5,k=3 p=5,k=4 每行分别左移1,2,3,4格 p阶方阵A1,A2,…,Ap-1: Ak=(aij(k))p×p, k=1,2,…,p-1. aij(k)=k·i+j mod p, i, j[0,p-1] 定理: 设p为素数, 则N(p)=p-1. p=4, k=2

定理: 设p为素数, 则N(p)=p-1. 证明:Ak=(aij(k))p×p, k=1,2,…,p-1. aij(k)=k·i+j mod p, i,j= 0,1,…,p-1 先证Ak是拉丁方: aij(k) = ait(k)jt mod pj=t aij(k) = asj(k)k(i-s)0 mod pi=s 再证Ag,Ah正交: 若(aij(g),aij(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 pi=r j=s 得证. key: a·b=0 mod p  a=0或b=0mod p. ( p=4? )

定理2: n=pa, p素数,a>0  N(n)=n-1 定义: 设集合F对可交换运算+和封闭, 满足 (1) <F,+>是群(记其么元为0), (2) 乘法分配律: a(b+c)=ab+ac (3) <F,>是半群, (4) 消去律: ab=0  a=0或b=0. 则称<F,+,>是一个域. F有限:有限域(Galois域GF) 注: (3)+(4)等价于<F\{0},>是群. 命题: 若n阶有限域存在, 则N(n)=n-1. 定理: p素数,a正, pa阶GF存在. GF的阶是素数幂. 这里的两个定理不用证明.

GF的构造方法 以GF(n)记n阶有限域. 对素数p, GF(p)=<{0,1,…,p-1}, + mod p,  mod p> 对a>0, 取a阶多项式xa+c1xa-1+…+ca, 满足: 各次项系数取值于GF(p) 没有根在GF(p)上 记其任一个根为, 令 F={b0+b1+…+ba-1a-1 : b0,b1,…,ba-1[0,p-1]} 则GF(pa)=<F, + mod p,  mod p >.

举例:阶为22的有限域 p=2,a=2 GF(p)= GF(2)=Z2=<{0,1}, + mod 2,  mod 2>, 取a阶多项式为x2+x+1, 令为方程x2+x+1 =0的根, F(pa)=F(4)={b0+b1 |b0,b1 {0,1}} ={0,1, , 1+} 所以<{0, 1, , 1+}, + mod 2,  mod 2>是域.

举例:阶为22的有限域 GF(4)=<{0, 1, , 1+}, + mod 2,  mod 2>是域. 其中为方程x2+x+1 =0的根 加法表: 乘法表: 0 1  1+ 1  1+ 0 1  1+ 1  1+ 0 0 0 0 0 1  1+   1+ 1+  1 1  1+  1+ 1 1+  1  1+ 1  1

举例:阶为33的有限域 GF(3)=Z3={0,1,2},令为x3+2x+1=0的根,令 F={a + b  + c 2 : a,b,cZ3} <F, + mod 3,  mod 3>是27阶有限域. 例: (1+ 22) =  + 23=  + 2 + 4 = 1. (2 +  + 22)(1 + 2)=1.

利用有限域构造MOLS举例 回顾 Ak=(aij(k))n×n, aij(k)=k·i+j mod p, 设有n阶有限域< F={0, b1, … , bn-1} , +, >, 则Ak=(aij(k))n×n, k=1,…,n-1, aij(k)=bkbi+bj , 其中b0=0, i, j[0,n-1] A1= A2= A3=

作业 第一章P13:2, 4,30, 36. 第十章P387:17, 46. 编程题:nim和nim2 每章都交作业