Statement

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

Solution

In this as in most combinatoric problems I decided to use a Dynamic Programming, top-down with memorization approach.

The base case is determined by the remaining length: If the remaining length is 1 then we just return the number of digits that appear less than 3 times.

If the length is > 1 then the result is the sum of:

• If there are digits that appear twice: The number of combinations of length - 1 where there is 1 more digit that has 3 appearances, 1 less digit that has 2 appearances and the same number of digits with 1 appearances, multiplied by the number of digits that appear twice.
• If there are digits that appear once: The number of combinations of length - 1 where there is number of digits with 3 appearances is the same, 1 more digit that has 2 appearances and 1 less digit that appears once, multiplied by the number of digits that appear once.
• (10 - (number of digits that appear 3 times + number of digits that appear twice + number of digits that appear once)) multiplied by the number of combinations of length - 1 where there is number of digits with 3 appearances is the same, the number of digits that appear twice is the same and 1 more digit that appears once.

dp_table = {
    (1, 5) : 5,
    (1, 4) : 6,
    (1, 3) : 7,
    (1, 2) : 8,
    (1, 1) : 9,
    (1, 0) : 10,
}
 
def solve(*args):
    if args in dp_table:
        return dp_table[args]
    if args[0] == 1:
        return dp_table[args[:2]]
    result = 0
    cant = 10 - args[1]
    if args[2]:
        result += args[2] * solve(args[0] - 1, args[1] + 1, args[2] - 1, args[3])
        cant -= args[2]
    if args[3]:
        result += args[3] * solve(args[0] - 1, args[1], args[2] + 1, args[3] - 1)
        cant -= args[3]
    if cant:
        result += cant * solve(args[0] - 1, args[1], args[2], args[3] + 1)
    dp_table[args] = result
    return result
 
if __name__ == '__main__':
    length = 17
    result = 9 * solve(length, 0, 0, 1)
    print("The result is:", result)

The Python file is available for download here.