一道有关排列组合的问题(求正整数s分成n个正整数的方法数)
来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/05/12 07:47:27
一道有关排列组合的问题(求正整数s分成n个正整数的方法数)
首先,对于不定方程
x(1)+x(2)+...+x(n)=s (s>=n>=1)
的正整数解的个数为 C(s-1,n-1)=C(s-1,s-n) 种
但是,如果规定x(1)
首先,对于不定方程
x(1)+x(2)+...+x(n)=s (s>=n>=1)
的正整数解的个数为 C(s-1,n-1)=C(s-1,s-n) 种
但是,如果规定x(1)
你的两个问题在数学界早有人探索过了.叫做拆分数问题.是组合数学研究的课题.
你的第一个问题等价于将整数s拆分为n个正整数的拆分数.关于这个问题有几个定理:
1.将整数r拆分为k个正整数的拆分数,等价于将r拆分为最大数为k的拆分数.证明略,你有兴趣可以去搜索下费勒斯图像.
2.将整数r拆分为重复度不超过k的拆分数,等价于将r拆分为不能被k+1整除的拆分数.可以用母函数证明.
所以你的第一个问题可以等价成将s拆分为最大数为n的拆分数,或者将s-n拆分为最大数不超过n的拆分数.
关于该拆分数的编程上的计算方法目前有很多,但是据我所知,在数学上目前还没有公式可以表示.递推公式也没有.
你的第二个问题中的k很容易求,这个k叫做一般拆分数,记做p,例如p(5)=7.
有如下递推关系:
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+...+(-1)^(m-1)*p(n-1/2*m(3m+或-1)),这个也可以用母函数证明.一句多余的话,母函数是组合数学中的重要工具.
还有关于拆分数的穷举,在数学上也没有有效的办法,还是需要借助计算机.
如果你希望获得关于拆分数穷举的程序或者算法,可以再联系我.本人是学计算机的.
你的第一个问题等价于将整数s拆分为n个正整数的拆分数.关于这个问题有几个定理:
1.将整数r拆分为k个正整数的拆分数,等价于将r拆分为最大数为k的拆分数.证明略,你有兴趣可以去搜索下费勒斯图像.
2.将整数r拆分为重复度不超过k的拆分数,等价于将r拆分为不能被k+1整除的拆分数.可以用母函数证明.
所以你的第一个问题可以等价成将s拆分为最大数为n的拆分数,或者将s-n拆分为最大数不超过n的拆分数.
关于该拆分数的编程上的计算方法目前有很多,但是据我所知,在数学上目前还没有公式可以表示.递推公式也没有.
你的第二个问题中的k很容易求,这个k叫做一般拆分数,记做p,例如p(5)=7.
有如下递推关系:
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+...+(-1)^(m-1)*p(n-1/2*m(3m+或-1)),这个也可以用母函数证明.一句多余的话,母函数是组合数学中的重要工具.
还有关于拆分数的穷举,在数学上也没有有效的办法,还是需要借助计算机.
如果你希望获得关于拆分数穷举的程序或者算法,可以再联系我.本人是学计算机的.
给正整数n,求n分为4个小于十的非负整数的方法数S(n).求公式 其中顺序不同算不同的方法.
求最大正整数n,使得n为集合S中的元素,且满足(1)S中的每个数均为不超过2002的正整数
有关完全平方数的问题已知n是正整数 4^7+4^n+4^1998是一个完全平方数 求n的值
求java程序:输入N个正整数,按升序排列输出,并计算最大正整数与最小数的阶层.
关于编程大赛的一道题目,一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,找出这样的数并输出!
n是满足下列条件的正整数中最小的数:(1)n是75的倍数(2)n恰有75个正整数因子,求n/7
c语言删数问题【问题描述】通过键盘输入一个正整数n,去掉其中任意s个数字后,剩下的数字按原左右次序,将组成一个新的正整数
怎么证明一个正整数n是完全平方数的充分必要条件是n有奇数个因子?求详细证明方法
和为10的正整数有多少个排列组合
2的n次幂+256是完全平方数(n为正整数)求n
求教一道处二数学题有一个正整数n,n的八分之一是平方数,n的九分之一是立方数,n 的二十五分之一是五次方数,求正整数n最
求正整数列前n个的奇数的和?