一类分拆数的计算问题

《一类分拆数的计算问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第23卷第2期(2007)河西学院学报V01．23No．2(2007)一类分拆数的计算问题郭育红(河西学院数学系，甘肃张掖734000)摘要：正整数n的分拆是指将正整数n表示成一个或多个正整数的无序和．设Q“m)是将正整数n分拆为m个互不相同的正整数之和的无序分拆数，而P(TI，Tn)是将正整数n分拆成rn个部分的无序分拆的分拆数．它们都是组合，图论。数论的重要概念和数据．本文得到了关于Q(岫)的一个递推关系以及P“m)与Q(n，111)之间的直接关系。进而可以利用已有的一些结果?来计算Q(rm)的值．同

2、时本文也讨论了Q“m)在图论中的一个应用．关键词：正整数的分拆；递推关系：计数；应用‘中图分类号：0157．1文献标识码：A文章编号：1672一0520(2007)02—0001一04l引言正整数刀的分拆是指将正整数疗表示成一个或多个正整数的无序和，其分拆数记为P(帕．龆伽，m)表示将正整数刀分拆成研个正整数之和的分拆数，Q以所)表示将正整数刀分拆成所个不相等的正整数之和的分拆数．荆，舷m)和纰朋)都是组合数学，图论，数论的重要数据和概念．对于酬，盹朋)的计数问题有许多结果(见文献【3】-【7】)，而对于Q@m)

3、的计数问题讨论的并不是很多．已有的结果如Q@肌)=㈣，m)+Q(n-m，m-1)，Q(珂，2)=Fa，烈％3)=I垒二妻l兰l等(见文献【l’2】)．对于刀≥4的情形还没有相关的简单统一的表达式．虽然∞，呐的值相对于弛m)的值而言要小一些，但是，计算起来仍然很繁琐．下面我们首先给出Q慨功的一个递推关系，同时建蚍肌)与鲰神之间的直接关系，进而利用已有的一些有关弛神和鲰2)，9∽3)的计数结果来计算∞，枘的值．首先引入几个记号：(1)设，产刀l饥+⋯帆，其中／'／l>，矿⋯>‰≥l，这种分拆的分拆数记为鲰m)．(2)

4、苗2垆刀l+，≯2+⋯+，钿，其中刀I>，12>⋯>，矿f，这种分拆的分拆数记为g惕ml>t)．(3)设劂l埘⋯帆，其中刀I>p⋯砜-f’这种分拆的分拆数记为Q慨圳f)．．(4)k】表示不超过口的最大整数，口为实数．(5)P《M表示将万分拆成无一部分大于m的分拆数．2主要结果2．I，关于纰m)的一个递推关系我们首先给出本文的第一个结果：关于Q以神的一个递推关系，通过此递推关系可以将Q帆m)化成有限个Q以2)和9以3)的和，从而利用鲰2)和Q(惕3)的简单公式计算Q(％神的值．引理l9眩肼)是不定方程(1)的正整数

5、解的个数．xl+2x矿⋯+，，lx_=厅(1)证明设劂I饥+⋯‰，其中以I>rip⋯砜．该分拆的Ferrers图和其共轭图分别如图l和图2所示．易知其共轭图所表示的疗的分拆就对应方程(1)的一个正整数解，并且不同的分拆对应的正整数也不同．反之，(1)的任意一个正整数解(而，而，⋯如)表示了含有x。个1，计2，⋯．‰个m的r／的一个收稿日期：2006-06-05作者简介：郭育红(1970一)，女，甘肃宕昌人，硕士，讲师，主要从事组合数学与图论方面的研究．万方数据郭育红：一类分拆数的计算问题oO⋯OOnloO⋯O／1

6、2●●●●●●●●●o拧所图1刀l忱刀m’ooo⋯ooOO⋯OO●●●●●●●●●●●●●●●o●●●oO●●●O图2分拆．将其从右向左安排而列恰含1个“onip屯列恰含2个“O”，⋯，‰列恰含坍个。O”，使第一行对齐，便得到珂的一个满砌。湖9⋯概的分拆的Ferrets图．以上已证得上述对应关系是一一的，故结论成立．证毕上述证明表明，‰对应于方程(1)中的‰而‘刀一％：一+2吃+．．．+(聊一1)‰≥业掣，所以‰≤堡掣：旦一掣，因此有下Zm‘mZ面的引理．引理2设萨确+时⋯饥，其中啊>矽⋯砜职≤}字]．进一步，(

7、1)的正整数解的个数即为x_取1,2，⋯，}孚卜对应M元不舫酣酣⋯+沏-1k．。=，卜mx．I的正整数解的个数之和．故有引理3Q∽，聊)=∑Q(疗，mI，)，其中，《昙一字]．引理4纰用J垆鳓心肌·11>f)．．证明设，F一1+，12+⋯+，k，刀l>，≯2>⋯>，≈产l(2)上式等价于，卜渤I帆+⋯饥l，刀l>p¨：狐l>，(3)故二者正整数解数相同．设户‰l嵋户0，则‰1．什，斛pf．故(3)的解数为Q(n-t，m-1I>f)．即结论成立．证毕引理5Q(n朋I>沪Q(n-mt，肌)．证明方程％+忱+⋯+，kI

8、-珂，胛l>，p⋯>，II，刀与方程“妒仇-卅⋯嘶‰一t)=n-mt度-(4)是等价的．而nct>l，i=l，2，⋯，m-I；，纠≥1而(4)的正整数的解数Q(n-mt,功，故有∞，mI>r)=Q(n-mt，曲证毕引理6触砷产gn-rot,m·1)．证明由引理4，引理5可得：Q@mlO=Q(n-t,m·1I>D；Q(n-t-(m一1Mm—1)2Q(n-mt，m-1)证毕于