整数分拆中的一个计数公式

《整数分拆中的一个计数公式》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第26卷第3期2007年9月《新疆师范大学学报》(自然科学版)JournalofXinjiavIIgNormalUniversity(NaturalSciencesEdition)整数分拆中的一个计数公式沙元霞(大庆师范学院数学系，黑龙江大庆163712)。V01．26，No．3Sep．2007摘要：文章给出了整数分拆时部分数中含有I的分拆P‘l’(n+k)的定义，利用分拆的计数公式以及分拆的意义，给出了P11’(n+k)的计致公式．关键词：整敦分拆f第一类元，部分，计数公式中曩分类号：0157．1文献标识码：A文章编号：1008-9

2、659一(2007)．03．0073-021引言在组合计数中整数分拆是一个较为困难的问题，但它却有着极为广泛的应用价值，我们在研究分拆计数问题时希望能够找到巧妙的解法从而得到完美的解决。本文就是在限定了某种条件下给出了分拆P11，(挖+五)的定义及计数公式。2预备知识定义1设nl，砌’．．·，m是奄个正整数，nl≥疗2≥⋯≥m．如果n=哟+m+⋯+m，则分解式行=筇l+行。+⋯m称为疗的一个恰有k个部分的(无序)分拆，或称为一个部分数为k的行一分拆椭(i=1，2’．．·惫)称为该分拆的一个部分，以P。(砣)表示部分数为k的竹一分拆的个数。定义

3、2设露，k都是正整数，以P甜(行)表示无一部分大于愚的疗一分拆的个数，并令Ps‘(o)=1。定义3设行，k都是正整数。以P丑(行)表示至多只有五个部分的以～分拆的个数，并令P垂(o)=1●引理1。Pt(n)=∑Pr(行一七)3主要结果定义4以A表示由全体部分数为r的行一分拆所成之集，设a∈A．若在分拆a中，含有等于1的部分，则称a为A的一个第一类元。定义5Pl”(一+忌)为部分数为k的含有第一类元的行+k分拆。定理1设k为任一正整数，则Pl"(咒+忌)可表示为R(疗+量)与Pk(一)之差的形式，即P{1’(疗+Ji})=P．(疗+磊)一P^(

4、行)证明P

5、(挖+忌)表示整数疗+而的量分拆数，设P

6、(雄+忌)=nl+啦+⋯+m(行l≥行2≥⋯≥m>0)将其分两部分考虑：(1)在各部分露l，啦．-．·m中，均不含有l，记作：一(竹+足)(2)在各部分行-，砌’．．·m中。至少有一个部分含有l，记作tPl”(以+五)．．．P．(疗+忌)=Pf(行+志)+Pl”(筇+五)·[收稿日期]2007一04一07[作奢简介]沙元曩(1980一)，女。愚龙江大庆人，在读硬士研究生。主要从事组合优化和图论方向的研究．万方数据74新疆师范大学学报(自然科学版)2007龟任取a∈戌(挖+五)，由心(疗+五

7、)定义可知，口不是第一类元。将珂(行+量)的各部分均减去1。得到部分数为点的rt一分拆，郾Pk(件)。所以得到耳(挖+量)=Pk(砣)。L--1定理2P11’(他+忌)=∑Pr(n)一1证明由定理1，R(行+惫)=Pt(n)+P{1’(雄+惫)鹾1’(珐+素)=Pl(跨+走)一A(对)Pl”(n+量)=Pi(再+七)一Pk(再)^=∑P，(行+志一正)一Pt(n)r_l▲=∑P，(唯)一PA(n)rllk--1=∑P，(刖定理得证实例：现有某班级要进行学期排课，本学期计划每周12节课。为方便开展活动，要求某些天此班至多有一节课，并且要求每天都

8、有课，问若不考虑课程之间的区别，共有多少种拌课的方法?解：J眭；题要求将12节课分到5天中去，求某些天至多一节课的分拆方法，相当于求将12分成5部分时含有第一类元的分拆数。5一l联"(12)=P51’(7+5)=>：Pr(7)鬲=P1(7)+B(7)+P3(7)+P4(7)=1+3+4+3=11定理3以P7(奄)表示k个数分到五个部分中去，允许某些部分为空的不重复鲥方法数，则P11’(再+五)=R(")[P，(志)一1]证明下面这样来做P{”(行+忌)由于R(一+忌)表示整数挖+k的量分拆数，Pt(拧)表示整数的分拆数故先把行+志个数中的n个

9、数取出分到忌个部分中去即为Pt(疗)，再把剩余的志个数分到志个部分中去，此时这忌个数不需要每个部分都含有，即可分到五个部分中的某些部分中去，记作P7(五)。相当于将惫个相同物品放蓟k个相同盒子中，可允许某些盒子为空的方法数。所以R(以)P，(矗)=R(竹+志)应用定理l有Pk(n)P7(五)=R(杯)+P11’(开+惫)P11’(矗+五)=P▲(，1)P7(五)一R(疗)=R(摊)[P7(惫)一1]定理得证Pi”(竹+点)在解决组合问题时具有一定的有效性和实用性，关于其具体的计数公式还有待于迸一步探索。参考文献：1"13曹汝成．组合数学[M]

10、．广州，华南理工大学出版社，2003。146--162．[2]柯召，魏万迫．组合论[M]．北京。科学出版社，1984；259—276．[3]孙淑玲，许胤龙．组合数学