當前位置:成語大全網 - 新華字典 - 壹道有關排列組合的問題(求正整數s分成n個正整數的方法數)

壹道有關排列組合的問題(求正整數s分成n個正整數的方法數)

妳的兩個問題在數學界早有人探索過了.叫做拆分數問題.是組合數學研究的課題.

妳的第壹個問題等價於將整數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)),這個也可以用母函數證明.壹句多余的話,母函數是組合數學中的重要工具.

還有關於拆分數的窮舉,在數學上也沒有有效的辦法,還是需要借助計算機.

如果妳希望獲得關於拆分數窮舉的程序或者算法,可以再聯系我.本人是學計算機的.