容斥原理和鸽巢原理.pptVIP

证假定没有长度为n+1的单调增子序列，下面证明必有长度为n+1的单调降子序列。设表示从开始的最长的单调增子序列的长度，由假设知由鸽巢原理知，至少有例**第93页，共132页，星期日，2025年，2月5日所求路径数为而容斥原理**第61页，共132页，星期日，2025年，2月5日习题3.103.213.22**第62页，共132页，星期日，2025年，2月5日n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。n个有区别的球放到m个不同的盒子中，要求无一空盒，求不同的方案数。设Ai为使第i个盒子为空的方案的集合，i=1,2,…,m。则有第二类司特林数展开式**第63页，共132页，星期日，2025年，2月5日容斥原理**第64页，共132页，星期日，2025年，2月5日所求方案为由知容斥原理**第65页，共132页，星期日，2025年，2月5日例容斥原理**第66页，共132页，星期日，2025年，2月5日推论1推论2由，容斥原理**第67页，共132页，星期日，2025年，2月5日问题：设S={1,2,…,n}，从S中取r个进行排列，得要求只有k个数满足，这样的错排数用来表示。例从4个中取3个的排列数为P(4,3)=24其中，这11个排列为231，312，214，241，412，314，341，431，234，342，432错排问题的推广**第68页，共132页，星期日，2025年，2月5日定理对于正整数，若，则有证设Ai为满足的所有r排列的集合，i=1,…,r当时，我们有容斥原理**第69页，共132页，星期日，2025年，2月5日，这9个排列为132，213，321，142，421，134，413，243，324，这3个排列为124，143，423，这1个排列为：123。容斥原理**第70页，共132页，星期日，2025年，2月5日容斥原理**第71页，共132页，星期日，2025年，2月5日广义容斥原理定理3.4**第72页，共132页，星期日，2025年，2月5日容斥原理**第73页，共132页，星期日，2025年，2月5日容斥原理例**第74页，共132页，星期日，2025年，2月5日容斥原理**第75页，共132页，星期日，2025年，2月5日容斥原理性质：(1)证**第76页，共132页，星期日，2025年，2月5日例容斥原理**第77页，共132页，星期日，2025年，2月5日(2)证容斥原理**第78页，共132页，星期日，2025年，2月5日鸽巢原理：若n+1个鸽子飞入n个鸽巢，则至少有一个鸽巢中有两只鸽子。例3.19从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中的一个数是另一个数的倍数。解设所取的n+1个数是：。令其中为奇数。鸽巢原理**第79页，共132页，星期日，2025年，2月5日由于1到2n的正整数中只有n个奇数，故中至少有两个相等。设，那么当时，是的倍数，否则是的倍数。鸽巢原理**第80页，共132页，星期日，2025年，2月5