第一节分拆的计数第二节完备分拆ppt课件

第一节 分拆的计数第二节 完备分拆第五章第五章 整数的分拆整数的分拆 第一节第一节 分拆的计数分拆的计数 学习完本节内容，他会了解以下内容：1清楚与整数的分拆问题等价的问题及类似的三个问题及其求解；2了解整数的分拆的定义；掌握分拆计数的两个递推公式及证明；3会求部分数为1，2，3，4等情况的分拆个数；4会将某些特殊的整数分拆问题转化成普通的整数分拆问题.学习指点学习指点n1n问题1：把个相异的小球放到个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？n1n个相异的小球放到问题2：把个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？问题3：把n个一样的小球放到1n个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？问题4：把n个一样的小球放到1n个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？1问题的引入问题的引入n1n问题1：把个相异的小球放到个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？n1n个相异的小球放到问题2：把个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？问题3：把n个一样的小球放到1n个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？问题4：把n个一样的小球放到1n个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？1.(1)!;2nn 2.;2n 3.1;n4.1.答案：nr问题1：把个相异的小球放到个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？nr个相异的小球放到问题2：把个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？问题3：把n个一样的小球放到r个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？问题4：把n个一样的小球放到r个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？2问题的普通化问题的普通化nr问题1：把个相异的小球放到个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？方法：先分组再陈列第一章；或容斥原理(第二章，P48)；或指数生成函数(第四章，P140)等.1(1).rr knkrkk 答案：nr个相异的小球放到问题2：把个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？参见第二类Stirling数的组合意义(第三章，P108).答案：11(1).!rr knkrkkr 注：问题2与问题1的联络.问题3：把n个一样的小球放到r个相异的盒子里，使得无一个盒子空，有多少种不同的放法数？参见不定方程的正整数解数的计数公式(第一章，P20).或者用常生成函数的方法求第四章，P121-125).答案：1.nnr此问题等价于不定方程的正整数解的个数.12rxxxn与问题1，2，3相关的练习题n把10个师范大学毕业生分到3所中学实习，使得每所学校至少3人，有多少种不同的分法？n把8个人分成3组，每组至少2人，有多少种不同的分法？n把15个一样的即不可分辩的足球分给3个小朋友，每人至少3个，有多少种不同的分法？问题4：把n个一样的小球放到r个一样的盒子里，使得无一个盒子空，有多少种不同的放法数？此问题等价于不定方程选取r个正整数1212,(1),rrn nn nnn使得12,rnnnn求不同的选取方法数.3问题问题4的等价问题的等价问题或等价于研讨如下的整数分拆问题：12rxxxn的无序正整数解的个数.12,rn nn定义5.1：设是12,rnnnr个正整数，12,rnnnn假设那么称分解式12rnnnn为n的一个恰有r个部分的无序)分拆，或称其为一个部分数为r的n-分拆，(1,2,)in ir称为该分拆的一个部分.以()rP n表示部分数为r的n-分拆的个数.4正整数分拆的定义正整数分拆的定义n1求部分数为3且没有一个部分等于1的15分拆的个数.对定义的了解对定义的了解n2把24颗水果糖分成5堆，每堆至少有3颗糖，有多少种分法？5两个递推公式两个递推公式1()()().rrkkP nP nrnr11()(1)(2).nrrrkP nPnrkrnr 作业：n把10件彼此相异的物件分给3个人，使得每人至少分得3件物件，有多少种不同的分法？n把8个人分成3组，每组至少2人，有多少种不同的分法？n把15个一样的即不可分辩的足球分给3个小朋友，每人至少3个，不同的分法共有多少种？n部分数为3且没有等于1的部分的15-分拆的个数是多少？n求6(11)P的值.