資源描述:
《06第二章:正整數(shù)的分拆2014》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、組合論第二章特殊計(jì)數(shù)1組合論第二章特殊計(jì)數(shù)§2.3正整數(shù)的分拆21本講內(nèi)容1、正整數(shù)分拆的概念2、有序分拆3、分拆數(shù)4、分拆的Ferrers圖3知識(shí)點(diǎn):?正整數(shù)分拆的概念?分拆數(shù)及遞推關(guān)系?分拆的Ferrers圖內(nèi)容及其掌握程度:?理解正整數(shù)分拆的有關(guān)概念?能熟練掌握計(jì)算分拆數(shù)的一些方法?學(xué)會(huì)利用Ferrers圖來研究正整數(shù)分拆42本講內(nèi)容1、正整數(shù)分拆的概念2、有序分拆3、分拆數(shù)4、分拆的Ferrers圖5一、基本概念給定n,k??,n的一個(gè)k部分拆:把n表示成k個(gè)正整數(shù)之和n=n1+n2+…+nk(2-1)的一種表示法,其中ni?1(1?i?k)
2、.分部:ni容量:ni的大小分拆分為有序分拆和無序分拆無序分拆簡稱為分拆63正整數(shù)n的一個(gè)k部分拆對應(yīng)把n個(gè)全相同的球放進(jìn)k個(gè)盒子里,每盒至少有一個(gè)球的一種分一、基本概念配方法.?有序分拆的情形:k個(gè)盒子全不同;?無序分拆的情形:k個(gè)盒子全相同.如:設(shè)n=n+n+…+n是正整數(shù)n的一個(gè)分拆,其12k對應(yīng)情形如圖所示:有序分拆無序分拆…………第1個(gè)盒子第2個(gè)盒子第k個(gè)盒子有n1個(gè)有n2個(gè)有nk個(gè)7本講內(nèi)容1、正整數(shù)分拆的概念2、有序分拆3、分拆數(shù)4、分拆的Ferrers圖84二、有序分拆有序分拆:若表達(dá)式n=n1+n2+…+nk(2-1)各分部不同的次
3、序認(rèn)為是不同的表示法.有序分拆可用一個(gè)有序k元組?n1,n2,…,nk?來表示.這時(shí)稱ni為這個(gè)有序分拆的第i個(gè)分部.有序分拆的計(jì)數(shù)問題常常能歸結(jié)為求不定方程的整數(shù)解問題.9二、有序分拆定理2.8正整數(shù)n的一個(gè)k部有序分拆?n1,n2,…,nk?就是k元不定方程x1+x2+…+xk=n(2-2)的一個(gè)正整數(shù)解,從而可知其總數(shù)是??n-1Cn(-1,-)nk?????k-1即:有序分拆的計(jì)數(shù)可歸結(jié)為求帶有一定限制條件的系數(shù)全為1的不定方程的整數(shù)解問題.105二、有序分拆正整數(shù)n的一個(gè)k部有序分拆?n,n,…,n?12k等價(jià)于把n個(gè)全相同的球放進(jìn)全不同的
4、k個(gè)盒子里,第i個(gè)盒子有n個(gè)球,n>0,i=1,2,…k.ik11二、有序分拆例1正整數(shù)2n分拆成k個(gè)分部,各分部都是正偶數(shù)的有序分拆個(gè)數(shù)為C(n?1,k?1).證明因?yàn)椴欢ǚ匠蘹+x+…+x=n的正12k整數(shù)解的個(gè)數(shù)等于不定方程2x+2x+…+2x=2n12k的正整數(shù)解的個(gè)數(shù).126二、有序分拆例2設(shè)p,p,…,p是k個(gè)正整數(shù),則正整數(shù)n的k12k部有序分拆中第i個(gè)分部大于等于pi(1?i?k)的分拆個(gè)數(shù)是k????nk?-1-?pi??i?1????k-1它也是把n個(gè)全相同的球放進(jìn)k個(gè)全不同的盒子里,第i個(gè)盒子里至少有p個(gè)球的分配方法數(shù).i13本
5、講內(nèi)容1、正整數(shù)分拆的概念2、有序分拆3、分拆數(shù)4、分拆的Ferrers圖147三、分拆數(shù)現(xiàn)在來研究無序分拆,即對諸ni任意換位后不變的分拆,無序分拆記為?=(n1,n2,…,nk)?無序分拆簡稱為分拆.p(n,k)--正整數(shù)n的所有k部分拆的個(gè)數(shù);n的k部分拆數(shù).p(n)--n的所有分拆的個(gè)數(shù)稱為n的分拆數(shù).p(n)=p(n,1)+p(n,2)+…+p(n,n)15三、分拆數(shù)p(n,n)=p(n,1)=1.若k>n?1,則p(n,k)=0,p(n,0)=p(0,n)=0.規(guī)定p(0,0)=1,則函數(shù)p(n,k)的定義域是?0.無序分拆的計(jì)數(shù)問題能否
6、也可歸結(jié)為帶有一定限制條件的不定方程的整數(shù)解問題呢?168三、分拆數(shù)1.分拆的指數(shù)型表示法例如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個(gè)1,?2個(gè)2,…,?n個(gè)n,稱為1?12?2…n?n-型的,且有1?1+2?2+…+n?n=n17三、分拆數(shù)1.分拆的指數(shù)型表示法n的一種分拆為1?12?2…n?n-型的,則有1?1+2?2+…+n?n=n即?1,?2,…,?n為下面不定方程1x1+2x2+…+nxn=n(2-3)的一個(gè)非負(fù)整數(shù)解
7、.反之不定方程(2-3)的一個(gè)非負(fù)整數(shù)解對應(yīng)n的一種無序分拆.p(n)恰是不定方程(2-3)的非負(fù)整數(shù)解個(gè)數(shù).189三、分拆數(shù)2.分拆數(shù)的遞推關(guān)系由正整數(shù)n的k部分拆的定義可知,若n>1,則p(n,1)=p(n,n?1)=1,p(n,2)=?n/2?,迄今為止,p(n,k)和p(n)都沒有比較簡單的計(jì)數(shù)公式.19三、分拆數(shù)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當(dāng)實(shí)數(shù)a?整數(shù)+1/2時(shí),記號(hào)?a?表示與
8、a最接近的整數(shù).2010三、分拆數(shù)定理2.9設(shè)n,k??,則p(n,k)有如下遞推關(guān)系:(1)p(n,k)=