組合數學 - 組合數的個數組合數的個數

輸入一個n,然後輸入n個一位數，求這n個數組成的不重複出現的整數的總和。

Mean: 

 略

analyse:

 這樣的數可以是1~n位，總共數的數目為：P(n,1)+p(n,2)+p(n,3)+.....+p(n,n)個。(其中p(n,m)表示從n個數中選m個數組成的排列的數目)。

若将這些數全部羅列出來再來求和，這不是一個好辦法。其實我們可以将個位的和a1求出來，然後十位的和a2求出來，然後百位，然後千位......直到第n-1位。

那麼最後的和就是：

sum=a1*1+a2*10^1+a3*10^2+a4*10^3.....an-1*10*n-2;

具體參看《組合數學.第三版》：P13

Time complexity：O(n^2)

Source code：