第2章 计数问题第2章 计问题数问题.ppt

鸽巢原理举例2 例2：证明在任意6个人中，要么有3个人互相认识，要么有3个人互相不认识。 证明：每个人用一个点表示，如果a，b认识，用红线连接，否则绿线链接。那么就是要证明下图中存在红色或绿色的三角形。 红色三角形：3个互相认识的人 绿色三角形：3个互相不认识的人 鸽巢原理举例2(续) (1)：a连接的5条边中一定有3条绿色或红色的，不妨设有三条绿色的 /*鸽洞原理*/ (2)如果bd边或者bc边是绿色，则存在绿色三角形abd或者abc。 (3)现在考虑bc边和bd边是红边的情况。如果dc边是绿色会构成绿色三角形adc；如果dc边是红色，会构成红色三角形dbc。证明完毕。 * 例2.2.6 生日问题 n个人中，求至少有两个人生日相同(同月同日不计年)的概率。假定出生在某天的概率均等，忽略2月29日。 解 设E表示“至少两个人生日相同”，则 表示“没有两个人生日相同”，则 。 从而 。 事实上，随着天数n的增加，至少两个人 生日相同的概率也随着增加，当n≥23时， 至少有两个人生日相同的概率大于1/2。 * 两个事件并的概率 定理2.5.2 设E1和E2是两个事件，则 P(E1∪E2)=P(E1)＋P(E2)－P(E1∩E2) (2.5.3) 如果E1∩E2=Φ，即E1与E2为不相交的事件，则有下面的推论。 推论2.5.3 设E1和E2是两个不相交的事件，则 P(E1∪E2) = P(E1)＋P(E2) (2.5.4) * 例2.5.7 掷出两个各面同性的骰子，得到“一对”(两个骰子点数相同)或点数和为6的概率是多少？ 解 设E1表示事件“一对”，E2表示事件“点数和为6”，则样本空间大小是36， 事件E1的种数为6,即 (1,1),(2, 2),(3,3),(4,4),(5,5),(6,6), 事件E2的种数为5，即(1,5),(2,4),(3,3),(4,2),(5, 1)。 E1∩E2的种数为1。 * 例2.5.7 解（续） 从而 P(E1) =1/6 , P(E2) = 5/36, P(E1∩E2) = 1/36 。 根据式(2.5.3)，有 P(E1∪E2)=1/6＋5/36－1/36=5/18 。 即得到“一对”或点数和为6的概率是5/18 。 * 2.6? 递归关系 递归关系可用于解决一些特定的计数问题。 递归关系是序列中第n个元素与它相邻前若干个元素之间的关系。 例如 第一个数是5； 2、将前一项加3得到后一项。 5, 8, 11, 14, … 递归关系 a1 = 5， an = an-1+3 * 定义2.6.1 对序列a0, a1, a2, …,an - 1, …， 用a0,a1,a2, …,an - 1中的某些项表示an的等式称为递归关系(recurrence relation)。显示地给出序列a0, a1, a2, …的有限项的值，称为初始条件(initial condition)。 显然，递归关系和确定的初始条件一起，才能确定一个序列。 * 例2.6.1 某人投资1000元，每年可收益12％。An表示他在第n年末的总资产。求出定义序列{An}的递归关系和初始条件。 解 序列{An}的递归关系和初始条件分别为： An = An - 1＋0.12×An -1= 1.12 An -1, n≥1 , A0 = 1000 * 例2.6.2 Sn表示不含子串“111”的n位字符串的个数。求出序列{Sn}的递归关系和初始条件。 解 序列{Sn}的递归关系和初始条件分别为： Sn = Sn-1＋Sn-2＋ Sn-3，n≥4, S1 = 2, S2 = 4, S3 = 7。 * 2.7 计数问题的应用 例2.7.1 7个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的“钥匙”。为了安全起见，必须有4位在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学工作者的“钥匙”至少应有多少种特征？ 解 为了使任意3个人在场时至少缺少一个特征而打不开门，该电子锁至少应具备C(7,3)=35种特征；每个科学工作者的“钥匙”至少要有C(6,3)= 20种特征。 * 例2.7.2 某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在a克到（a+0.1）克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生