复旦大学 数学模型 张云新.doc

... ... 期末考试复习张云新 1. 抽屉原理 or 容斥原理: a) 容斥原理: i. 核心:从 1 niiA ??入手考虑问题 ii. 基本定理: ① 1~ n 中能被 k 整除的个数: nk ? ?? ?? ?② 1 2 1 2 1 1 1 n n i i j i j k n i i j n i j k n A A A A A A A A A A A A ? ??? ????? ?????????????? ? ?? ??③ 1 1 n n i i i i A A ? ?? ?? : (欧拉函数( ) n?) ①( ) n?:?n 且与 n 互质的正整数的个数,其中, 1 n N n ? ?②解:将 n 作质因数分解: 1 2 1 2 mk k k m n p p p ??令全集{1, 2, , } S n ??, { | }, 1, 2, , i i A x S p x i m ? ? ??则1 ( ) mii n A ????,再用 iii, ii,i 即可求解③结论: 1 2 1 1 1 ( ) 1 1 1 m n n p p p ?? ?? ???? ???? ?? ???? ???? ?? :~ a f 做全排列,不出现 abd 与 ce 的排列种数注意捆绑法:出现 abd 的种数为 4! , ce 的种数为 5! ,同时出现的种数为 3! v. 例3 :求不超过 120 的素数的个数①不超过 120 的合数必是 2 、3 、5 、7 的倍数∵ 120 11 ?,而 11 以内的素数只有 2、3、5、7 ②令全集{1, 2, ,120} S??, { | }, 2, 3, 5, 7 i A x S i x i ? ? ?... ... 则用 iii, ii,i 即可求 2 3 5 7 A A A A ? ??③注意 1 )虽然 2、3、5、7 本身是其倍数,但是素数 2 )虽然 1 不是 2、3、5、7 的倍数,但既不是素数也不是合数综上,结果为 2 3 5 7 A A A A ? ??+4-1 : (错排数 nD ) ①nD :对 n 个元素重新排列,所有元素都不在原来的位置上的个数②记iA 为数 i 在第 i 个位置上的全体排列的集合,则 1 n n i i D A ???③结果: 1) 1 1 1 1 ! 1 ( 1) 1! 2! 3! ! n n D n n ? ?? ???????? ?? ?? 2) 1 2 1 2 ( 1)( ), 0, 1 n n n D n D D D D ? ?? ? ???理解: 情况一:第一位排 2 ,第二位不排 1 ,则可将第二位看作新的第一位, 对 1, 3, 4, , n?作1n?错排情况二:第一位排 2 ,第二位排 1 ,对剩下的做 3, 4, , n?的2n?错排(当然, 也可以考虑第一位排 k ,第k 位排不排 1 的情况, 故乘以 1n?) ④应用: 1) 1~9 中所有偶数都在原来位置上,而奇数不在的错排数: 5D 2) 1~9 中所有奇数都在原来位置上,而偶数不在的错排数: 4D 3) 1~9 中所有奇数都不在原位置的错排数: 1 3 5 7 9 A A A A A ? ???注意,若用 nD 做,应小心分类讨论: 奇数和所有偶数都不在原位置+ 奇数和1 个偶数不在原位置+ 奇数和2 个偶数不在原位置+ 奇数和 3 个偶数不在原位置+ 偶数固定,奇数不在原位置= 0 1 2 3 4 4 9 4 6 4 7 4 8 4 5 C D C D C D C D C D ? ???(4 )也是同样的) 4)