组合计数与编码.ppt

* 组合计数与编码 ----by Logic 区组设计 区组设计主要研究某一有限集合是否存在满足一定条件的子集族并且构造这样的子集族。这种设计理论在实验设计、赛程安排及数字通信等许多种领域具有重要的作用。 概念介绍 设X是一个有限集合，则称X的子集族B={B1,B2,B3,...,Bb}，为X的一个区组设计，记作D=(X,B),X称作此设计的基集。 而子集族B中的每个子集Bi(i=1,2,3,...,b)称为此设计的区组。 基集X的元素个数|x|称为子集的阶。 对于区组Bi(i=1,2,3,...,b)中元素的个数|Bi|记为k。 对x∈X，B中含有x的区组的个数称为元素x的重复数，记为r(x)。 对于x,y∈X,且x≠y,B中包含{x,y}子集的区组个数称为x与y的相遇数,记为λ(x,y)。拭擦 均衡不完全区组设计(BIBD) 设有限集X={X1,X2,X3,...,Xv}, B={B1,B2,B3,...,Bb}是X的一个区组设计，若满足： |Bi|(i=1,2,3,...,b)=k,且kv。 X中每个元素在B子集族中出现r次。 X中每两个不同元素x,y相遇数都是λ。 则称B={B1,B2,B3,...,Bb}是参数为(b,v,r,k,λ)的均衡不完全区组设计 (Balanced Incompleted Block Design),记为BIBD(b,v,r,k,λ)。 例子：品尝实验 对于人的味觉来说，品尝的对象增加太多时鉴别差异的灵敏度便下降，因而每个人只能品尝一部分。 规定7个人(A,B,C,D,E,F,G)来品尝7种水果(a,b,c,d,e,f,g),每个人只限品尝3种。那么可进行如下设计： A B C D E F G 第一种 a b c d e f g 第二种 b c d e f g a 第三种 d e f g a b c 例子：品尝实验 我们把水果总数作为基集X，此时v=7;共有7人品尝，故b=7；每个人品尝到的水果种类集合就是每个区组，由于每人仅限品尝3种，那么k=3；每种水果被品尝3次，r=3；任意两种水果的组合在每个区组中只出现一次，λ=1。 故此设计是BIBD(7,7,3,3,1)。 其他例子 药物实验、田间实验：随着研究工作的发展，不论单因素还是多因素试验，供试处理数趋向于增多，尤其多因素试验。当然由于作物育种(药物研制)工作的发展，供试品种(系)数量迅速增加，因而单因素试验也需要扩展其容量。但增加处理数意味着要扩大区组，这在与实施局部控制原则是有矛盾的。区组变大意味着局部控制失效。因而在以往完全区组(complete block)，每一区组包含全套处理的基础上，发展出了不完全区组(incomplete block)的概念，即一套处理分成几个区组，或一个区组并不包含全部处理，但同样要通过区组实施地区控制，后来混杂的概念也被应用于单因素试验，从而发展出了一系列的不完全区组设计。 BIBD的最大优点在于可使区组不完全,因而,当每个区组实际可能安排的处理数(或品种数)少于供试处理时,仍可作出各处理间的正确比较；BIBD的缺点是区组数必须严格按规定数目设立,缺一不可,否则各处理之间的比较将失去均衡性。 基本性质 证明略。。。。。。。 基本性质 基本性质 由SBIBD构造BIBD 由SBIBD构造BIBD 拉丁方 拉丁方 简单的n阶拉丁方的构造方法想必大家都知道： 将1~n填入方阵第一行，从第二行开始每次将上一行的每个元素右移一格，将最右端的元素填入第一列即可。 但如果题目的要求中有约束条件(如USACO的5.4.1)，上述构造算法就不合适了，这时就需要采用有哪些信誉好的足球投注网站的方式。 正交拉丁方 三十六军官问题： 大数学家欧拉曾提出一个问题：即从不同的6个军团各选6种不同军阶的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军阶各不相同，应如何排这个方队？ 如果用(1，1)表示来自第一个军团具有第一种军阶的军官，用(1，2)表示来自第一个军团具有第二种军阶的军官，用(6，6)表示来自第六个军团具有第六种军阶的军官，则欧拉的问题就是如何将这36个数对排成方阵，使得每行每列的数无论从第一个数看还是从第二个数看，都恰好是由1、2、3、4、5、6组成。历史上称这个问题为三十六军官问题。 正交拉丁方 符合此问题要求的矩阵即为6阶正交拉丁方。 该问题已被证明无解，即6阶正交拉丁方不存在。 定义：设A=(aij),B=(bij)是两个n阶拉丁方，如果叠置后的n2个有序偶对(aij,bij)全部都互异，则拉丁方A和B就称为是正交的。 C=((aij,bij))n*n为正交拉丁方。