Let p(n) be the probability that a random n-digit integer has all 10 digits occurring each at least once.
Let us allow leading zeroes; e.g. 0000018274 will be included in the set of 10-digit numbers).
So p(9) is 0 , p(10) = 10!/1010 and p(1000) would be very close to 1.
a. What is the smallest n for which p(n) > 1/2?
b. >3/4?
c. >.95?
(In reply to
Matrix solution by Brian Smith)
To find a closed form expression for the original probability function, start by diagonalizing T into T = Q * D * Q^-1.
T is a lower-triangular matrix so its eigenvalues are simply the elements on the main diagonal. The corresponding eigenvectors turn out to be the rows of Pascal's triangle with alternating signs added. Then Q, D, and Q^-1 are:
[ 1 0 0 0 0 0 0 0 0 0 ] [0.1 0 0 0 0 0 0 0 0 0 ] [ 1 0 0 0 0 0 0 0 0 0 ]
[ -9 1 0 0 0 0 0 0 0 0 ] [ 0 0.2 0 0 0 0 0 0 0 0 ] [ 9 1 0 0 0 0 0 0 0 0 ]
[ 36 -8 1 0 0 0 0 0 0 0 ] [ 0 0 0.3 0 0 0 0 0 0 0 ] [ 36 8 1 0 0 0 0 0 0 0 ]
[ -84 28 -7 1 0 0 0 0 0 0 ] [ 0 0 0 0.4 0 0 0 0 0 0 ] [ 84 28 7 1 0 0 0 0 0 0 ]
[ 126 -56 21 -6 1 0 0 0 0 0 ] [ 0 0 0 0 0.5 0 0 0 0 0 ] [ 126 56 21 6 1 0 0 0 0 0 ]
[-126 70 -35 15 -5 1 0 0 0 0 ] [ 0 0 0 0 0 0.6 0 0 0 0 ] [ 126 70 35 15 5 1 0 0 0 0 ]
[ 84 -56 35 -20 10 -4 1 0 0 0 ] [ 0 0 0 0 0 0 0.7 0 0 0 ] [ 84 56 35 20 10 4 1 0 0 0 ]
[ -36 28 -21 15 -10 6 -3 1 0 0 ] [ 0 0 0 0 0 0 0 0.8 0 0 ] [ 36 28 21 15 10 6 3 1 0 0 ]
[ 9 -8 7 -6 5 -4 3 -2 1 0 ] [ 0 0 0 0 0 0 0 0 0.9 0 ] [ 9 8 7 6 5 4 3 2 1 0 ]
[ -1 1 -1 1 -1 1 -1 1 -1 1 ] [ 0 0 0 0 0 0 0 0 0 1 ] [ 1 1 1 1 1 1 1 1 1 1 ]
Then T^(n) = Q * D^(n) * Q^-1 Focusing on the element (10,1), its closed form valuation is f(n) = -1*0.1^n + 9*0.2^n - 36*0.3^n + 84*0.4^n - 126*0.5^n + 126*0.6^n - 84*0.7^n + 36*0.8^n - 9*0.9^n + 1. Then the original p(n) = f(n-1).
re: Matrix solution - Diagonalization and a closed form function
