Table of Contents
Overview: Problem 172
How many 18-digit numbers \(n\) (without leading zeros) are there
such that no digit occurs more than three times in \(n\)?
Link to Project Euler Problem 172
Background
Project Euler Problem 172 is your 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
Note that multiset permutations are also discussed on the following wiki pages and blog posts:
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!}
$$
A Simple Problem (And 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
$$
A slightly More Complicated Problem
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 }
$$
Algorithm
We can generalize the process. Suppose we are forming a number of length N from a number of digits/classes \(k\)
labeled from \(0 \dots k-1\), 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_0, N_1, N_2, \dots, N_{k-1}}
$$
where the limits of the summations are given by:
$$
N_1 = \min \left(N - (k-1) m, 0 \right) \dots m
$$
$$
N_2 = \min \left( N - N_1 - (k-2) m, 0 \right) \dots m
$$
etc...
$$
N_{k-1} = \min \left( N - N_1 - N_2 - \dots - N_{k-2}, 0 \right) \dots m
$$
these all fix the number of zeros N_0:
$$
N_0 = N - N_1 - N_2 - N_3 - \dots - N_k
$$
Notice that we ignore N_0 in the list of summations, because fixing the number of the first k-1 digits/classes
(1s, 2s, 3s, ..., (k-1)s) will fix the number of 0s. Alternatively, we could count 0s and include a summation over \(N_0\),
and eliminate the last summation over \(k-1\).
However, the multiset permutation expression includes ALL of the N's, from \(N_0\) to \(N_{k-1}\), since the choice
of each variable leads to additional permutations.
Also note that any algorithm implementing this procedure can save time by checking if, for the preceding combinations
of \(N\), we have already reached the maximum possible digits that can be selected. (Alternatively, we could write the
upper limit of the summations as expressions depending on the prior values of \(N_i\), but we'll keep it simple.)
Ignoring Numbers Starting with Zero
We have one last hurdle remaining, and that is how to ignore numbers that start with 0.
If we think about the problem as selecting the number of times each digit is repeated, then assembling that
selection into all possible permutations, fixing the first digit as 0 is equivalent to removing one from the
total length of the number that must be assembled, and removing one from the possible 0s that will go in the
final number. Thus, if we are assembling an N digit number from \(N_0\) 0s, \(N_1\) 1s, \(N_2\) 2s, \(N_3\) 3s, on up to \(N_9\) 9s,
then the total number of permutations is given by:
$$
\binom{ N }{N_0, N_1, \dots, N_9}
$$
If we fix the first digit as 0, the remaining number of permutations is given by:
$$
\binom{N-1}{ N_0-1, N_1, \dots, N_9 }
$$
Therefore, the number of permutations, excluding those beginning with 0, is written:
$$
\binom{ N }{N_0, N_1, \dots, N_9} - \binom{N-1}{ N_0-1, N_1, \dots, N_9 }
$$
Also, it is important to note that if N_0 = 0 to begin with, there are no possible ways of assembling numbers that begin with 0 because there are no 0s in the number, so the second term becomes 0:
$$
\binom{ N }{0, N_1, \dots, N_9} - 0
$$
Code
Test Cases
Test Case 1
Assemble two digits \(\{0,1\}\) into a 10-digit number, if each digit \(\{0,1\}\) can occur up to 5 times.
In this case, we know that 0 and 1 must occur exactly 5 times each. Now we are asking how we can assemble
two sets of 5 things into 10 slots. This is a multiset permutation problem:
$$
\binom{10}{5,5} = \dfrac{10!}{5! \cdot 5!} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252
$$
But wait! We also want to exclude numbers starting with 0, so we actually have:
$$
\binom{10}{5, 5} - \binom{9}{4, 5} = 126
$$
which is half of 252 - exactly what we would expect.
Test Case 2
Assemble three digits \(\{[0, 1, 2\}\) into a 6-digit number, if each digit \(\{0, 1, 2\}\) can occur up to 3 times. No number should start with 0.
In the prior case, we had one outcome of number of 0s and 1s, but in this case, we have a larger number of outcomes that we might see.
Evaluating the expressions for the limits of \(N_i\), we get:
$$
\sum_{N_0 = 0}^{3} \sum_{N_1 = \max(0, 3 - N_0) }^{3} \binom{6}{N_0, N_1, (N-N_0-N_1)}
$$
where \(N_2 = N - N_0 - N_1\). Written out, this becomes the total number of possible 6-digit numbers,
$$
a = \binom{6}{0,3,3} + \binom{6}{1,2,3} + \binom{6}{1,3,2} + \binom{6}{2,1,3} + \binom{6}{2,2,2} + \\
\binom{6}{2,3,1} + \binom{6}{3,0,3} + \binom{6}{3,1,2} + \binom{6}{3,2,1} + \binom{6}{3,3,0}
$$
minus the number of 6-digit numbers starting with 0:
$$
b = 0 + \binom{5}{0,2,3} + \binom{5}{0,3,2} + \binom{5}{1,1,3} + \binom{5}{1,2,2} + \\
\binom{5}{1,3,1} + \binom{5}{2,0,3} + \binom{5}{2,1,2} + \binom{5}{2,2,1} + \binom{5}{2,3,0}
$$
Let \(a\) be the first expression and \(b\) be the second expression; then the total is:
In [40]: np.sum(a)
Out[40]: 510.0
In [41]: np.sum(b)
Out[41]: 170.0
In [42]: np.sum(a) - np.sum(b)
Out[42]: 340.0
$$
a - b = 340
$$
Recursion
The essence of this problem is a nested for loop - but because we have 9 digits to deal with, a 9-level
nested for loop would be a big headache and would not generalize well.
Instead, we can write a recursive method that is called for each of the \(k\) (9) digits being selected
to compose the final \(N\)- (18-) digit number.
The recursive method looks something like this:
global variable solution_count
global variable m
global variable N
def recursive_method( n_tuple, n) {
if(n==9) {
compute multiset permutation combinations
increment global solutions total
need N, N0, N1, N2, etc.
} else {
assemble choices for N_i
for(choice in choices) {
set N_i to choice
call recursive_method()
unset N_i
}
}
}
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 is:
$$
\sum_{N_1} \sum_{N_2} \sum_{N_3} \sum_{N_4} \sum_{N_5} \sum_{N_6} \sum_{N_7} \sum_{N_8} \sum_{N_9} \binom{N}{N_0, N_1, N_2, \dots, N_9} - \binom{N-1}{N_0-1, N_1, N_2, \dots, N_9}
$$
where the limits of summation are given by:
$$
N_1 = \max \left( N - (10-1) m, 0 \right) \dots m
$$
$$
N_2 = \max \left( N - N_1 - (10-2) m, 0 \right) \dots m
$$
$$
N_3 = \max \left( N - N_1 - N_2 - (10-3) m, 0 \right) \dots m
$$
$$
N_4 = \max \left( N - N_1 - N_2 - N_3 - (10-4) m, 0 \right) \dots m
$$
etc...
$$
N_9 = \max \left( N - N_1 - N_2 - \dots - N_7 - N_8, 0 \right) \dots m
$$
and from these, \(N_0\) is determined by:
$$
N_0 = N - N_1 - N_2 - \dots - N_8 - N_9
$$
Python Code
Link to Problem 172 Python Code at git.charlesreid1.com
To implement the solution to Problem 172 in Python, we used recursion, as mentioned above.
THe only tricky part of implementing this recursive method was the usual challenge with
recursive methods: keeping track of the total number of solutions found via a global variable.
To do this in Python, we declare a variable outside the scope of a given function, and we use
that variable as a global variable by declaring it with the global keyword.
import numpy as np
# Real problem:
k = 10
m = 3
N = 18
solution_count = 0
factorials = {}
Now we have a main() driver method to call the recursive method:
def main():
global solution_count
n_tuple = [None,]*k
recursive_method(n_tuple,1)
print("Total number of permutations:")
print("%d"%(solution_count))
We have the recursive backtracking method that constructs
all combinations of \(k\) digits into \(N\)-digit numbers:
def recursive_method( n_tuple, ni ):
"""
Use recursive backtracking to form all possible
combinations of k digits into N-digit numbers
such that the number of digits is m or less.
(n_tuple is actually a list.)
ni = current class step 1..(k-1)
n_tuple = list of number of digits for each class 0 through k
"""
global solution_count, k, m, N
if(ni==k):
# N_1 through N_(k-1) have been set,
# now it is time to set N_0:
# N_0 = N - N_1 - N_2 - N_3 - .. - N_{k-1}
sum_N = np.sum([n_tuple[j] for j in range(1,k)])
n_tuple[0] = max(0, N-sum_N)
# Compute multiset permutation
solution_count += multiset(N,n_tuple) - multiset_0(N,n_tuple)
return
else:
# Problem: we are not stopping
# when the sum of digits chosen
# is greater than N
# Assemble the minimum and maximum limits for N_i:
# (Everything up to ni-1 should be defined, no TypeErrors due to None)
sum_N = np.sum([n_tuple[j] for j in range(1,ni)])
ktm = (k - ni)*m
expr = N - sum_N - ktm
minn = int(max( 0, expr ))
# Note: previously this was just maxx=m.
# This required a check around each call to
# recursive_method to see if the sum of n_tuple
# was already maxed out. Now we just do it here.
maxx = min(m, N-sum_N)
for N_i in range(minn,maxx+1):
# Set
n_tuple[ni] = N_i
# Explore
recursive_method(n_tuple, ni+1)
# Unset
n_tuple[ni] = None
return
We have a multiset() method that evaluates the multiset permutation count formula:
$$
\binom{N}{N_1, \dots, N_k} = \dfrac{N!}{N_1! \dots N_k!}
$$
def multiset(N, n_tuple):
"""
Number of multiset permutations
"""
r = factorial(N)/(np.product([factorial(j) for j in n_tuple]))
return r
def multiset_0(N, n_tuple):
"""
Number of multiset permutations that start with 0
"""
if(n_tuple[0]>0):
r = factorial(N-1)/(np.product([factorial(j-1) if(i==0) else factorial(j) for i,j in enumerate(n_tuple)]))
return r
else:
return 0
And finally, we have a factorial() method:
def factorial(n):
"""
Factorial utility
"""
if(n<0):
raise Exception("Error: negative factorials not possible")
if(n==1 or n==0):
return 1
else:
return n*factorial(n-1)
At the bottom of the file, we ensure that the driver is run when the
funtion is run directly through Python:
if __name__=="__main__":
main()
Final Answer
Setting the correct parameters should result in the following result:
$$
P = 227,485,267,000,992,000
$$
