一百顆糖，發給十個小朋友，要求每個小朋友都有糖，且不存在兩個小朋友手上的糖一樣多，問一共有多少種分法？

01-29

正兒八經的數學問題，本人大三，解不出來，感覺理科生的尊嚴遭到了挑戰

SeriesCoefficient[ Product[1/(1 - x^n), {n, 10}], {x, 0, 45}]

最終答案是 33401 種。

小孩都看成一樣的話，題目就是要求 $x_1+x_2+cdots+x_{10}=100$ 在 $0<x_1<x_2<cdots<x_{10}$ 時的整數解。令 $t_1=x_1-1,t_2=x_2-x_1-1,cdots,t_{10}=x_{10}-x_{9}-1$ . 則所有的 $t$ 都是非負整數。原方程現在變成了 $10t_1+9t_2+cdots+t_{10}=45$ . 這個方程的非負整數解就是級數 $prod_{i=1}^{10} frac{1}{1-x^i}$ 在 $x^{45}$ 處的係數。然後用 Mathematica 算出了答案。如果小孩不一樣，將前面的結果乘以 $10!$ 就可以了。

如果不考慮小朋友之間的區別，即A分到2顆B分到1顆的情況和A分到1顆B分到2顆的情況視為同一種，那麼共有33401種分法

如果考慮小朋友之間的區別，那麼共有33401*10! = 121205548800種分法

用Mathematica純暴力枚舉的，算了8秒多出的結果，代碼如下，ans里保存了所有可能的分配方法。

ans = Select[IntegerPartitions[100, {10}], UnsameQ @@ # ]; num = Length[ans] num*10!

理論演算法暫時還沒想出來。。。

更新了簡單解釋

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

題目就是求n分成m個不同正整數（不考慮順序）的和的方法數，直觀上就和劃分數同一難度的。方法也基本一樣：生成函數（ @鄭育強），暴力（ @無影東瓜等），和遞推：

令f[n, m, min]表示把n分成m個不同正整數（不考慮順序）的和並且每個數都不小於min的方法數，則

f[n_, 1, min_] := Boole[n &>= min] f[n_, m_, min_] := Sum[f[n - i, m - 1, i + 1], {i, min, n/m}]

第一行是指把n分成1份，並且這一份&>=min的方法數。顯然當n&>=min時為1，否則為0；

第二行是考慮這m份中最小的一份，設為i。除去這一份，剩下的n-i分成了m-1份，並且每份都&>=i+1。考慮所有可能的i並求和就是最後結果。

結果就是

f[100, 10, 1] 33401

感興趣也可以看看wikipedia Partition (number theory)

另外這方法極其簡單粗暴，很容易優化。例如 @薩摩公園的答案

菜魚ftfish 的方法可以進一步優化，例如 f[n_, m_, min_] 實際上可以寫成 f[n_-m_*(min_-1), m_, 1]

這樣就能把 min 這個維度消掉，方程改寫如下

f[n_, 1] := Boole[n &> 0] f[n_, m_] := Sum[f[n - i * m, m - 1], {i, 1, n/m}]

我試著計算了一下，然後突然有了一種想舉報這個問題的衝動。。。。。。。。。

#coding=utf-8 #此為python代碼


child = [0]*10

n = 0

COUNT = 0

f = open(/Users/pengzhenghao/desktop/result.txt, w)
#遞歸函數。第一項為待分割的數（即上次分割之後右邊的數）。第二項為上次

#分割之後，左邊的數。第三項為數組。第四項為遞歸層數，或者是待填充的數組的下標。

def setnumber(divide, lastleft, list, tier):

    #引入全局變數計數

    global COUNT

for i in range(lastleft+1, 101): list[iter] = i #把數字divide分成左右兩部分 list[iter+1] = divide-i if list[iter+1] &<= list[iter]:#循環出錯，退出 break if iter == 8: #遞歸終止條件 f.write(str(list)) #寫入文件 COUNT += 1 #計數 continue setnumber(list[iter+1], list[iter], list, iter+1) #開始運算 setnumber(100,0,child,0) print(COUNT) f.close()

拙作一篇，結果是33401。

另外這是不考慮小朋友全排列的結果。小朋友的全排列是

$A_{10}^{10} =10!=3628800$

因此總數是：121,205,548,800

不考慮全排列，所有可能的情況見下：

Length[Solve[

q + w + e + r + t + y + u + i + o + p == 100

q &> w &> e &> r &> t &> y &> u &> i &> o &> p &> 0, {q, w, e, r, t, y, u, i,

o, p}, Integers]]

雖然有點蠢。。。

殺死九個小朋友。

這是你侄子問你的暑假作業嗎？

百度：小學奧數-插板法。

純理論演算法的話

我不知道你理論基礎到多少

但現在我只知道非同步差分，直接套公式就可以。

三十年前的十萬個為什麼里有類似的題

頂上一隊大神都給出了理論演算法，這裡給個學渣演算法。

寫個程序枚舉唄_(:з」∠)_

這個題可能性太多了，前面大神的解答還看不懂，感覺數學白學了

def sugar(k,x,aj): if sum(range(aj+1,aj+12-k))&>x:return 0 elif k==10:return 1 else:return sum([sugar(k+1,x-ak,ak) for ak in range(aj+1,x+1)]) print(sugar(1,100,0))

硬生生湊起來的代碼，其中的數學部分都是中學水平，應該很容易看懂 (??ˇ_ˇ??) 。

算下來1秒不到，核心思想就是

x0&同時，動態求解xi可取的最大值

先要個位置，回家後答題。