组合数学-第十三节：相异代表系.docxVIP

PAGE PAGE # 第7章相异代表系 7.1引论 我们先来看一个例子。现有 6名职员x1,x^|x6和6项工作y,,y^( y6，每个职员适合做某些工作而不适 合做另外一些工作。为了方便，在图，如何把它找到？如果这种安排不存在，那么对多少人能做合适的安 排？ V】 2 力 yt 乂 眺 1 % % % 勿 i % % 在第5章中，我们把它看成是有限制位置的排列问题，使用容斥原理及棋子多项式可以求出合适安排的方 法数。但是，它仅仅是计数，对于如何找到合适的安排不能提供任何信息。 在本章中，我们将按照一种完全不同的方法来研究并解决这个问题。 在前面的问题中，所谓合适的安排，就是在无阴影的部分里不同行、不同列选 6个方块的一种方法。如果 把每行无阴影方块的横坐标写成集合，那么 A *%山 A *1肆3,小5】 A4 - l yi, y3, y6 匚 yud 氏+3、*、y^ 如果能从每个集合中选出一个元素，而且 6个元素两两互不相同，就得到了一种合适的安排。遗憾的是, 对于这里的 Ai,AH||A6而言，这样的选择不存在。这是因为，无论 Ai,As, A5选出的是yi,y2,y6，还是 y2, y6,yi, A4都没有合适的元素可选。 7.2相异代表系 令A, A III An是集合E的n个子集。E的n个元素^?，川宀，其中，e 人2,川耳己A，称为 是集族「A,AlHAn?的一个代表系。如果集族的代表系中的元素两两互不相同， 则称该代表系为集族的相 异代表系。 例如，4, 1, 4，3 是 A,「1,4?,A2「1,2,3 二 A3 =「3,4,5?, A —3,4,5?的代表系，而 1, 2，3，4 和 4， 2，3，5是认，Az, 4,人？的相异代表系。 非空集合A,, AJ1I人构成的集族一定有代表系，但不一定有相异代表系。例如， A —1,4二A —1,2,3,4,5 1, A —4,几 —1,4,就没有相异代表系。直观上看，是因为 AU AbU乓中 的元素太少。如何把感性认识上升到理论高度，找出集族有相异代表系的充要条件是本节的任务。 假设即今,川釣是集族｛人，4川代｝的相异代表系，对于｛1,2，川n｝有2n -1个非空子集，故这种必要条 件有2n -1个。 1935年，P.Hall提出将这2n -1放在一起就是集族〈人，人|||人？有相异代表系的充分条件。 定理7.2.1 集族认，人川人，有相异代表系，当且仅当对每个k=1,2川In和每种选择 i1,i2JI|ik 1斗 叮2 ：：：11丨5冬n ，集族满足 flKU …UAkk 证明 由前面的分析，必要性是显然的。下面通过对 n进行归纳来证明充分性。 当n =1时，由定理的条件知 A兰1，即A是非空集合。任取 A的元素，就是｛ A ｝的相异代表系。 设对任何m ：：：n, 3,A2,IHAj满足定理的条件，则该集族有相异代表系 即初川，琳。 现假设集族Ia’AzIHAJ满足定理的条件，我们将分两种情况讨论： （1 ）对于任何 k（1兰k兰n —1），选择1兰h vi2 v||| ik兰n均满足 AAJA^^JAk? k + 1，由于 A，AJHAn满足定理的条件，于是 A -1仁i岂n。任取en ? An，构造集族 A - 6 f , A? -: e*』,| H , An 4 - e* / 匚 则对于任意1乞k乞n -1和1 _ i :：: i2 ：：：川：：：ik _ n -1，有 （A -心叽他-?｝）U…U（A -｛耳｝） =（A CKUAk ）-?｝ A A1 U A2 U Ak, -1 _k 即该集族满足定理的条件，由归纳假设知它有相异代表系 （e,e2^|e1JL，且e ^en^i n-1）。从而 e ,e2川|en」,en就是A, AJHAj的相异代表系。 （2）对某个 P（1 兰 P 兰n—1）及某种选择「2,…,ip（1 Eh ci? 兰n U A2U…U Ap： = P，不 失一般性，我们假设这p个集合是A1,A2H|AP，则AjjA^-U A^ I = n-1）。由于 A’AJHAp取自原来的集族｛人，人2|||代｝，故满足定理的条件，并且 p兰n-1cn，由归纳假设知集族 ｛A1,A2川Ap｝有相异代表系e，e2，|||ep，然而f UAi2U…U Ap| = P，故 A UA2 U…UAp =扁,良,…eplF 现考虑n - p个集合构成的集族 Mp1 -F,Ap 2 -F,|||An-F? 对于任意 1 空 k 乞 n - p 和 p ? 1 _ j1 ::: j2 ：：： IH ：：： jk _ n，有 （f -F归冶十）U…出他-F J I 二 A^JjAj^jAjk -F NAUAU-UApUALUA^U-UAjJ