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

.页眉..:a)容斥原理::从1niiA??:①1~n中能被k整除的个数:nk? ?? ?? ?②1 2 1 21 1 1nn i i j i j k ni i j n i j k nA A A A A A A A A A A A? ??? ????? ?????????????? ? ?? ??③1 1n ni ii iA A? ?? ??:(欧拉函数( )n?)①( )n?:?n且与n互质的正整数的个数,其中, 1n N n? ?②解:将n作质因数分解:1 21 2mkk kmn p p p??令全集{1, 2, , }S n??,{ | }, 1, 2, ,i iA x S p x i m? ? ??则1( )miin A????,再用iii,ii,i即可求解③结论:1 21 1 1( ) 1 1 1mn np p p?? ?? ???? ???? ?? ???? ???? ??:~a f做全排列,不出现abd与ce的排列种数注意捆绑法:出现abd的种数为4!,ce的种数为5!,同时出现的种数为3!:求不超过120的素数的个数①不超过120的合数必是2、3、5、7的倍数∵120 11?,而11以内的素数只有2、3、5、7②令全集{1, 2, ,120}S??,{ | }, 2, 3, 5, 7iA x S i x i? ? ?.页眉..,ii,i即可求2 3 5 7A A A A? ??③注意1)虽然2、3、5、7本身是其倍数,但是素数2)虽然1不是2、3、5、7的倍数,但既不是素数也不是合数综上,结果为2 3 5 7A A A A? ??+4-:(错排数nD)①nD:对n个元素重新排列,所有元素都不在原来的位置上的个数②记iA为数i在第i个位置上的全体排列的集合,则1nn iiD A???③结果:1)1 1 1 1! 1 ( 1)1! 2! 3! !nnD nn? ?? ???????? ?? ??2)1 2 1 2( 1)( ), 0, 1n n nD 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中所有偶数都在原来位置上,而奇数不在的错排数:5D2)1~9中所有奇数都在原来位置上,而偶数不在的错排数:4D3)1~9中所有奇数都不在原位置的错排数:1 3 5 7 9A A A A A? ???注意,若用nD做,应小心分类讨论:奇数和所有偶数都不在原位置+奇数和1个偶数不在原位置+奇数和2个偶数不在原位置+奇数和3个偶数不在原位置+偶数固定,奇数不在原位置=0 1 2 3 44 9 4 6 4 7 4 8 4 5C D C D C D C D C D? ???(4)也是同样的)4)1~9中所有偶数都不在原位置的错排数:2 4 6 8A A A A? ??:( )nQ①:nQ1~n的排列中没有12, 23, , ( 1)n n??..页脚.②12 23 ( 1)n n nQ A A A?? ????③应用:8名学生排成一排跑步,后一天与前一天相比,没有一个学生的前面的人与前一天相同