Difficult combinatorics question...?

Question

Find the number of integers from 0 to 999999 that have no two equal neighboring digits in their decimal representation.

(Don't worry, this is not my homework or for a take-home test. If you look at some of my answers to questions, I am a math tutor and do math for fun.)

Ok, but to get the best answer you need to explain your formulas. =D

Answer 1

I have tried to write these formulae out, but they get messy.

So here:

the number of n-digit numbers WITH the property of equal neighboring digits = (9*10^n - 10*9^n) / 10

number of numbers WITH the property between 0 and 999...(n 9's) = 10^n - ( 9^[n+1] - 1) / 8

with n=6, this is 402,129

So your answer is 1,000,000 - 402,129 = 597,871

Steve

EDIT - Ok, the formulas:

Let #(m) denote the number of m-digit number with this property.

Then:

#(1) = 0
#(2) = 9
#(3)=?

Well the number of 3-digit numbers with equal consecutive digits is, by the inclusion-exclusion principle, the number with the first and second equal, which is 9*10, and the number with the second and third equal, which is also 9*10, less the number with all three equal which is 9. so #(3) = 9*10 + 9*10 - 9 = 171.

Continuing in this fashion, it is not hard to see that:

#(m) = Sum[1 to (n-1)] (-1)^(i-1) * 9 * C[(n-1),i] * 10^(n-1-i)

Where C[p,q] is the binomial coefficient.

Using the formula for an alternating exponential series, this is equal to:
(9*10^n - 10*9^n) / 10

Summing #(k) from k = 1 to n also gives, by some algebra,
10^n - ( 9^[n+1] - 1) / 8

Note that 10 and 9 are not specific numbers here. If the problem was in base b, with n the same, the formulas turn out to be:

#(m) = [ (b-1)b^n - b(b-1)^n ] / b

and total #(m) = b^n - [ (b-1)^(n+1) - 1 ] / (b-2) (assuming b>2)

2nd Edit:
Sometimes the attempt to be original obscures the obvious.

For m-digit numbers, we can select the most significant digit 9 ways, the next 9 ways, etc. So there are 9^m m-digit numbers that satisfy your criterion.

But then the # of numbers that satisfy it between 0 and 999,999 are 1 + 9 + 81 + ... + 9^6 = (9^7 - 1) / 8 = 597,871

Much easier.

Answer 2

as far as I can estimate, the probability of the 2nd digit being equal to the 1st digit is 0.1, and so for the following digits, which make the total probability for 2 identical consecutive numbers in a 6 digits number 0.5
so the total would be 0.5 *899999+ 0.4*89999+0.3*8999+0.2*899+0.1*89 for 6,5,4,3,2 digits numbers.
that is an inexact estimate since the result is not integer, which clearly should not be the case.

Answer 3

It's 10x9^5 which is 590490