拆分数估计
数学术语
整数的拆分问题,即将正整数n分解为若干个正整数的和。不考虑起求和的顺序。正整数的一种拆分可以理解为将n个无区别的球,放入n个无区别的盒子,其每种方案就是一种拆分。一般来说现在整数的拆分问题求解的常用工具是母函数和Ferrers图像。整数拆分在组合数学、群论、概率论、数理统计学等方面都有重要应用,但当n比较大时,计算机复杂度高,所以这里给出一种关于拆分数估计的定理与证明,便于拆分数的推广与应用。
拆分数估计定理
正整数n拆分成若干个正整数之和,其不同的拆分数用p(n)表示,{p(n)}的母函数为:
则拆分数估计可以表示为:
证明
根据马克罗林级数:
所以:
又由于
所以有下式成立:
因此有
所以
但是
所以
设 有
曲线y=lnx是向上凸的,所以曲线y=lnx在(1,0)的切线为y=x-1,即有 .
所以
对于 ,令其一阶导 ,方程的解为
又因为y的二阶导 ,所以y的极小值为
所以
应用
1.一般情况下,p(n)的递推关系比较复杂,但很多情况我们往往不需要知道确切的拆分数,我们可以用拆分数估计定理来估计拆分数的上界;p(n)的渐进公式也是很多学者研究的课题。
2. 图论,组合论等领域中有广泛应用。
参考资料
最新修订时间:2024-05-21 15:34
目录
概述
拆分数估计定理
证明
参考资料