r(R1)?（{a,b),(b,c),(c,a),(a,a)}
r(R2)?{(a,a),(b,b),(c,c),(d,d)} s(R2)??
t(R2)??
等价关系
设R为非空集合 A上的关系，若 上的关系，若 R是自反的、对称的和传递的
，则R为A上的等价关系。若(x,y)?R，称 x等价于 y，记作 x~y。 设R1和R2是集合A上的等价关系，证明R1IR2 也是集合A上的一个等价关系。 R1，R2是集合A上的等价关系，因此R1，R2是自反的、对称的和传递的。 ?x(x?A??x,x??R1)，?y(y?A??y,y??R2) ?x(x?A??x,x???y(y,y)?R1IR2) ，R1IR2是自反的 ?x?y(x,y?A??x,y??R1??y,x??R1) ?c?d(c,d?A??c,d??R2??d,c??R2) R1IR2是对称的 R1IR2是传递的 所以R1IR2是A上的等价关系。 划分
设
i1?i?nA是非空集合，A
的一簇子集|A1UA2ULUAn|?n?1?|A|??|AiIAj|?满足以下条件
1?i?j?n1?i?j?k?n?|AiIAjIAk|?L???1?|AiIAjILIAn|
(1)Ai??(i?1,2,3L) (2)?Ai?A
i?1m(3)Ai?Aj??(i?j)
若满足1），2），3），称?A1,A2,LAn?是A的一个划分，且称?A1,A2,LAn?中的任一元素为A的一个类或划分的一个块。
设集合A?{A1,A2,LAn}是集合S的划分，并且B是一个任意集合。试证明集合{A1IB,A2IB,LAnIB} 是集合SIB的划分 由题意可知S满足 (1)Ai??(i?1,2,3L) (2)?Ai?A i?1m(3)Ai?Aj??(i?j) 偏序关系
设R为非空集合A的二元关系，如果R具有自反性，反对称性合传递性，则称R为A上的偏序关系，集合A和A上的偏序关系R一起叫做偏序集。基座（A，R）.可以把偏序关系记作? ，偏序集记为（A，?）。如果R是集合A上的偏序关
（a,b）?R可以表示为a?b 系，
设R是S上的偏序关系，证明：R-1是S上的偏序关系. 例
?x?S,因为R在A是自反的，则（x，x）?R 有（x，x）?R?1，则R?1在A是自反的 （x，y）?R?1,x?y，有（y，x）?R，因为R在A是反对称的， 有（x，y）?R，（y，x）?R-1，则R?1在A是反对称的 （x，y）?R?1（,y，z）?R?1，则（z，y）?R?1（,y，x）?R?1， 容斥定理
两个集合的容斥原理：两个有穷集的并集中存在的元素数等于 这两个集合的元素数之和减去其交集种的元素数，即
|A?B|?|A|?|B|?|A?B|
容斥原理，设A1,A2,LAn 是有穷集。那么
|A1UA2ULUAn|?
1?i?n?|A|??i|AiIAj|?1?i?j?n1?i?j?k?n?|AiIAjIAk|?L???1?n?1|AiIAjILIAn|
例
有120名同学，其中100人至少会C++，Java，python中的一门编程语言，65人会C++，45人会Java，42人会python，20人会C++和Java，25人会C++和Python，15人会Java和python。求 （！）会所有语言的学生人数 （2）只会一种编程语言的学生人数 （1）100-（42-65-45+15+20+25）=8人 （2）100-（15+20+25-16）=54 人
特点
k 阶常系数线性非齐次递推方程的标准形：
常系数线性非齐次方程
G?n??a1G?n?1??a2G?n?2??L?akG?n?2??r?n? （1）
其中a1,a2,L,ak为常数，ak?0,n?k，r?n??0，f?n?是只依赖于n的函数 当r?n??0时，常系数线性齐次递推方程 ：
G?n??a1G?n?1??a2G?n?2??L?akG?n?2??0（与非齐次方程相伴的线性齐
次递推式）
通解的结构
定理 设
G?n?是对应的相伴线性齐次递推方程 (6.2) 的通解 , G*( n)是非 齐次递推方程的一个特解，则
G(n)= G?n?+ G*( n) 为非齐次递推方程的通解 。
1. 非齐次递推方程的通解 (结构 )=齐次递推方程的通解 +非齐次递推方程的一个特解
2. 特解的形式依赖于 f(n)
3. 求解的关键：确定常系数非齐次递推方程的一个特解
求解步骤
求相伴的常系数线性齐次递推方程的通解 求非齐次递推方程的一个特解 G*( n) G(n)= + G*( n)
非齐次方程的两种不同情况下特解的求解方法 f(n) 为n的t次多项式 (多项式函数 )
f(n) 为n的t次多项式，其特解一般也是n的t次多项式
2求递推方程an?2an?1?2n的通解。 2设an*?Pn?P2n?P3,带入递推方程得 1??P2n?P3-2?P Pn11?n?1??P2?n?1??P3?2n 222??22整理得 ?Pn??4P11?P2?n?2P1?2P2?P3?2n ??P1?2? ?4P1?P2?0??2P?2P?P?0123? ??P1?2??P2??8 ?P??12?3an?c2n?2?n2?4n?6?
f(n) = ) =A?n (指数函数)
若?不是特征根，则解为c?n, 其中 c为待定常数 .
若?是 e 重特征根，则解为cne?n, 其中 c为待定常数
H(n)?5H(n?1)?6H(n?2)?2n 令 H*(n)?Pn2 代入得 Pn2?5P(n-1)2nn?1n?6P(n?2)2n?2?2n n?1解得P=-2，特解 H*(n)??n2 迪利克雷及其他数学家对鸽巢原理早期的应用
鸽巢原理最早是由 19 世纪的德国数学家
狄利克雷（ Dirichlet Dirichlet ）运用于解决数学问题而提出来的 , 又称
为“狄利克雷原理”，也有称抽屉”的。
它常 被用来证明一些存在性的数学问题 ，并且在数论和密码 学中也有着广泛的应用。 鸽巢原理 的应用 是千变万化，它可以解决许多有趣的问题，并且常能得到一些令人惊异的 鸽巢原理（抽屉）
若把 n+1 个物体放到 n（n≥1 ）个盒子中去，则 至少 有一个盒 子放有 至少 2个物体。 斐波那契数的应用
广义的鸽巢原理 ：如果将 N个物体放入 ??个(N >??)盒子中，则 至少有一个盒子包含 ?N/k ?个
斐波那契数列
数列f1, f2, …, fn, … 称作斐波那契数列，其中的每一个数也称作斐波那契数。
f1?1??f2?1 ??f?f?fn?1n?2?n
斐波那契数在叶序、植物叶片排列的研究
在树木的枝干上选一片叶子，记其为数0，然后依序点数叶子（假定没有折损），直到到达与那些叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转
离散数学期中课程报告
