Project Euler 172

题目

Investigating numbers with few repeated digits

How many \(18\)-digit numbers \(n\) (without leading zeros) are there such that no digit occurs more than three times in \(n\)?

多重全排列公式

多重全排列公式：假设使用\(r_1\)个相同元素\(c_1\)，\(r_2\)个相同元素\(c_2\)，\(\dots\)，\(r_n\)个相同元素\(c_n\)，那么可以构成以下数量的不同全排列个数：

\[\dfrac{(\sum_{i=1}^nr_i)!}{\prod_{i=1}^nr_i!}\]

解决方案

由于每个数位最多使用\(3\)次，因此分别枚举有\(i,j,k,h(h+i+j+k=10)\)个数位使用了\(1\)次，\(2\)次，\(3\)次，或者没有使用。由此，现在问题变成了两个独立的子步骤：这\(i,j,k,h\)个数位对应到\(10\)个数位，有多少种对应方式？当数位对应好后，有多少个排列？

第一个步骤：分配各个数位的对应次数的数量为\(\dbinom{10}{i}\dbinom{10-i}{j}\dbinom{10-i-j}{k}=\dfrac{10!}{i!\cdot j!\cdot k!\cdot h!}\)。

第二个步骤：使用多重全排列公式，可以得到\(\dfrac{N!}{(0!)^h\cdot(1!)^i\cdot(2!)^j\cdot(3!)^k}\)。

两个步骤前后相互独立，故相乘。

注意这里要求不包括前导\(0\)，由于每一个数位填在最高位的概率都是平等的，因此最终答案需要乘个\(\dfrac{9}{10}\)。

代码

N = 18
M = max(N, 10)
fac = [1]
for i in range(1, M + 1):
    fac.append(fac[-1] * i)
ans = 0
for i in range(11):
    for j in range(11 - i):
        for k in range(11 - i - j):
            if i + 2 * j + 3 * k == N:
                h = 10 - i - j - k
                a = fac[N] // 2 ** j // 6 ** k
                c = fac[10] // fac[h] // fac[i] // fac[j] // fac[k]
                ans += a * c

ans = ans * 9 // 10
print(ans)