All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Pandigital + (Posted on 2017-05-03)
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?

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: Matrix solution - Diagonalization and a closed form function Comment 3 of 3 |
(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).

 Posted by Brian Smith on 2017-05-04 12:23:54

 Search: Search body:
Forums (0)