📄 2_6.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.6 整数的拆分和Ferrers图像 </h1><p> §2.6.1 问题举例 </p> <p> 所谓整数拆分即把整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。 </p> <p> 例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？ </p> <p> <img border="0" src="2_6.pic/image002.gif" width="219" height="99"></p> <p> 从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x<sup>5</sup> 项，即称出5克的方案有2：5=3+2=4+1，同样，6=1+2+3=4+2；10=1+2+3+4。故称出6克的方案有2，称出10克的方案有1 </p> <p> 例2：求用1分、2分、3分的邮票贴出不同数值的方案数。 </p> <p> 因邮票允许重复，故母函数为 </p> <p> <img border="0" src="2_6.pic/image006.gif" width="251" height="51"></p> <p> 以其中x<sup>4</sup>为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即 </p> <p> <img border="0" src="2_6.pic/image008.gif" width="243" height="19"></p> <p> 例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？ </p> <p> <img border="0" src="2_6.pic/image010.gif" width="301" height="177"></p> <p> 例4: 整数n拆分成1，2，3，…，m的和，并允许重复，求其母函数。如若其中m至少出现一次，其母函数如何？ </p> <p> 若整数n拆分成1，2，3，…，m的和，并允许重复，其母函数为： </p> <p> <img border="0" src="2_6.pic/image012.gif" width="271" height="51"></p> <p> <img border="0" src="2_6.pic/image014.gif" width="271" height="141"></p> <p> 若拆分中m至少出现一次，其母函数为： </p> <p> <img border="0" src="2_6.pic/image016.gif" width="272" height="100"></p> <p>显然有 </p> <p> <img border="0" src="2_6.pic/image018.gif" width="296" height="91"></p> <p>等式(2-6-1)的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。</p> <p> 例1：若有1、2、4、8、16、32克的砝码各一枚，问能称出那几种重量？有几种可能方案？ </p> <p> <img border="0" src="2_6.pic/image020.gif" width="293" height="144"></p> <p> 从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。 </p> <p> 这问题可以推广到证明任一十进制数n，可表示为 </p> <p> <img border="0" src="2_6.pic/image022.gif" width="200" height="36"></p> <p>而且是唯一的。 </p> <p>§2.6.2 拆分数估计式 </p> <p> 定理：设p<sub>n</sub>为整数n的拆分数，则 </p> <p> <img border="0" src="2_6.pic/image026.gif" width="69" height="39"></p> <p> 证：令</p> <p> <img border="0" src="2_6.pic/image028.gif" width="179" height="25"> </p> <p> 一个整数n拆分成若干整数的和，在拆分中每个整数允许重复出现。故 </p> <p> <img border="0" src="2_6.pic/image030.gif" width="199" height="44"></p> <p> <img border="0" src="2_6.pic/image032.gif" width="233" height="136"></p> <p> <img border="0" src="2_6.pic/image034.gif" width="296" height="197"></p> <p> <img border="0" src="2_6.pic/image036.gif" width="223" height="44"></p> <p>由于 </p> <p> <img border="0" src="2_6.pic/image038.gif" width="161" height="24"></p> <p> <img border="0" src="2_6.pic/image040.gif" width="272" height="69"></p> <p> 把(2-6-3)式代入(2-6-2)式得 </p> <p> <img border="0" src="2_6.pic/image042.gif" width="263" height="85"></p> <p>由于 </p> <p> <img border="0" src="2_6.pic/image044.gif" width="183" height="61"></p> <p>因而 </p> <p> <img border="0" src="2_6.pic/image046.gif" width="260" height="167"></p> <p>设 x€(0,1)，有 </p> <p> <img border="0" src="2_6.pic/image050.gif" width="277" height="120"></p> <p>把(2-6-4)式代入(2-6-5)式得 </p> <p> <img border="0" src="2_6.pic/image052.gif" width="269" height="41"></p> <p>曲线z=lny 是上凸，故曲线位于曲线z=lny的切线下方，点(1,0) 的切线为z=y-1故有 </p> <p> **</p> <p> (图 (2-6-1)) 缺 </p> <p> <img border="0" src="2_6.pic/image064.gif" width="72" height="41"> </p> <p>以上式代入(2-6-5)式得： </p> <p> <img border="0" src="2_6.pic/image066.gif" width="279" height="91"> </p> <p> 不等式(2-6-7)的左端lnp<sub>n</sub> 是常数，右端是x的函数 ，即不等式对于x€(0,1) 成立。右端函数取极小值时将给出较好的上界值。令 </p> <p> <img border="0" src="2_6.pic/image072.gif" width="143" height="44"> </p> <p>求导得 </p> <p> <img border="0" src="2_6.pic/image074.gif" width="121" height="44"> </p> <p>令ý=0 ，得 </p> <p> <img border="0" src="2_6.pic/image078.gif" width="159" height="24"> </p> <p>解方程，得 </p> <p> <img border="0" src="2_6.pic/image080.gif" width="273" height="93"> </p> <p> <img border="0" src="2_6.pic/image082.gif" width="220" height="44"> </p> <p>x<sub>2</sub>是极小值。以x<sub>2</sub> 的值代入y，得 </p> <p> <img border="0" src="2_6.pic/image087.gif" width="71" height="47"></p> <p> <img border="0" src="2_6.pic/image089.gif" width="105" height="39"> </p> <p>利用 </p> <p> <img border="0" src="2_6.pic/image091.gif" width="137" height="44"> ，</p> <p>上式可改进为 </p> <p> <img border="0" src="2_6.pic/image093.gif" width="75" height="39"> </p> <p>§2.6.3 Ferrers图像 </p> <p> 一个从上而下的n层格子，m<sub>i</sub> 为第i层的格子数，当m<sub>i</sub>>=m<sub>i+1</sub>(i=1,2,<sup>...</sup>,n-1) ，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如图(2-6-2)示。 </p> <p> <img border="0" src="2_6.pic/image123.gif" width="327" height="245"></p> <p> 图 (2-6-2)</p><p> Ferrers图像具有如下性质： </p> <p> 1.每一层至少有一个格子。 </p> <p> 2.第一行与第一列互换，第二行于第二列互换，…，即图(2-6-3)绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers 图像称为一对共轭的Ferrers图像。 </p> <p> 利用Ferrers图像可得关于整数拆分的十分有趣的结果。 </p> <p> (a)整数n拆分成k个数的和的拆分数，和数n拆分成个数的和的拆分数相等。 </p> <p> 因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如： </p> <p> <img border="0" src="2_6.pic/image124.gif" width="563" height="357"></p> <p> 图 (2-6-3) </p><p> (b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。 理由和(a)相类似。 </p> <p> 因此，拆分成最多不超过m个数的和的拆分数的母函数是 </p> <p> <img border="0" src="2_6.pic/image102.gif" width="156" height="44"></p> <p> 拆分成最多不超过m-1个数的和的拆分数的母函数是 </p> <p> <img border="0" src="2_6.pic/image104.gif" width="165" height="44"></p> <p> 所以正好拆分成m个数的和的拆分数的母函数为 </p> <p> <img border="0" src="2_6.pic/image106.gif" width="205" height="140"></p> <p> (c)整数n拆分成互不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等. 设 </p> <p> <img border="0" src="2_6.pic/image108.gif" width="243" height="24"></p> <p>其中n<sub>1</sub>>n<sub>2</sub>><sup>...</sup>>n<sub>k</sub> </p> <p> 构造一个Ferrers图像，其第一行，第一列都是n<sub>1</sub>+1格，对应于2n<sub>1</sub>+1，第二行，第二列各n<sub>2</sub>+1格，对应于2n<sub>2</sub>+1。以此类推。由此得到的Ferres图像是共轭的。反过来也一样。 </p> <p> 例如 17=9+5+3 对应为Ferrers图像为 </p> <p> <img border="0" src="2_6.pic/image125.gif" width="510" height="267"> </p> <p> 图 (2-6-4) </p><p> </p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -