0172 少量重复数字
* * * *
拉格朗日计划
* * * *
少量重复数字

任意数字都只出现不超过三次的18位数共有多少个?

本题难度:



解答

设有i个数出现了一次,j个数出现了两次,k个数出现了三次,相应地有$10-i-j-k$个数没有出现。

对应的数字组合共有 $$\binom{10}{i}\binom{10-i}{j}\binom{10-i-j}{k},$$ 种。在每种组合中通过不同排列得到不同的数,排列总数共有 $$\frac{18!}{(2!)^j(3!)^k},$$ 种。最后,上述排列中有些以0开头,这样的排列并不是合法的18位数,需要排除。

由于0以均等的概率出现在首位,因此直接乘以$9/10$即可。最终结果是 $$\sum_{\substack{i,j,k\in\{0,1,\ldots,10\} \\ i+j+k\le10 \\ i+2j+3k=18}}\binom{10}{i}\cdot\binom{10-i}{j}\cdot\binom{10-i-j}{k}\cdot\frac{18!}{(2!)^j(3!)^k}=227485267000992000.$$
n=6402373705728000 # =18!
a=[2**i for i in range(11)]
b=[6**i for i in range(11)]

c=[[1],[1,1]]

for i in range(2,11):
    c.append([1]+[c[-1][j]+c[-1][j+1] for j in range(i-1)]+[1])
      
print sum(c[10][i]*c[10-i][j]*c[10-i-j][k]*n/a[j]/b[k] for i in range(11) for j in range(11-i) for k in range(11-i-j) if i+2*j+3*k==18)*9/10