In [1]:
# a(d,k) = number of d-digit numbers containing only the digits 1 through k such that
# no digit occurs more than three times.
#
# The following recurrence is satisfied:
# a(d, k) = sum (i=0 to 3) c(d+1, i) * a(d-i, k-1)
# where c() is a binomial coefficient.
#
# The final answer (inserting the zeros last) is
# a(d, 10) = sum (i=0 to 3) c(d, i) * a(d-i, 9)
# The replacement of c(d+1, i) with c(d, i) occurs because leading zeros are not permitted.
from collections import Counter
def c(n,r):
if n < 0 or r < 0 or r > n:
return 0
c = 1
for k in range(r):
c = (c * (n-k)) // (k+1)
return c
a = Counter()
a[0] = 1
for k in range(10):
e = (k == 9)
for d in range(18, 0, -1):
a[d] += sum(c(d-e, i) * a[d-i] for i in [1,2,3])
print(a[18])
In [ ]: