把一個正整數分解成若干（大於等於一）個正整數的和，有多少種分法？存在通項公式嗎？

12-30

不考慮順序
舉例：
1=1，1種
2=2=1+1，2種
3=3=2+1=1+1+1，3種

4=4=3+1=2+2=2+1+1=1+1+1+1，5種
5=5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1，7種
...
n呢？

謝邀，

請參考 Partition (number theory)

沒有通項...如果不算生成函數的話...

$frac{1}{(q;q)_{infty }}$ 的在x=0處的泰勒展開係數就是解:

$[frac{1}{{{{(q;q)}_infty }}} = 1 + q + 2{q^2} + 3{q^3} + 5{q^4} + 7{q^5} + 11{q^6} + 15{q^7} + Oleft( {{q^8}} ight)]$

==================================================

這類題的通用秒殺法...

$[prod {frac{1}{{1 - {z^k}}}} ]$ 在z=0點處泰勒展開

其中k是允許的集合,本題就是全體自然數的集合{1,2,3,4...}...

我記得Project Euler上有道題要求使用素數分解...那麼k就取全體素數{2,3,5,7...}

然後兌換硬幣問題,k就取{1,2,5,10}啥的...

反正只要是分解問題就能用這個辦法秒殺掉...

==================================================

還是Mathematica大法好...上億的輸入都能秒算...

用的是Hardy-Ramanujan-Rademacher演算法...

Array[PartitionsP,100]
Rest@CoefficientList[1/QPochhammer[q]+O[q]^101,q]

==========================================

不過自己造輪子刷OJ的話,DP妥妥的超時....

歐拉五邊形數演算法就夠了,十萬以下大概不會超時

五邊形數就是所謂 $[g(n) = frac{{n(3n - 1)}}{2}]$ 的數

容易求出其生成函數就是 $[G(x) = frac{{(2x + 1)x}}{{{{(1 - x)}^3}}}]$

歐拉發現了這個式子和五邊形數的聯繫

$[egin{aligned} prodlimits_{n = 1}^infty {(1 - {x^n})} = (1 - x)(1 - {x^2})(1 - {x^3}) cdots \ = 1 - x - {x^2} + {x^5} + {x^7} - cdots\ = sumlimits_{k = 0}^infty {{{( - 1)}^k}{x^{frac{k}{2}(3k pm 1)}}}\ end{aligned} ]$

有的項消掉了,最後剩下的正好都是無邊形數.

另外歐拉函數的倒數就是我們要求的分割函數P(k)的生成函數...

$[frac{1}{{varphi (x)}} = sumlimits_{k = 0}^infty {P(k){x^k}} ]$

於是就能寫出遞推式:

$[egin{aligned} 1 = varphi (x)sumlimits_{k = 0}^infty {P(k){x^k}} \ = sumlimits_{k = 0}^infty {{{( - 1)}^k}{x^{frac{k}{2}(3k pm 1)}}} sumlimits_{k = 0}^infty {P(k){x^k}} \ = (1 - x - {x^2} + {x^5} + cdots )(1 + {p_1}x + {p_2}{x^2} + {p_3}{x^3} + cdots )\ Rightarrow p(n) = p(n - 1) + p(n - 2) - p(n - 5) - cdots \ end{aligned} ]$

仔細看了一下回答的跟題主說的不一樣。題主要的是拆分成和，每個集合只有數量有意義，而不是N個對象拆分成集合

也就是說實際上是求不定方程解的數量：

$x_1 + x_2 + ... + x_k = N$

其中 $x_1 le x_2 le x_3 ... le x_k$

記得在哪見過這個問題，先更新下回頭再補充

突然看到這個問題，曾經用 nodejs 寫過一個程序玩整數拆分。

const solve = n =&> callback =&> { let rest = n; // the rest number to fill let working = []; // the working array let i = 0; // the current index of working array let mrf = -1; // the most recently filled number


  // loop to find solution

  while (true) {

    // if no rest number to fill, one solution found.

    if (rest == 0) {

      // output the solution

      callback(working.slice(0));

      // if the index exceeds the number n,

      // no more solution, so just return.

      if (i &>= n) return;

      while (true) {

        // try backtracking

        --working[--i];

        ++rest;

        if (working[i] == 0) {

          // remove the trailing zero and continue backtracking

          working.splice(i);

        } else {

          // restore the possible last most recently filled number,

          // break out of the backtracking routine

          // and try to filling the rest number.

          mrf = working[i++];

          break;

        }

      }

    } else {

      // if i == 0, means that we are filling the first number,

      // it"s unconditionally ok to

      // fill the rest number altogether in the next blank.

      // if rest &< mrf, means that we can
      // ensure a descending order filling to avoid repetitions.
      // i.e. during filling, a partition sequence 3-2-1-1
      // can also appear as 2-1-3-1, and 1-2-1-3,
      // and 1-1-3-2, and so forth,
      // forcing a descending order will make it
      // always be 3-2-1-1 identically.
      let value = (i == 0 || rest &< mrf) ? rest : mrf;
      mrf = working[i++] = value;
      rest -= value;
    }
  }
};

solve(7)(a =&> console.log(a.join("+")));

// 7

// 6+1

// 5+2

// 5+1+1

// 4+3

// 4+2+1

// 4+1+1+1

// 3+3+1

// 3+2+2

// 3+2+1+1

// 3+1+1+1+1

// 2+2+2+1

// 2+2+1+1+1

// 2+1+1+1+1+1

// 1+1+1+1+1+1+1
// to calculate the count of partitions

const s = n =&> (x =&> (solve(n)(_ =&> x = x + 1), x))(0);

s(7) // 15 s(60) // 966467

另外，我自己推導了一個遞推演算法，可以直接求整數拆分的個數。

const Cache = class { constructor() { this.map = new Map(); } get(i, j) { const m = this.map.get(i); return m ? m.get(j) : undefined; } set(i, j, value) { let m = this.map.get(i); if (!m) this.map.set(i, m = new Map()); m.set(j, value); return value; } };


const p = (n, m) =&> {

  const cache = new Cache();

  const p = (n, m) =&> {

    if (m == null || m &> n) m = n;

    if (n &< 0 || n &> 0  m &< 1) return 0
    else if (n &<= 1 || m == 1) return 1;
    else if (n == 2) return 2;
    else if (m == 2) return (n + 2) &>&> 1;
    let v = cache.get(n, m);

    if (v) return v;
    if (n &> m) {

      v = p(n - m, m) + p(n, m - 1);

      cache.set(n, m, v);

      return v;

    }

    else {

      let v = 0, i = 0;

      while(i &< m  n - i &>= 0) {

        i++;

        v += p(n - i, i);

      }

      cache.set(n, m, v);

      return v;

    }

  };

  return p(n, m);

};

p(7) // 15 p(60) // 966467 p(299) // 8620496275465025

我們考慮把正整數n，分成m個正整數的和。

首先我們很容易想到一個dp方程，這是用完全背包實現的。

設dp[i][j]表示把i拆分，最大的數不超過j。

轉移很簡單，dp[i][j]=dp[i-j][i]+dp[i][j-1]。其中前者表示用了j，後者表示沒用j。

我們發現這樣的複雜度是O(n^2)的。

如果你水平高一點，你可能想到另一個稍微巧妙一點的dp方法。

設dp[i][j]表示把i拆分成j個正整數的和。

這個方程並不好推，我們考慮「有1」和「沒有1」這兩種情況。

如果有1，方法就是dp[i-1][j-1]（把1拿去）

如果沒有1呢？這個就挺有意思了，我們把這j個數，每個數都減1。

j個數的和等於i，而每個數-1，就變成了j個數的和等於i-j。

也就是說，這種情況是dp[i-j][j]

綜上所述，dp[i][j]=dp[i-1][j-1]+dp[i-j][j]。

到了這一步，我們發現自己一直在做無用功，因為上面的方法，仍然是O(n^2)的

看樣子這道題就到這裡為止了。

其實並不是的，接下來就開始神奇了。

我們定義一個M≈sqrt(n)

把所有的數分成兩類，一類是大於M的，一類是小於M的。注意到要想弄到n，大於M的數不超過M個（因為M≈sqrt(n)）。

我們設F[i][j]表示，把數字i拆成正整數的和，最大數不超過j。這就是第一個dp方法，但是我們這裡j的循環上界是M。

再設G[i][j]表示把數字i拆成j個正整數的和，但是！！這j個正整數各個都＞M！！

怎麼轉移呢？其實和第二個dp方法極其類似，只不過把1變成M，也就是dp[i-M][j-1]+dp[i-j][j]。

注意到由於大於M的數不超過M個，所以j的循環上界也是M。

到了這一步，我們基本上就知道f[i]表示，用1~M這些數拆出i的方案數了，接著也知道g[i]表示M+1~n這些數拆出i的方案數了。

接著只要算Σf(i)*g(n-i)即可。

該問題在O(n^1.5)的時間複雜度內解決，空間複雜度也是O(n^1.5)，如果用滾動數組似乎能壓到O(n)來著

注意到最後那一步是一個卷積。

我們能用FFT，在O(n log n)的時間複雜度里，求出對於i=1~n，i的拆分數。

然後這東西也是有生成函數的，叫什麼五邊形數還是啥的，我比較弱就不瞎BB了。

由於這東西好久以前看的了，可能打錯了一些地方，求指出

謝邀。

設整數 $n$ 能劃分的種數為： $P(n)$ 。

那麼，對於 $n>1$ 時， $P(n)=1+ sum_{k=1}^{n}{} {(-1)}^{k+1} {*} { [ P(n-frac{k*(3*k+1)}{2})+P(n-frac{k*(3*k-1)}{2})] }$ 。

其中 $P(1)=1$ ， $P(0)=1$ ， $P(n<0)=0$ 。

或者第二種：

$P(n) = P(n - 1) + P(n - 2) - P(n - 5) - P(n - 7) + ldots$

詳見oi題：數的劃分

整數劃分問題是這個題吧？

給個OEIS的鏈接：A000041 - OEIS

印象中有nsqrt(n)的五邊形數以及nlogn的FFT兩種做法。

用遞歸就可以了。這應該是百度的一道面試題。

通項公式不會，但是可以推一下遞推公式

$left{egin{matrix} L(n, m) = L(n - m, m) + L(n, m - 1) (n >= m) \ L(n, m) = L(n, n) (n < m) end{matrix} ight.$

然後注意一下初始條件

L(n, m)代表拆分數字n的各項中最大數不超過m的組合方式數

參考題目ID: HDU 1028

DP方程: dp[n][k] = dp[n][k-1] + dp[n-k][k]

（dp[n][k]表示劃分n，最大數小於等於k的方案數）

遞歸解法

拉馬努金研究過

傳說中的組合拆分問題啊，用母函數

整數的分拆問題在很多組合數學書里都有論述，一般記p(n)為n的分拆個數。p(n)有很奇妙的性質，但這個暫且不提，我們只關心p(n)的大小，甚至具體數值。

以下用手機碼公式，很醜，請見諒。為通俗起見就不用latex來表示了。

考慮級數∑p(n)x^n，這裡求和範圍是n≥0，並且補充定義p(0)=1，那麼這個級數對於收斂的x而言收斂到∏1/(1-x^n)，求積範圍是n≥1。這是比較熟知的事。我們可以用哈代和拉馬努金給出的漸進公式快捷地估計它的大小：p(n)~exp(π*sqrt(2n/3))/(4n*sqrt(3))

，這裡~表示左右兩邊之比在n趨於無窮時極限為1。

那麼有沒有可以算出它的值的方法呢？有的，如果只關心某個具體的n，使用遞推來計算即可滿足應用需要。如果關心一般的n，這是結果：1936年拉德馬赫給出了p(n)的級數表達式，次年塞爾伯格也獨立得到相同結果，但是這個級數相當複雜。

最後提一下p(n)的神奇性質，即拉馬努金分拆等式：p(5n+4)≡0(mod 5)，p(7n+5)≡0(mod 7)，p(11n+6)≡0(mod 11)。

分拆的資料可以在組合數學(應該很多都有)、解析數論(比如阿波斯托爾)里找到，順便附上維基百科：https://en.m.wikipedia.org/wiki/Partition_(number_theory)