离散数学第三讲.docx

本文格式为Word版，下载可任意编辑离散数学第三讲 二、容斥原理与鸽巢原理 1、 容斥原理(§1) （计数原理、包含排斥原理） 容斥原理（包含排斥原理）： 设A，B是有限集，那么 A?B?A?B?A?B 容斥原理的相关推论： (i) A?B?C ?A?B?C?A?B?B?C?A?C?A?B?C (ii) 利用归纳法 A1?A2?A3???An??Ai? i?1n1?i?j?n?A?Aij?1?i?j?k?n?A?Aij?Ak ???(?1)n?1A1?A2???An(iii) A?A?U, A?U?A (iv) A1?A2???An?U?A1?A2???An （留神基的概括含义） 设S是有限集，P1,P2,?,PrPi的子集，即 是r条性质， Ai是S中具有性质 A?i ?xx?S,x具有性质Pi? （i=1,2,…，r） 那么 （1）S 中至少具有性质 P1,P2,?,PrA1?A2?A3???Ar??Ai?i?1r1?i?j?r一条的元素数是： ?A?Aij?1?i?j?k?r?A?Aij?Ak ???(?1)r?1A1?A2???Ar （2）S 中不具有性质 元素数是： P1,P2,?,Pr的 A1?A2???Ar?U?A1?A2???Ar e.g 1 设n?2，?(n)表示不超过n 且与n 互质的 正整数的个数，求?(n) 该函数在计算机中称为EURTER函数。

解： S??1,2,3,?,n? 不妨令： n?p1p2???pr数； 设 ?1?1?r p1,p2,?,pr为互异的质 Ai??xx?S,且xpi?n,AiAj?pipji?1,2,?,r ? nAi?那么pi?(n)?A1A2?Ar…… 2、 鸽巢原理（抽屉原理、鞋盒原理）（教材P63） n+1个鸽子飞进n个鸽巢，那么可以找到一鸽巢里至少有2只鸽子 或者： 假设k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体 e.g 1 把10个点放入边长为1的正三角形内，证明，可以 找到两个点，它们之间的距离不超过三分之一 （概括问题，找鸽子，做笼子） 推广1、n个鸽洞，（多于）r?n?1个鸽子，必有一个鸽洞住有至少r+1 只鸽子 推论2、 （平均数原理） 设 xi是自然数，且 x1?x2???xn?r(r?N) n 那么 ? xk，使得 xk?r?1 证明：…… e.g 2 一个园盘划分为36个扇形，把1~36这36个数放入扇形中，每格一个数，证明无论怎样放，总可以找到三个连续的扇形，使得这三个扇形中的数之和?56。

解：…… 练习 No1 有n个乒乓球运鼓动比赛，每人至少赛一场，同一对手至多比赛一场，证明这n个运鼓动可以找到二个运鼓动，他们比赛的场数一样 No2 设 x1,x2,?,xn是n个正整数， 证明，其中至少存在若干个（下标）连续的数，使得它们的和是n的倍数 e.g 3 假定一组6个人，任意两个人或者是挚友或者是敌人，证明在这组人中或存在3个人彼此都是挚友，或存在3个人彼此都是敌人教材P65：例3.12) — 4 —。