1樓：乘著歌聲的翅膀
糾正一下，lz舉的例子有誤，不懂為什麼沒有2+8，a_n應該等於9。
oeis有收錄該數列，將n拆分成至少2個不同大小的整數的個數。這個數列沒有公式表達。
A111133 - OEIS
倒是有個母函式表示式……
2樓：幷州達人
太久沒複習組合方面的概念，反而想多了。題主的問題其實不需要涉及到貝爾數……不過姑且先把答案留這兒吧。
如果把乙個數分為多個不同的數相加的話，隱約記得leetcode上就有類似的演算法題，我記得沒有O（1）解法，也要用遞迴和動態規劃解決，換句話說，也沒有通項公式。
以下是最開始的回答
這是乙個組合學概念，叫做貝爾數，可以理解為把N個物件分為進行分組的話，總共有多少種分組方式。
直接求貝爾數有些難，所以一般會退而求其次的去求另乙個東西，叫做斯特勞林數，在利用斯特勞林數來求出貝爾數。
斯特勞林數（這裡特指第二類斯特勞林數），意味著把N個東西，分成K組，有多少種分法,一般寫作S(n,k)。
當K為一些特殊數的時候，其實求斯特勞林數很簡單。
比如K為1的時候，意味著把N個東西分為1組，有多少分法，很明顯。只有一種分法。
當然 N為一些特殊數的時候，求的斯特勞林數也會很簡單，比如N為1的時候，如果k也為1，那就只有一種分法，如果K大於1，那就由0種分法，也就是，1個東西不可能分成兩份以上。
然後我們又發現了乙個斯特勞林數的遞推公式。
S(n,k) = S(n-1,k-1)+k*S(n-1,k)
可以這麼想，假設我們想把N個東西分成K份，有兩種情況，第一種情況，我們把前N-1個東西分成K-1份，然後第N個東西自己作為最後乙份，湊成K份。
第二種情況，前面N-1個東西已經可以分成K份了，我們再把最後乙個東西，隨便塞進前面K份裡（也就是說總共有k個選擇可以塞）。
把這種想法轉化成數學公式，就成了上面的寫法。
我們把S(n,k)轉化成 S(n-1,k-1)和S(n-1,k)來表達。不過S(n-1,k-1)和S(n-1,k)也能再次用公式展開，裡面的n和k變得更小。
當我們不斷反覆展開，直到n成為1或者k成為1的時候，這就成了我們上面說的簡單情況，可以直接求出數字了。
那麼怎麼求出原題想要的結果，也就是貝爾數呢？ 我們把K=1,k=2,k=3 ……一直到K=n的情況全部求出來，再加起來，就是原題想要的結果了。
這麼求還是挺複雜的，N一旦很大，那麼計算就很複雜。不過暫時也沒有那種只要把N輸入進去，就立刻能出結果的演算法。只能期待組合學能有進一步突破吧。