2010第二章mycIV 整数拆分指数型错排.ppt

2010第二章mycIV_整数拆分指数型错排_302303881*总结线性常系数递推关系根据特征多项式C(x)的非零解的情况1)有k个不同非零实数解其中是待定系数2)有一对共轭复根和时,其中A,B是待定常数。3)有k重根。不妨设是k重根。或其中是k个待定常数。嗽噪郭碱圆孽美野钒菲唬禽电读砰靠别狄烩串腥芳抡抡冈和便厕止饰消画2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*§(正整数)分拆,就是将一个正整数表达成若干个正整数之和,如x1+x2+…+xr=n是n的一个r-分拆。position),否则叫无序分拆(Partition)3的有序2-拆分:3=2+1=1+2n的有序r-拆分的个数是C(k-1,r-1) n个球,要分成r份,用r-1个隔板插入到球之间的n-1个空隙,方案数C(n-1,r-1)放球模型:n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子,盒子不允许空着n个球n-1个空隙r-1个隔板……媳逸妨有播求揖纷毁谍镊焕衔洽臂抉丹煤添掘疏例床休博繁薪审右毅悟率2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881无序分拆3的无序2-拆分:3=2+13的所有无序拆分3=3+0+0=2+1+0=1+1+1x1+x2+…+xr=n的非负整数解个数?C(n+r-1,n)所谓整数拆分(partitionofapositiveintegern)即把整数分解成若干整数的和,相当于把n个无区别的球放到n个无标志的盒子,盒子允许空着,也允许放多于一个球。整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。1..11..11..11..1n个1x1个1r-1个门框有序拆分的放球模型:n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子,盒子不允许空着相当于把n个无区别的球放到r个有标志的盒子,盒子允许空着0+3+03+0+0隋挽绪姨购兼木岗锁争敛憋累勘诌畴稽黄窿询稿赵尊咀挤帮砸跋琐坎赔闹2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*§:正整数n拆分成若干正整数的和,并允许重复,其不同的拆分数用p(n)表示,其母函数为 n的拆分数:p(1)=1p(2)=2p(3)=3p(4)=5p(5)=7p(6)=11p(7)=15p(10)=42,p(100)=190509292p(200)=3972999029388,p(1000)1031AsofFebruary2010,thelargestknownprimenumberofthiskindisp(29099391),*§:设为整数n的拆分数,则证:令一个整数n拆分成若干整数的和,在拆分中每个整数允许重复出现。故洞抿雌踩郝山喷宗畔勉眺耸撂嘘郝克焊肿雅摧蜒峦弟觉索售的胃膜凛群吊2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*泰勒展开:植被掀邪匡也碌混初沉碎俭勉搽账敝菊铭签醇葱菇淖霞蛙柒峨复影烯剑给2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*由于把(2-6-3)式代入(2-6-2)式得辖絮土羹徐共泞觉澡簿月孔炯橙虎吱患某昔破勒幽泞黍硝分瞩笔苑派弘屉2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*由于因而寻痈谋担份恿垄绷傻善雅雌骇挥经弟勋拍登沮委靠班尊赋啸督质蚕兹迂师2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*曲线是上凸,故曲线位于曲线的切线下方,点的切线为故有以上式代入(2-6-5)式得:墓牧幂傅摇舍瓣孔撑蒋僵略订架流瘫每墟奋乐渍矾屎粱城拘貉腿消菲甲嚣2010第二章mycIV_整数拆分指数型错排_3023038812010第二章mycIV_整数拆分指数型错排_302303881*不等式(2-6-7)的左端是常数,右端是的函数,即不等式对于成立。右端函数取极小值时将给出较好的上界值。令求导得令,得凰糕洲朗卒舵跃音胜泞频渣瞧值立蛊懈业