06第二章：正整数的分拆2014

《06第二章：正整数的分拆2014》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合论第二章特殊计数1组合论第二章特殊计数§2.3正整数的分拆21本讲内容1、正整数分拆的概念2、有序分拆3、分拆数4、分拆的Ferrers图3知识点：正整数分拆的概念分拆数及递推关系分拆的Ferrers图内容及其掌握程度：理解正整数分拆的有关概念能熟练掌握计算分拆数的一些方法学会利用Ferrers图来研究正整数分拆42本讲内容1、正整数分拆的概念2、有序分拆3、分拆数4、分拆的Ferrers图5一、基本概念给定n,k,n的一个k部分拆:把n表示成k个正整数之和n=n1+n2+…+nk(2-1)的一种表示法，其中ni1(1ik)

2、.分部：ni容量：ni的大小分拆分为有序分拆和无序分拆无序分拆简称为分拆63正整数n的一个k部分拆对应把n个全相同的球放进k个盒子里，每盒至少有一个球的一种分一、基本概念配方法.有序分拆的情形：k个盒子全不同；无序分拆的情形：k个盒子全相同.如:设n=n+n+…+n是正整数n的一个分拆，其12k对应情形如图所示：有序分拆无序分拆…………第1个盒子第2个盒子第k个盒子有n1个有n2个有nk个7本讲内容1、正整数分拆的概念2、有序分拆3、分拆数4、分拆的Ferrers图84二、有序分拆有序分拆:若表达式n=n1+n2+…+nk(2-1)各分部不同的次

3、序认为是不同的表示法.有序分拆可用一个有序k元组n1,n2,…,nk来表示.这时称ni为这个有序分拆的第i个分部.有序分拆的计数问题常常能归结为求不定方程的整数解问题.9二、有序分拆定理2.8正整数n的一个k部有序分拆n1,n2,…,nk就是k元不定方程x1+x2+…+xk=n(2-2)的一个正整数解，从而可知其总数是n-1Cn(-1,-)nkk-1即：有序分拆的计数可归结为求带有一定限制条件的系数全为1的不定方程的整数解问题.105二、有序分拆正整数n的一个k部有序分拆n,n,…,n12k等价于把n个全相同的球放进全不同的

4、k个盒子里，第i个盒子有n个球，n>0,i=1,2,…k.ik11二、有序分拆例1正整数2n分拆成k个分部，各分部都是正偶数的有序分拆个数为C(n1,k1)．证明因为不定方程x+x+…+x=n的正12k整数解的个数等于不定方程2x+2x+…+2x=2n12k的正整数解的个数.126二、有序分拆例2设p,p,…,p是k个正整数,则正整数n的k12k部有序分拆中第i个分部大于等于pi(1ik)的分拆个数是knk-1-pii1k-1它也是把n个全相同的球放进k个全不同的盒子里,第i个盒子里至少有p个球的分配方法数.i13本

5、讲内容1、正整数分拆的概念2、有序分拆3、分拆数4、分拆的Ferrers图147三、分拆数现在来研究无序分拆，即对诸ni任意换位后不变的分拆,无序分拆记为=(n1,n2,…,nk)无序分拆简称为分拆.p(n,k)--正整数n的所有k部分拆的个数;n的k部分拆数.p(n)--n的所有分拆的个数称为n的分拆数．p(n)=p(n,1)+p(n,2)+…+p(n,n)15三、分拆数p(n,n)=p(n,1)=1.若k>n1,则p(n,k)=0，p(n,0)=p(0,n)=0.规定p(0,0)=1,则函数p(n,k)的定义域是0.无序分拆的计数问题能否

6、也可归结为带有一定限制条件的不定方程的整数解问题呢？168三、分拆数1.分拆的指数型表示法例如4的所有分拆有如下表示：4＝4→41,4＝3+1→3111,4＝2+2→22,4＝2+1+1→2112，4＝1+1+1+1→14.一般地,如果n的一种分拆中有1个1,2个2,…,n个n，称为1122…nn-型的，且有11+22+…+nn=n17三、分拆数1.分拆的指数型表示法n的一种分拆为1122…nn-型的，则有11+22+…+nn=n即1,2,…,n为下面不定方程1x1+2x2+…+nxn=n(2-3)的一个非负整数解

7、.反之不定方程(2-3)的一个非负整数解对应n的一种无序分拆.p(n)恰是不定方程(2-3)的非负整数解个数.189三、分拆数2.分拆数的递推关系由正整数n的k部分拆的定义可知，若n>1，则p(n,1)=p(n,n1)=1，p(n,2)=n/2，迄今为止,p(n,k)和p(n)都没有比较简单的计数公式.19三、分拆数2n,n0(mod6)122n1-,n1,5(mod6)21212npn(,3)2112n-,n2,4(mod6)1232n1,n3(mod6)124当实数a整数+1/2时，记号a表示与

8、a最接近的整数.2010三、分拆数定理2.9设n,k，则p(n,k)有如下递推关系：(1)p(n,k)=