资源描述：
《Ferrers图在正整数拆分中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第9卷第1期太原师范学院学报(自然科学版)Vol.9No.12010年3月JOURNALOFTAIYUANNORMALUNIVERSITY(NaturalScienceEdition)Mar.20103Ferrers图在正整数拆分中的应用尹飞杨方燕子宗(长江大学信息与数学学院,湖北荆州434023)〔摘要〕正整数的拆分与许多计数问题有着密切的关系.文章运用Ferrers图讨论了正整数拆分问题,得到正整数拆分的共轭拆分表达式,证明了正整数进行拆分的拆分数,可转化为求较小m(m+1)数n-的拆分数.2〔关键词〕正整数;拆分数;Ferrers图〔文章编号〕
2、167222027(2010)0120051203〔中图分类号〕O157〔文献标识码〕A0引言正整数的拆分是组合数学、图论、数论研究的一个重要课题,拆分过程就是将正整数n分解为若干个与次序无关的正整数的和,一般假设n=n1+n2+⋯+nm,n1≥n2≥⋯≥nm.针对一个整数n的所有可能拆分方式的个数称为n的拆分数,一个具体拆分中所分成的正整数的个数m称为分部数,而对应分成的m个正整数称为拆分的分部量.本文利用Ferrers图像对正整数拆分问题进行了一些探讨,从中总结出了几个有意义的结论.1基本概念[1]定义1设n=n1+n2+⋯+nm,n1≥n2≥⋯
3、≥nm是任一个分部数为m的n拆分,则它对应于一个由n个点构成的行数为m,列数为k点阵图:第i(i=1,2,⋯,m)行有ai个点,且每一行的第j(1≤j≤a1)个点位于第j列中,这个点阵图称为该拆分的Ferrers图.将第一行与第一列对调,第二行与第二列对调,⋯⋯所得到的图仍然是Ferrers图,并称这两个图是一对共轭的Ferrers图.[2]性质1一个整数n拆分成恰好为m部分的拆分数,等于这个整数n拆分成最大部分为m的拆分数.[2]性质2整数n拆分成最多有m部分的拆分数,等于这个整数拆分成每一部分不超过m的拆分数.[2]性质3整数n的Ferrers图
4、为自共轭的拆分数与整数n拆分为若干个互异奇数的拆分数相等.2主要结果定理1(共轭Ferrers图的拆分表达式)若整数n拆分成m部分的表达式为:n=a1+a2+⋯+an,a1≥a2≥⋯≥am,则其共轭拆分表达式为:n=am3m+(am-1-am)3(m-1)+⋯+(am-i-am(i-1))3(m-i)+⋯+(a1-a2)31其中(am-i-am-(i-1))3(m-i)只是一种符号,表示有am-i-am(i-1)个m-i相加,即(m-i)+⋯+(m-i).am-i-am-(i-1)个证明设整数n拆分成m部分的表达式为:n=(a1+a2+⋯+am(a1
5、≥a2≥⋯≥am),做出其相对应的Ferrers图(见图1)和共轭Ferrers图(见图2).3收稿日期:2009212224作者简介:尹飞(19852),男,云南曲靖人,长江大学信息与数学学院在读硕士研究生,主要从事最优化理论与计算的研究.52太原师范学院学报(自然科学版)第9卷km●●●●···●a1●●●····●n1●●●●··●a2●●●···●n2●●●●·●a3●●●··●n3····…●●●·●n4m···●k···…··●am-2··●nk-2·●am·●nk-11●am●nkn1n2n3n4⋯nk-1nka1a2a3⋯am-2am
6、-1am图1Ferrers图图2共轭Ferres图Fig.1FenrersgraphFig.2ConjugateFerrersgrnph由互为共轭Ferrers图的定义可知:图1的m行k列转换成了图2的m列k行,即图2的第一行元素个数为m,而且我们还可以看出,图1中最后一行有am个元素就对应图2中最大部分有am行,最大部分有m个元素.图1中倒数第二行比倒数第一行多am-1-am个元素就对应于图2中次最大部分有am-1-am行,次最大部分有m-1个元素,以此类推下去,图1中第一行比第二行多a1-a2个元素对应于图2的最小部分有a1-a2行,最小部分有1
7、个元素.由此得到:m+⋯+m(m-1)+⋯+(m-1)(m-i)+⋯+(m-i)1+1+⋯+1++⋯++⋯+我们可以用am个am-1-am个am-i-am(i-1)个a1-a2个n=am3m+(am-1-am)3(m-1)+⋯+(am-i-am(i-1))3(m-i)+⋯+(a1-a2)31来表示.m(m+1)定理2把整数n分裂成m个不同部分的拆分数,等于把整数n-分裂成最多m个部分的拆2m(m+1)分数.这里n>.2证明正整数n分裂成m个不同部分就是把正整数刚好拆分为m个不相等的数之和,设这m个数为a1,a2,⋯,am,并且a1>a2>⋯>am,把
8、问题考虑成把n个点放入m行中,使其能满足n的一个不允许重复[3]m拆分.为此可进一步思考,先从这n个点中取出
