下载文档原格式
相异实数的概念相异实数是指两个实数之间的差值不为零的实数。
换句话说，如果两个实数a 和b满足a-b≠0，则我们称它们为相异实数。
为了更好地理解相异实数的概念，我们可以先来思考一下实数的性质。
实数是包括有理数和无理数的数的集合，它们可以用来表示各种各样的数量，如长度、面积、时间等。
在实数集合中，我们可以进行各种运算，如加法、减法、乘法和除法，这些运算可以帮助我们处理各种实际问题。
在实数集合中，有一些特殊的实数，它们的性质与其他实数有所不同，这就是相异实数。
相异实数可以用来表示两个不同的数之间的差值，它们之间的差值是一个非零实数。
相异实数的概念在数学中是非常重要的，它可以帮助我们解决一些实际问题和证明一些数学定理。
相异实数的例子有很多，比如2和3就是相异实数。
因为它们之间的差值为3-2=1，1是一个非零的实数。
又比如，π和e也是相异实数，它们之间的差值为π-e，这个差值也是一个非零的实数。
相异实数的概念可以推广到更高维度的情况下。
在一维实数中，我们可以表示两个不同的点之间的距离。
在二维平面中，我们可以表示两个不同的点之间的欧几里德距离。
在三维空间中，我们可以表示两个不同的点之间的三维距离。
在更高维度的情况下，我们可以类似地表示两个不同的点之间的距离。
相异实数的概念在数学中有着广泛的应用。
比如，在微积分中，我们可以使用相异实数的概念来定义函数的导数。
如果一个函数在某个点的导数存在，那么这个导数就是这个函数在该点的切线的斜率，而这个切线的斜率就是相异实数。
此外，在代数中，我们可以使用相异实数的概念来定义不等式。
如果两个实数a 和b满足a-b>0，则我们可以说a大于b，或者b小于a。
这样，我们就可以比较和排序实数，从而解决一些代数问题。
另外，相异实数还可以用来表示向量和矩阵之间的差值。
在线性代数中，我们可以使用相异实数的概念来定义向量和矩阵的运算，如加法、减法和求标量倍数。
这些运算可以帮助我们解决线性方程组和矩阵方程组的问题。
7.1引论我们先来看一个例子。
现有6名职员x1,x^|x6和6项工作y,,y^( y6，每个职员适合做某些工作而不适合做另外一些工作。
为了方便，在图，如何把它找到？如果这种安排不存在，那么对多少人能做合适的安排？V】>2 力yt在第5章中，我们把它看成是有限制位置的排列问题，使用容斥原理及棋子多项式可以求出合适安排的方法数。
但是，它仅仅是计数，对于如何找到合适的安排不能提供任何信息。
在本章中，我们将按照一种完全不同的方法来研究并解决这个问题。
在前面的问题中，所谓合适的安排，就是在无阴影的部分里不同行、不同列选6个方块的一种方法。
如果把每行无阴影方块的横坐标写成集合，那么A *%山A *1肆3,小5】A4 - l y i, y3, y6 匚yud 氏+3、*、y^如果能从每个集合中选出一个元素，而且6个元素两两互不相同，就得到了一种合适的安排。
遗憾的是,对于这里的A I,AH||A6而言，这样的选择不存在。
这是因为，无论A i,A s, A5选出的是y i,y2,y6，还是y2, y6,y i, A4都没有合适的元素可选。
令A, A III A n是集合E的n个子集。
E的n个元素^©，川宀，其中，e 人2,川耳己A，称为是集族「A,AlHA n?的一个代表系。
如果集族的代表系中的元素两两互不相同，则称该代表系为集族的相异代表系。
例如，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是认，A z, 4,人？的相异代表系。
非空集合A,, AJ1I人构成的集族一定有代表系，但不一定有相异代表系。
例如，A —1,4二A —1,2,3,4,5 1, A —4,几—1,4,就没有相异代表系。
直观上看，是因为AU AB U乓中的元素太少。
如何把感性认识上升到理论高度，找出集族有相异代表系的充要条件是本节的任务。
组合数学知识点总结组合数学是数学的一个重要分支，它研究的是集合、排列和组合等离散的数学结构。
在现代科学和工程中，组合数学经常被应用于计算机科学、密码学和操作研究等领域。
本文将对组合数学的一些重要知识点进行总结。
一、集合论基础在组合数学中，集合是一个基本概念。
集合由元素组成，元素可以是具体的对象或者抽象的个体。
在集合论中，常用的符号有∈表示“属于”，∉表示“不属于”，∪表示“并集”，∩表示“交集”，∖表示“差集”，等等。
二、排列与组合1. 排列排列是从集合中选择一部分元素按照一定的顺序排列，其重要性质有：- 有序性：排列的元素是有顺序的。
- 可重复性：元素可以重复使用。
2. 组合组合是从集合中选择一部分元素不考虑顺序的组成一个组合，其重要性质有：- 无序性：组合的元素无顺序要求。
- 不可重复性：元素不可重复使用。
三、二项式定理与多项式定理1. 二项式定理二项式定理是组合数学中一个基本且重要的定理，它用于展开二次幂或高次幂的多项式。
二项式定理的公式为：(a + b)^n = C(n, 0)a^n * b^0 + C(n, 1)a^(n-1) * b^1 + ... + C(n, n)a^0 *b^n其中，C(n, k)为组合数，表示从n个元素中选择k个元素的组合数。
2. 多项式定理多项式定理是二项式定理的推广，用于展开更高次幂的多项式。
多项式定理的公式为：(a1 + a2 + ... + ak)^n = Σ C(n, k1, k2, ..., km)a1^k1 * a2^k2 * ... *ak^km其中，Σ表示对所有组合进行求和，C(n, k1, k2, ..., km)为多重组合数，表示从n个元素中选择k1个元素作为第一项，k2个元素作为第二项，以此类推。
四、图论基础图论是组合数学的一个重要分支，研究的是图及其性质。
图是由节点和边组成的一种数学结构，用于描述事物之间的关系。
图论中的一些基本概念和算法包括：- 图的表示方法：邻接矩阵、邻接表等。
第7章 相异代表系7.1 引论我们先来看一个例子。
现有6名职员126,x x x 和6项工作126,y y y ，每个职员适合做某些工作而不适合做另外一些工作。
为了方便，在图，如何把它找到？如果这种安排不存在，那么对多少人能做合适的安排？在第5章中，我们把它看成是有限制位置的排列问题，使用容斥原理及棋子多项式可以求出合适安排的方法数。
但是，它仅仅是计数，对于如何找到合适的安排不能提供任何信息。
在本章中，我们将按照一种完全不同的方法来研究并解决这个问题。
在前面的问题中，所谓合适的安排，就是在无阴影的部分里不同行、不同列选6个方块的一种方法。
如果把每行无阴影方块的横坐标写成集合，那么{}{}{}{}{}{}1122134532641365166345,,,,,,,,,,A y y A y y y y A y y A y y y A y y A y y y ======如果能从每个集合中选出一个元素，而且6个元素两两互不相同，就得到了一种合适的安排。
遗憾的是，对于这里的126,A A A 而言，这样的选择不存在。
这是因为，无论135,,A A A 选出的是126,,y y y ，还是2614,,,y y y A 都没有合适的元素可选。
7.2 相异代表系 令12,n A A A 是集合E 的n 个子集。
E 的n 个元素12,,n e e e ，其中，1122,,n n e A e A e A ∈∈∈，称为是集族{}12,n A A A 的一个代表系。
如果集族的代表系中的元素两两互不相同，则称该代表系为集族的相异代表系。
例如，4，1，4，3是{}{}{}{}12341,4,1,2,3,3,4,5,3,4,5A A A A ====的代表系，而1，2，3，4和4，2，3，5是{}1234,,,A A A A 的相异代表系。
非空集合12,n A A A 构成的集族一定有代表系，但不一定有相异代表系。
例如，{}{}{}{}12341,4,1,2,3,4,5,4,1,4A A A A ====就没有相异代表系。
直观上看，是因为134A A A 中的元素太少。
如何把感性认识上升到理论高度，找出集族有相异代表系的充要条件是本节的任务。
假设12,,n e e e 是集族{}12,n A A A 的相异代表系，对于{}1,2,n 有21n -个非空子集，故这种必要条件有21n-个。
1935年，P.Hall 提出将这21n-放在一起就是集族{}12,n A A A 有相异代表系的充分条件。
定理7.2.1 集族{}12,n A A A 有相异代表系，当且仅当对每个1,2,k n =和每种选择()1212,,1k k i i i i i i n ≤<<<≤，集族满足12k i i i A A A k ≥证明 由前面的分析，必要性是显然的。
下面通过对n 进行归纳来证明充分性。
当1n =时，由定理的条件知11A ≥，即1A 是非空集合。
任取1A 的元素1e ，就是{}1A 的相异代表系。
设对任何{}12,,,m m n A A A <满足定理的条件，则该集族有相异代表系12,,,m e e e 。
现假设集族{}12,n A A A 满足定理的条件，我们将分两种情况讨论：（1）对于任何()11k k n ≤≤-，选择121k i i i n ≤<<<≤均满足121k i i i A A A k ≥+，由于12,n A A A 满足定理的条件，于是()11i A i n ≥≤≤。
任取n n e A ∈，构造集族{}{}{}{}121,,,nn n n A e A e A e ----则对于任意11k n ≤≤-和1211k i i i n ≤<<<≤-，有{}(){}(){}()(){}1212121kkk i ni ni ni i i ni i i A e A e A e A A A e A A A k---=-≥-≥即该集族满足定理的条件，由归纳假设知它有相异代表系121,,n e e e -，且()11i n e e i n ≠≤≤-。
从而121,,,n n e e e e -就是{}12,n A A A 的相异代表系。
（2）对某个()11p p n ≤≤-及某种选择()121212,,,1,p p p i i i i i i i i i n A A A p ≤<<<≤=，不失一般性，我们假设这p 个集合是12,p A A A ，则()1211p i i i A A A p p n =≤≤-。
由于12,p A A A 取自原来的集族{}12,n A A A ，故满足定理的条件，并且1p n n ≤-<，由归纳假设知集族{}12,p A AA 有相异代表系12,,p e e e ，然而12p i i i A A A p =，故{}1212,,p p A A A e e e F ==现考虑n p -个集合构成的集族{}12,,p p n AF A F A F ++---对于任意1k n p ≤≤-和121k p j j j n +≤<<<≤，有()()()()()()12121212kk k j j j j j j pj j j A F AFA FA A A F A AA A A A F p k p k---=-=-≥+-=即{}12,,,p p n A F A F A F ++---满足定理的条件，且集族中的集合数1n p n n -≤-<。
由归纳假设知它有相异代表系12,,p p n e e e ++，且{}12,,p p n ee e F φ++=从而1212,,,,,,p p p n e e e e e e ++就是集族{}12,n A A A 的相异代表系。
例1 已知{}{}{}{}{}123451,2,1,4,1,3,4,5,2,4,1,4A A A A A =====。
因为{}12451,2,43A A A A ==由定理{}12345,,,,A A A A A {}1234,,,A A A A ，4，5，2。
定理7.2.2 集族{}12,n A A A 中存在着r 元子集有相异代表系，当且仅当对每个1,2,,k n =和每种选择()1212,,,1k k i i i i i i n ≤<<<≤，集族满足()12k i i i A A A k n r ≥--证明 对于1k n r ≤≤=，定理中的不等式自动满足。
令{}12,,n r F f f f -=，且()12n F A A A φ=，考虑集族{}12,,nA F A F A F 。
下面先证明：{}12,n A A A 的r 元子集有相异代表系，当且仅当{}12,,nA F A F A F 有相异代表系。
假设{}12,n A A A 的r 元子集有相异代表系，不失一般性，设{}12,r A A A 有相异代表系12,r e e e ，12,,n r f f f -就是{}12,,nA F A F A F 的相异代表系。
假设{}12,,nA F A F A F 有相异代表系12,,n x x x ，因F 中只有n r -个元素，所以12,,n x x x 中至少有r 个元素不在F 中。
不妨假设1122,,r r x A x A x A ∈∈∈，且两两互不相同，从而12,,r x x x 是{}12,n A A A 的r 元子集{}12,r A A A 的一个相异代表系。
下面再证明：{}12,,nA F A F A F 有相异代表系，当且仅当对每个1,2,,k n =和每种选择()1212,,,1k k i i i i i i n ≤<<<≤，有()12k i i i A A A k n r ≥--根据定理7.2.1，{}12,,nA F A F A F 有相异代表系，当且仅当对每个1,2,,k n =和每种选择()1212,,,1k k i i i i i i n ≤<<<≤，有()()()12ki i i AFAFAF k ≥由于()()()121212kkk i i i i i i i i i AFAFAFA A A FA A A F==+从而()12k i i i A A A k n r ≥--由定理，集族{}12,n A A A 的r 元子集有相异代表系，当且仅当对每个1,2,,k n =和每种选择()1212,,,1k k i i i i i i n ≤<<<≤，有()12k i i i A A A n k r +-≥使该不等式成立的r 的最大值就是()12k i i i A A A n k +-的最小值。
故有如下推论：推论7.2.1 集族{}12,n A A A 有相异代表系的最大子集数等于()12k ii i A A A n k +-的最小值，其中，1,2,,k n =以及所有选择()1212,,,1k k i i i i i i n ≤<<<≤例2 已知{}{}{}{}{}{}{}12345671,6,4,5,6,2,6,1,2,1,2,4,6,1,1,2,6A A A A A A A =======，则有(){}1234567751,2,625A A A A A A A +-=+=且6，5，2，1，4是子集族{}12345,,,,A A A A A 的相异代表系。
于是，{}1234567,,,,,,A A A A A A A 有相异代表系的子集数最大为5。
7.3 棋盘覆盖问题棋盘覆盖问题是指将m n ⨯棋盘中的一些方块涂上阴影，余下部分用12⨯的多米诺骨牌覆盖。
所谓棋盘的完全覆盖，是指多米诺骨牌的一种放置方法，它满足如下3个性质： （1）每个多米诺骨牌覆盖棋盘上两个相邻的方法（无阴影的）； （2）棋盘上的每个方块均被某个多米诺骨牌覆盖； （3）所有多米诺骨牌不重叠放置。
现在的问题是：任意给定一个部分涂上阴影的棋盘，是否有一个完全覆盖？如果没有，那么满足性质（1）和（3）的覆盖需要用多少多米诺骨牌？ 例 对图解 首先，对整个56⨯棋盘依次标记,w b ，使得有公共边的方块标记不同。
然后，对无阴影部分（要覆盖的区域）的标记从左到右、从上到下进行编号。
因为每个多米诺骨牌必定覆盖一个w 和一个b ，所以无阴影部分中标记w 的块数与标记b 的块数相同才有可能有完全覆盖。
对每个i b 定义一个集合i A ，它由用多米诺骨牌覆盖i b 时可能覆盖的j w 组成，即{i j A w =标记j w 和i b 的方块有公共边}显然，14i A ≤≤ 图，令{}{}129129,,,,B b b b w w w w ==相应的129,,,A A A 为{}{}{}{}{}{}{}{}{}11222363256436754765768879989,,,,,,,,,,,,,,,,,,,,A w w A w w w A w w w A w w w A w w A w A w w A w w A w w =========如果{}129,,,A A A 有相异代表系，则该棋盘有一个完全覆盖。
