Project Euler/172

Problem Statement

Link: https://projecteuler.net/problem=172

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

Explanation

A classic Project Euler problem: short, simple, and overwhelmingly complicated.

To nail this one, it's important to start simple - very simple. What I'll do is walk through the process of breaking this problem down to find and generalize the patterns needed to count permutations of digits.

First, in combinatorics problems it is important to think about what is changing, and how to count possible outcomes one piece at a time. Then the overall pieces can be combined to get the total count. In this case, we can think about a case for each digit: the case of 3 occurrences, the case of 2 occurrences, the case of 1 occurrence, and the case of 0 occurrences. Depending on the case, we limit our choices for later digits.

Let's start with a similar, but much simpler, problem: how do we construct a binary number with N digits and no more than m 0s and no more than m 1s?

In fact, let's make it even easier: how do we construct a 10 digit binary number with no more than 5 0's and no more than 5 1's?

The answer is, there is only ONE way to choose no more than 5 0's and no more than 5 1's to form a 10 digit number, and that's by having exactly 5 0's and 5 1's. Now that we know exactly how many of each digit we have, we can count the number of permutations of the number 0000011111 (the number of permutations).

Multiset Permutations

Also see article on lattice paths.

If we are selecting from a group of $ N_1 $ things of type A, $ N_2 $ things of type B, and $ N_3 $ things of type C to form a total of $ N $ things, this type of combinatorics problem is called a multiset permutation, and the total number of ways of arranging this set of 3 things is given by:

$ \binom{N}{N_1, N_2, N_3} = \dfrac{N!}{N_1! N_2! N_3!} $

In fact, this generalizes, for $ k $ classes of things we have a k-set permutation:

$ \binom{N}{N_1, \dots, N_k} = \dfrac{N!}{N_1! \dots N_k!} $

Solution

Back to the problem at hand: to count the number of ways of placing 5 0s and 5 1s to form a 10 digit number.

Once we place 5 digits into any of the 10 available slots, that fixes the locations of the remaining 5 digits. However, we still have to include two 5! values, to account for all possible duplicates if we exchanged all 5 of the 1s with one another, or all 5 of the 0s with one another. We use the expression:

$ \binom{10}{5} = \dfrac{10!}{5! 5!} = 10 \times 9 \times 8 \times 7 \times 6 $

Slightly More Complicated

To solve a slightly more complicated problem: suppose we have to assemble a 10-digit binary number from no more than 6 0s and no more than 6 1s?

Now we have 3 possible cases of numbers of 0s:

4 0s: 0000111111 - and its permutations

5 0s: 0000011111 - and its permutations

6 0s: 0000001111 - and its permutations

For each of these cases, we can think of it as the "bucket" of 0s containing 4 0s (5 and 6 0s, respectively) and the "bucket" of 1s containing 6 1s (5 and 4 1s, respectively). We still have a number of permutations that we can form using this given number of 0s and 1s, given by a multiset permutation expression.

For each case, we have a multiset permutation expression that tells us how many permutations we can form from the given number of 0s and 1s:

$ \binom{ N }{ N_0, N_1 } $

So we have three possible outcomes, and the total number of arrangements is the sum of these three cases:

$ N_{perms} = \binom{ 10 }{ 6, 4} + \binom{ 10 }{ 5, 5 } + \binom{ 10 }{ 6 , 4 } $

Generalizing

We can generalize the process. Suppose we are forming a number of length $ N $ from a number of digits/classes $ k $, and each digit/class can only appear a maximum of $ m $ times.

The number of combinations that can be formed for a given $ N, k, m $ is given by the multiset permutation expression above. So the total number of permutations that can be formed is a sum of these multiset permutation expressions, over each possible combination of digits/classes into a number of length $ N $.

In computer science terms, we can think of this as a nested for loop or dynamic program; in mathematical terms, we can think of a sequence of summations whose limits depend on the variables in the other summations.

$ \sum_{N_1} \sum_{N_2} \dots \sum_{N_k} \binom{N}{N_1, N_2, \dots, N_k} $

where the limits of the summations are given by:

$ N_1 = \min \left(N - (k-1) m, 0 \right) \dots m <math> <math> N_2 = \min \left( N - N_1 - (k-2) m, 0 \right) \dots m $

etc...

$ N_k = \min \left( N - N_1 - N_2 - \dots - N_{k-1}, 0 \right) \dots m $

Code

Pseudocode

Computing the number of possible integers n that meet the specified criteria thus boils down to a long sequence of nested summations (nested loops).

The problem is posed for $ N=18, k = 10, m = 3 $. For this case, the final expression for the total number of permutations